素数 p，q を用いて，p^q + q^p と表される素数をすべて求めよ．

久々の数学ネタ．


素数 p，q を用いて，\(p^q+q^p\) と表される素数をすべて求めよ．
だって．＞twitter
答えは知ってて 17 だけど，普通は，まずは試行錯誤して，並ぶ数字から考えるしかない．というか 17 がすぐ見つかるけれど，「すべて求めよ．」だから，17以外にないことは証明しなければならない．そっちが大変．

試行錯誤

素数は 2, 3, 5, 7, 11, 13, 17, 19, ...
\(2^2+2^2=4+4=8\) でハズレ．
って，偶数+偶数=偶数だから，p=q=2 では素数にはなりえない．

さらに，奇数+奇数=偶数 だから， p，q が両方とも奇数というものありえない．
というもの，このとき，\(p^q\)，\(q^p\) どちらも，素因数 2 が入り込む余地がなく，どちらも奇数だからである．

だからp，qの片方は 2 で，もう一方は 3 以上の素数といえる．．

\(2^3+3^2=8+9=17\) で命中．
\(2^5+5^2=32+25=57=3\times19\) でハズレ．
\(2^7+7^2=128+49=177=3\times59\) でハズレ．
\(2^{11}+11^2=2048+121=2169=3\times723\) でハズレ．
\(2^{13}+13^2=8192+169=8361=3\times2787\) でハズレ．
命中以外は，なんか 3の倍数が並ぶなぁ．

＋ の左側，2の奇素数乗 8，32，128，2048，8191 は，どれも3で割ると 2 余る．
＋ の右側，5以上の素数の2乗 25，49，121，169 は，どれも3で割ると 1 余る．
2 余る数と，1余る数を足せば，当然3で割り切れるわけだ．
だから，答えは 17 しかなく，p=2で qが5以上の素数の時，いつも3で割り切れることを「証明」して解答の完成となる．

実際の証明は，
(1)「2の奇素数乗は，3で割ると 2 余る．」
と
(2)「5以上の素数の2乗は，3で割ると 1 余る．」
の2本を書いて，
(3) (1)(2)より「2 余る数と，1余る数を足せば，3で割り切れる」から
「p=2で qが5以上の素数の時，\(p^q+q^p\) は3で割り切れる」と言えばよい．
ここからは，証明の技術的な問題．

「2の奇素数乗は，3で割ると 2 余る．」

実際は条件を奇素数乗より弱めて「2の奇数乗は，3で割ると 2 余る．」を示す．奇数で成り立てば a fortiori 奇素数でも成り立つので．

\(2=3-1\) と考えると．
\((3-1)^3=3^3+3\times3^2(-1)+3\times3(-1)^2+(-1)^3\)
\((3-1)^5 \\ =3^5+5\times3^4(-1)+10\times3^3(-1)^2+10\times3^2(-1)^3+5\times3(-1)^4+(-1)^5\)
で，最終項 \((-1)^q=-1\) 以外はすべて 3 を因数に含むから，\((3-1)^q=2^q\) はいつも（3の倍数-1） で，3で割ると 2 が余るのだろう．

（泥臭い証明）
奇数 q に対し，\(2^q=(3-1)^q\) とする．
\(2^q=(3-1)^q\) を展開すると，2項定理により，
\(2^q={}_qC_03^q+{}_qC_13^{q-1}(-1)+{}_qC_23^{q-2}(-1)^2 \\ +\cdots+{}_qC_{q-1}3(-1)^{q-1}+{}_qC_q(-1)^q\)
この最終項以外はすべて3を因数として含むので，整数 M に対し，
\(2^q=3M+{}_qC_q(-1)^q=3M+(-1)^q=3M+(-1) \\ =3M+(-3)+2=3(M-1)+2\)
より，\(2^q\) は3で割ると 2 余る．（証明おわり）
inductionによる証明＞追記：「数学的帰納法」

合同式を使えば，簡潔になる．（簡潔にかけばわかりやすいというものではないが）
（証明）
\(2\equiv-1\pmod3\)
\(2^q\equiv(-1)^q\pmod3\)
qは奇数だから，
\((-1)^q=-1\)
よって，
\(2^q\equiv-1\equiv2\pmod3\)
より，\(2^q\) は3で割ると 2 余る．（証明おわり）

