次の数
４２９４９６７２９７
を見て、「これって、素因数分解可能？」と問われて、「うん、できるね！」と即答できる人は、
数学のよほどの熟達者か、もしくは単なる楽天家のどちらかだろう。
私自身、すぐに「そうだね！」と相槌が打てるほど力も自信もない。
しかし、この数は整数論の世界では有名すぎる数である。
の形の数は、フェルマー数といわれる。
因みに、 ｎ＝１ のとき、 ２2＋１＝５ で、これは、素数！ （→ 素数表）
ｎ＝２ のとき、 ２4＋１＝１７ で、これは、素数！
ｎ＝３ のとき、 ２8＋１＝２５７ で、これは、素数！
ｎ＝４ のとき、 ２16＋１＝６５５３７ で、これは、素数！
とくれば、 ｎ＝５ のとき、 ２32＋１＝４２９４９６７２９７ も素数？
と考えるのが人情だろう。
この期待を見事に裏切ったのがオイラー（１７３２年）である。
オイラーが用いた方法とは全く異なるが、エレガントな方法で素因数分解するとすれば、
次のようになるであろう。
２32＝２28・２4＝（２7）4・２4 において、 ２4＝１６ 、２7＝１２８ であるが、５4＝５２５
であることを考えると、
２4＋５4＝６４１ 、 ５・２7＝６４０
という２つの式が成り立つ。このとき、 ２4＋５4＝Ｎ とおくと、 ５・２7＝Ｎ−１ である。
そこで、 ２32＋１＝２28・２4＋１
＝２28・２4＋（２28−（２7）4）・５4＋１ （← このアイデアはすごい！）
＝２28・（２4＋５4）−（５・２7）4＋１
＝２28・Ｎ−（Ｎ−１）4＋１
＝２28・Ｎ−Ｎ4＋４Ｎ3−６Ｎ2＋４Ｎ−１＋１
＝２28・Ｎ−Ｎ4＋４Ｎ3−６Ｎ2＋４Ｎ
＝Ｎ・（２28−Ｎ3＋４Ｎ2−６Ｎ＋４）
＝６４１×６７００４１７
したがって、
４２９４９６７２９７＝６４１×６７００４１７ （← う〜む、感動！！）
因みに、オイラーはどのようにして求めたのだろうか？
実は、オイラーの用いた方法は、上記のようなエレガントな方法ではなく、地道な計算だ
ったようだ。
ただ、一般人が、素数 ２、３、５、７、・・・ で順次割っていくのとは違って、次の事実を活
用して能率よく見つけたそうだ。
フェルマー数が素因数 Ｐ を持てば、 Ｐ≡１ （ｍｏｄ ２ｎ＋1）
この事実から、ｎ＝５ の場合は、素因数として
１９３ 、２５７ 、４４９ 、５７７ 、６４１ 、・・・・・
について調べれば十分である。（← 上手いですね〜！）
実際に割り算をして、ようやく、５番目の数 ６４１ で割り切れることを確認したのだろう。
オイラーの活用した公式が気になるので、証明しておこう。
フェルマー数が素因数 Ｐ （Ｐ≠２）を持つとする。以下で、簡単のため、２ｎ＝ｍ とおく。
このとき、 ２ｍ＋１≡０ （ｍｏｄ Ｐ） より、 ２2ｍ≡１ （ｍｏｄ Ｐ） が成り立つ。
このことから、 ２k≡１ （ｍｏｄ Ｐ） となる自然数 ｋ は、２ｍ＝２ｎ＋1 の約数である。
ｋ＝１、２、２2、２3、・・・、２ｎ の場合は、２ｍ≡−１ （ｍｏｄ Ｐ） に矛盾するので起こり
えない。
よって、 ２k≡１ （ｍｏｄ Ｐ） となる最小の自然数 ｋ は、 ｋ＝２ｎ＋1 となる。
ここで、オイラーの定理により、 ２Ｐ−1≡１ （ｍｏｄ Ｐ） が成り立つが、
ｋ＝２ｎ＋1 の最小性から、２ｎ＋1 は、Ｐ−１ の約数でなければならない。
よって、 Ｐ−１≡０ （ｍｏｄ ２ｎ＋1） より、 Ｐ≡１ （ｍｏｄ ２ｎ＋1） が成り立つ。
（証終）
ところで、 ４２９４９６７２９７＝６４１×６７００４１７ において、６４１ や ６７００４１７ が
素数であることは、Ｅｘｃｅｌ のＶＢＡ を用いて簡単に示される。
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
Ｅｘｃｅｌ を起動し、[ツール]−[マクロ]−[Ｖｉｓｕａｌ Ｂａｓｉｃ Ｅｄｉｔｏｒ] とクリックして Ｅｄｉｔｏｒ
を起動し、[挿入]−[標準モジュール] を選択して、上記を記述すればよい。後は、Ｅｘｃｅｌ
の任意のセルに、例えば、 ＝f（１２，２） と打ち込むと、瞬時に、２×２×３ と素因数分
解される。「×」を用いた式が出なければ、それは素数ということになる。
是非、皆さんも試してみてくださいネ！
（参考文献：和田秀男 著 数の世界 整数論への道 （岩波書店））
