フォロー
香港で公開された英数学者A・チューリングの手稿〔AFPBB News〕
素数は難しい
1と自分自身のみを約数に持つ自然数が素数です。2、3、5、7、11、13、17、19、23、29、31、37、41、…。約数さえ理解できれば素数自体は容易です。
87は素数でしょうか。87＝3×29なので87は素数ではありません。1より大きい自然数で素数でない数を合成数と呼びます。では、1729はどうでしょう。少し時間をかければ、1729＝7×13×19と分かり1729は合成数です。
与えられた数が大きくなると素数か合成数の判定は途端に容易ではなくなります。ここに数学が必要になります。
その意味で素数は難しいと言えます。連載「サラリーマンのための超入門・リーマン予想」でも紹介したリーマンによるリーマン予想（1859年）の発見は、素数探究の末にたどり着いた深い闇です。
ところで1より大きい自然数は素数か合成数のどちらかでしたから、素数判定とともに合成数判定も考えられます。合成数とは2つ以上の素数の積で表すことができる自然数のことです。例えば6や30はそれぞれ2×3、2×3×5と素数の積で表される合成数です。
「フェルマーの小定理」を確かめる
フェルマーの小定理といわれる定理があります。「pが素数ならば、任意の整数nのp乗をpで割った余りはnである」というものです。
ちなみに同じフェルマーによるフェルマーの大定理は、「3以上の自然数nに対してx^n+y^n=z^nは自然数の解をもたない」というもので1994年にワイルズによって証明されました。
ではフェルマーの小定理を具体的に計算して確かめてみましょう。
素数p=3の場合
n=2 2^3=8 → 3で割ると商が2で、余りは2
n=3 3^3=27 → 3で割ると商を８として、余りは3
n=4 4^3=64 → 3で割ると商を20として、余りは4
n=5 5^3=125 → 3で割ると商を40として、余りは5
素数p=5の場合
n=2 2^5=32 → 5で割ると商が6で、余りは2
n=3 3^5=243 → 5で割ると商を48として、余りは3
n=4 4^5=1024 → 5で割ると商を204として、余りは4
n=5 5^5=3125 → 5で割ると商を624として、余りは5
このように余りはnと等しいことが分かります。もっと大きな数で確かめてみましょう。
素数p=17の場合
n=2 2^17=131072 → 17で割ると商が7710で、余りは2
n=3 3^17=129140163 → 17で割ると商が7596480で、余りは3
n=4 4^17=17179869184 → 17で割ると商が1010580540で、余りは4
n=5 5^17=762939453125 → 17で割ると商が44878791360で、余りは5
やはり最後の余りはnと等しくなります。「任意の整数nのp乗」の指数部分pが素数でないとこうはなりません。例えば、指数部分を6とすれば、
素数でないp=6の場合
n=2 2^6=64 → 6で割ると商が10で、余りは4
n=3 3^6=729 → 6で割ると商が121で、余りは3
n=4 4^6=4096 → 6で割ると商が682で、余りは4
n=5 5^6=15625 → 6で割ると商が2604で、余りは1
となり余りがnと等しくない場合が出てきます。
