2016年2月27日土曜日

素数 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) より百万日後は火曜日だw
以前の記事「不定方程式」

「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)をわかる1」

0 件のコメント:

コメントを投稿

「コメントの記入者:」は「匿名」ではなく,「名前/URL」を選んで,なにかニックネームを入れてください.URL は空欄で構いません.