p=q^n-n^n を満たす素数と自然数の組

p,q素数、n自然数、p=q^n-n^nを満たす組(p,q,n)を全て求めよ。（shimomire様）

n が素数または 1 であることを背理法で証明する。

n が合成数、すなわち n = ab（a, b は 2 以上の自然数）と書けたとすると、
右辺 = q^n - n^n
　　　= q^ab - n^ab
　　　= ( q^a - n^a ) { q^a(b-1) + q^a(b-2) n^a + …… + n^a(b-1) }
　　　= (q-n) { q^(a-1) + q^(a-2) n + …… + n^(a-1) }
　　　　　　　× { q^a(b-1) + q^a(b-2) n^a + …… + n^a(b-1) }
いま a≧2 なのでこの積の 2 番目と 3 番目は明らかに 2 以上である。
よって右辺は合成数。
一方左辺 p は素数であるのでこの等式は矛盾している。
よって n は素数または 1 である。


n=1 のとき
p=q-1 より p=2, q=3

n が素数のとき
右辺 = q^n - n^n
　　　= (q-n) { q^(n-1) + q^(n-2) n + …… + n^(n-1) }
この積の 2 番目は明らかに 2 以上 である。
しかしこれが素数 p と一致するのだから、q-n = 1
いま q も n も素数であるから、q=3, n=2
このとき p = 3^2-2^2 = 5

よって、(p, q, n) = (2, 3, 1), (5, 3, 2)