合同式とは (mod 3) のとき，3で割った余りが等しい時に，≡ という記号を使う．
－9 ≡ －6 ≡ －3 ≡ 0 ≡ 3 ≡ 6 ≡ 9 (mod 3)，
－8 ≡ －5 ≡ －2 ≡ 1 ≡ 4 ≡ 7 ≡ 10 (mod 3)，
－7 ≡ －4 ≡ －1 ≡ 2 ≡ 5 ≡ 8 ≡ 11 (mod 3)
である．
1≡10(mod 3)の両辺に等しい数の加減乗と，同じ累乗しても ≡は変わらないという著しい性質があって，余りの計算が便利といえる．（割り算はだめ）
これを使うと月曜日の 10日後は 10≡3(mod 7) より3日後と同じ木曜日とすぐわかり，両辺2乗しても≡だから，100≡9≡2 (mod 7) より百日後は2日後と同じ水曜日，さらに3乗して，1000000≡8≡1 (mod 7) より百万日後は火曜日だｗ
＞以前の記事「不定方程式」

「5以上の素数の2乗は，3で割ると 1 余る．」

実際は条件を5以上の素数より弱めて「3で割り切れない数の2乗を3で割ると 2 余る．」を示す．3で割り切れない数で成り立てば a fortiori それに含まれる5以上の素数でも成り立つので．

「平方数を3で割った余りは2にならない」
の証明は，教科書にもある練習問題である．
余りが 0 になるのは3の倍数の平方だけなので，3で割り切れない数の平方は必ず 1 になるといえる．

（泥臭い証明）
5以上の素数q はすべて3で割り切れないから，3で割ると余りは 1 か 2 である．
したがって，整数 k について，\(q=3k+1\) or \(q=3k+2\) と書ける．
(i) \(q=3k+1\) のとき，
\(q^2=(3k+1)^2=9k^2+6k+1=3(3k^2+2k)+1\)
\((3k^2+2k)\) は整数だから，\(q^2\) は3で割ると 1 余る．
(ii) \(q=3k+2\) のとき，
\(q^2=(3k+2)^2=9k^2+12k+4=9k^2+12k+3+1 \\ =3(3k^2+4k+1)+1\)
\((3k^2+4k+1)\) は整数だから，\((3k^2+2k)\) は整数だから，\(q^2\) は3で割ると 1 余る．
つまり，3で割り切れない数を2乗すると必ず余りが1 になる．（証明おわり）

（合同式による証明）
5以上の素数q はすべて3で割り切れないから，3で割ると余りは 1 か 2≡－1 (mod3) である．
よって，q≡1 (mod 3) または q≡－1 (mod 3) である．
q≡1 (mod 3) のとき両辺2乗して，q^2≡1 (mod 3)
q≡－1 (mod 3) のとき両辺2乗して，q^2≡1 (mod 3)
より，5以上の素数2乗してを3で割ると，余りが1となる．（証明おわり）

「5以上の素数qは3で割り切れない」というのが大事なところだな．
素数以外の q=9 だと 2^9+9^2 = 512+81 = 593 = 3*197 + 2 と破綻してしまう．（593自体は素数だが）

解答例

泥臭い証明を長々・・・でなく，合同式をつかってすっきり解答を清書すれば次の通り．

（解答）
p=q=2 のとき，\(2^2+2^2\)は素数ではない．
p，q ともに奇素数のとき，\(p^q\)，\(q^p\) ともに奇数となり，その和は偶数なので，素数ではない．
したがって，p，q の片方が2で，もう片方は3以上の奇数である．
p=2，q=3 のとき，\(2^3+3^2=17\)は素数である．
ここで，p=2，qは5以上の素数とする．
\(2\equiv-1\pmod3\) より \(2^q\equiv(-1)^q\pmod3\)

qは奇数だから，\((-1)^q=-1\) より，\(2^q\equiv-1\pmod3\)．
5以上の素数pは3で割り切れないので，\(p\equiv\pm1\pmod3\) より \(p^2\equiv(\pm1)^2=1\)
ゆえに，\(2^p+p^2\equiv-1+1=0\pmod3\)
したがって，p=2，qは5以上の素数はのときの\(p^q+q^p\)は，3の倍数なので素数でない．
ゆえに，素数 \(p,q\) を用いて，\(p^q+q^p\) と表される素数は，17 のみである．（解答おわり）

と極めて簡潔だけれど，整数論のリテラシーがないと，まさに「なんのことやら」

整数論はネットの暗号技術を支える理論である．＞以前の記事「公開鍵暗号(RSA)をわかる１」