・ グッとくる素因数分解 S.H氏
次の数
4294967297
を見て、「これって、素因数分解可能?」と問われて、「うん、できるね!」と即答できる人は、
数学のよほどの熟達者か、もしくは単なる楽天家のどちらかだろう。
私自身、すぐに「そうだね!」と相槌が打てるほど力も自信もない。
しかし、この数は整数論の世界では有名すぎる数である。
の形の数は、フェルマー数といわれる。
因みに、 n=1 のとき、 22+1=5 で、これは、素数! (→ 素数表)
n=2 のとき、 24+1=17 で、これは、素数!
n=3 のとき、 28+1=257 で、これは、素数!
n=4 のとき、 216+1=65537 で、これは、素数!
とくれば、 n=5 のとき、 232+1=4294967297 も素数?
と考えるのが人情だろう。
この期待を見事に裏切ったのがオイラー(1732年)である。
オイラーが用いた方法とは全く異なるが、エレガントな方法で素因数分解するとすれば、
次のようになるであろう。
232=228・24=(27)4・24 において、 24=16 、27=128 であるが、54=525
であることを考えると、
24+54=641 、 5・27=640
という2つの式が成り立つ。このとき、 24+54=N とおくと、 5・27=N−1 である。
そこで、 232+1=228・24+1
=228・24+(228−(27)4)・54+1 (← このアイデアはすごい!)
=228・(24+54)−(5・27)4+1
=228・N−(N−1)4+1
=228・N−N4+4N3−6N2+4N−1+1
=228・N−N4+4N3−6N2+4N
=N・(228−N3+4N2−6N+4)
=641×6700417
したがって、
4294967297=641×6700417 (← う〜む、感動!!)
因みに、オイラーはどのようにして求めたのだろうか?
実は、オイラーの用いた方法は、上記のようなエレガントな方法ではなく、地道な計算だ
ったようだ。
ただ、一般人が、素数 2、3、5、7、・・・ で順次割っていくのとは違って、次の事実を活
用して能率よく見つけたそうだ。
フェルマー数が素因数 P を持てば、 P≡1 (mod 2n+1)
この事実から、n=5 の場合は、素因数として
193 、257 、449 、577 、641 、・・・・・
について調べれば十分である。(← 上手いですね〜!)
実際に割り算をして、ようやく、5番目の数 641 で割り切れることを確認したのだろう。
オイラーの活用した公式が気になるので、証明しておこう。
フェルマー数が素因数 P (P≠2)を持つとする。以下で、簡単のため、2n=m とおく。
このとき、 2m+1≡0 (mod P) より、 22m≡1 (mod P) が成り立つ。
このことから、 2k≡1 (mod P) となる自然数 k は、2m=2n+1 の約数である。
k=1、2、22、23、・・・、2n の場合は、2m≡−1 (mod P) に矛盾するので起こり
えない。
よって、 2k≡1 (mod P) となる最小の自然数 k は、 k=2n+1 となる。
ここで、オイラーの定理により、 2P−1≡1 (mod P) が成り立つが、
k=2n+1 の最小性から、2n+1 は、P−1 の約数でなければならない。
よって、 P−1≡0 (mod 2n+1) より、 P≡1 (mod 2n+1) が成り立つ。
(証終)
ところで、 4294967297=641×6700417 において、641 や 6700417 が
素数であることは、Excel のVBA を用いて簡単に示される。
Function f(n, d)
If n < d * d Then
f = n
Else
If n - Int(n / d) * d = 0 Then
f = d & "x" & f(n / d, d)
Else
If d = 2 Then
d = 3
Else
If d = 3 Then
d = 5
Else
If d Mod 6 = 1 Then d = d + 4 Else If d Mod 6 = 5 Then d = d + 2
End If
End If
f = f(n, d)
End If
End If
End Function
Excel を起動し、[ツール]−[マクロ]−[Visual Basic Editor] とクリックして Editor
を起動し、[挿入]−[標準モジュール] を選択して、上記を記述すればよい。後は、Excel
の任意のセルに、例えば、 =f(12,2) と打ち込むと、瞬時に、2×2×3 と素因数分
解される。「×」を用いた式が出なければ、それは素数ということになる。
是非、皆さんも試してみてくださいネ!
(参考文献:和田秀男 著 数の世界 整数論への道 (岩波書店))