素数 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)をわかる１」