1. $ n = 1 $の場合: $ 157115 = 5 \times 7 \times 67^2 $
2. $ n = 2 $の場合: $ 314229 = 3 \times 104743 $
3. $ n = 3 $の場合: $ 628457 = 73 \times 8609 $
4. $ n = 4 $の場合: $ 1256913 = 3^2 \times 7 \times 71 \times 281 $
5. $ n = 5 $の場合: $ 2513825 = 5^2 \times 193 \times 521 $
6. $ n = 6 $の場合: $ 5027649 = 3 \times 11 \times 131 \times 1163 $
7. $ n = 7 $の場合: $ 10055297 = 7 \times 1436471 $
8. $ n = 8 $の場合: $ 20110593 = 3 \times 541 \times 12391 $
9. $ n = 9 $の場合: $ 40221185 = 5 \times 59 \times 136343 $
10. $ n = 10 $の場合: $ 80442369 = 3^3 \times 7^2 \times 41 \times 1483 $

使用したプログラム

はるか

Sympyのfactorintメソッドを使用して素因数分解をした。

import sympy as sp

# 定数
base = 78557

# 素因数分解の結果を保存するリスト
factorizations = []

# n = 1 から 10 までの計算と素因数分解
for n in range(1, 11):
    result = base * 2**n + 1
    factors = sp.factorint(result)
    factorizations.append((n, result, factors))

合成数であることの証明

証明の前の準備

はるか

まぁ、証明の準備の前にn=36まで確認してみる。なぜ、36までかは突っ込まないで。

1. $ n = 1 $: $ 157115 = 5 \times 7 \times 67^2 $
2. $ n = 2 $: $ 314229 = 3 \times 104743 $
3. $ n = 3 $: $ 628457 = 73 \times 8609 $
4. $ n = 4 $: $ 1256913 = 3^2 \times 7 \times 71 \times 281 $
5. $ n = 5 $: $ 2513825 = 5^2 \times 193 \times 521 $
6. $ n = 6 $: $ 5027649 = 3 \times 11 \times 131 \times 1163 $
7. $ n = 7 $: $ 10055297 = 7 \times 1436471 $
8. $ n = 8 $: $ 20110593 = 3 \times 541 \times 12391 $
9. $ n = 9 $: $ 40221185 = 5 \times 59 \times 136343 $
10. $ n = 10 $: $ 80442369 = 3^3 \times 7^2 \times 41 \times 1483 $
11. $ n = 11 $: $ 160884737 = 13 \times 523 \times 23663 $
12. $ n = 12 $: $ 321769473 = 3 \times 43 \times 47 \times 73 \times 727 $
13. $ n = 13 $: $ 643538945 = 5 \times 7 \times 1759 \times 10453 $
14. $ n = 14 $: $ 1287077889 = 3 \times 353 \times 599 \times 2029 $
15. $ n = 15 $: $ 2574155777 = 19 \times 135481883 $
16. $ n = 16 $: $ 5148311553 = 3^2 \times 7 \times 11 \times 7429021 $
17. $ n = 17 $: $ 10296623105 = 5 \times 2059324621 $
18. $ n = 18 $: $ 20593246209 = 3 \times 6864415403 $
19. $ n = 19 $: $ 41186492417 = 7 \times 1583 \times 3716857 $
20. $ n = 20 $: $ 82372984833 = 3 \times 53 \times 173 \times 311 \times 9629 $
21. $ n = 21 $: $ 164745969665 = 5 \times 73 \times 451358821 $
22. $ n = 22 $: $ 329491939329 = 3^2 \times 7 \times 101 \times 51782483 $
23. $ n = 23 $: $ 658983878657 = 13 \times 811 \times 62504399 $
24. $ n = 24 $: $ 1317967757313 = 3 \times 439322585771 $
25. $ n = 25 $: $ 2635935514625 = 5^3 \times 7 \times 63337 \times 47563 $
26. $ n = 26 $: $ 5271871029249 = 3 \times 11 \times 29 \times 43 \times 128110399 $
27. $ n = 27 $: $ 10543742058497 = 37 \times 167 \times 42209 \times 40427 $
28. $ n = 28 $: $ 21087484116993 = 3^3 \times 7 \times 1873 \times 59569669 $
29. $ n = 29 $: $ 42174968233985 = 5 \times 75659 \times 111486983 $
30. $ n = 30 $: $ 84349936467969 = 3 \times 41 \times 73 \times 859 \times 10936129 $
31. $ n = 31 $: $ 168699872935937 = 7^2 \times 109 \times 31585821557 $
32. $ n = 32 $: $ 337399745871873 = 3 \times 463^2 \times 524640139 $
33. $ n = 33 $: $ 674799491743745 = 5 \times 19 \times 541301 \times 13122371 $
34. $ n = 34 $: $ 1349598983487489 = 3^2 \times 7 \times 181 \times 1579 \times 1861 \times 40277 $
35. $ n = 35 $: $ 2699197966974977 = 13 \times 47 \times 93755653 \times 47119 $
36. $ n = 36 $: $ 5398395933949953 = 3 \times 11 \times 163587755574241 $

はるか

んー。よく見ると、nが偶数の時って、３の倍数になってない？

ということで、$ n \equiv 0 \pmod{2} $のとき、$ a_n \equiv 0 \pmod{3} $となるのではないかと考えられる。

ふゅか

じゃ。残りの奇数の部分も見てみよう！

$ n = 1 $: $ 157115 = 5 \times 7 \times 67^2 $
$ n = 3 $: $ 628457 = 73 \times 8609 $
$ n = 5 $: $ 2513825 = 5^2 \times 193 \times 521 $
$ n = 7 $: $ 10055297 = 7 \times 1436471 $
$ n = 9 $: $ 40221185 = 5 \times 59 \times 136343 $
$ n = 11 $: $ 160884737 = 13 \times 523 \times 23663 $
$ n = 13 $: $ 643538945 = 5 \times 7 \times 1759 \times 10453 $
$ n = 15 $: $ 2574155777 = 19 \times 135481883 $
$ n = 17 $: $ 10296623105 = 5 \times 2059324621 $
$ n = 19 $: $ 41186492417 = 7 \times 1583 \times 3716857 $
$ n = 21 $: $ 164745969665 = 5 \times 73 \times 451358821 $
$ n = 23 $: $ 658983878657 = 13 \times 811 \times 62504399 $
$ n = 25 $: $ 2635935514625 = 5^3 \times 7 \times 63337 \times 47563 $
$ n = 27 $: $ 10543742058497 = 37 \times 167 \times 42209 \times 40427 $
$ n = 29 $: $ 42174968233985 = 5 \times 75659 \times 111486983 $
$ n = 31 $: $ 168699872935937 = 7^2 \times 109 \times 31585821557 $
$ n = 33 $: $ 674799491743745 = 5 \times 19 \times 541301 \times 13122371 $
$ n = 35 $: $ 2699197966974977 = 13 \times 47 \times 93755653 \times 47119 $

ふゅか

んー。あれ、1、5、9、13・・・って５の倍数じゃん！ってことはnが4で割ったときに1余る場合、$a_n$が5で割り切れるかも！

はるか

さらに、$ n \equiv 1 \pmod{4} $以外を確認する。

$ n = 3 $: $ 628457 = 73 \times 8609 $
$ n = 7 $: $ 10055297 = 7 \times 1436471 $
$ n = 11 $: $ 160884737 = 13 \times 523 \times 23663 $
$ n = 15 $: $ 2574155777 = 19 \times 135481883 $
$ n = 19 $: $ 41186492417 = 7 \times 1583 \times 3716857 $
$ n = 23 $: $ 658983878657 = 13 \times 811 \times 62504399 $
$ n = 27 $: $ 10543742058497 = 37 \times 167 \times 42209 \times 40427 $
$ n = 31 $: $ 168699872935937 = 7^2 \times 109 \times 31585821557 $
$ n = 35 $: $ 2699197966974977 = 13 \times 47 \times 93755653 \times 47119 $

はるか

ここまでくると、規則性が見えてきたな。$n=7,19,31$は7で割り切れそう。nは12で割ったときに7余る。

ふゅか

そうね。$n=11,23 ,35 $は13で割り切れそうね。nは12で割ったときに11余るときね！

$ n = 3 $: $ 628457 = 73 \times 8609 $
$ n = 15 $: $ 2574155777 = 19 \times 135481883 $
$ n = 27 $: $ 10543742058497 = 37 \times 167 \times 42209 \times 40427 $

ふゅか

残りの3つは個別に見ていく必要がありそうね。39と51、63を見てみよう！

$ n = 39 $: $ 43187167471599617 = 71 \times 73 \times 211 \times 39490356709 $
$ n = 51 $: $ 176894637963672027137 = 19 \times 2083 \times 4469632310778281 $
$ n = 63 $: $ 724560437099200623149057 = 37 \times 33109276591 \times 591457033571 $

ふゅか

36で割ったとき3余る場合は73、15余る場合は19、27余る場合は37で割り切れそうね！

はるか

ということで、規則性の推測をまとめる。

規則性の推測

規則性の推測は次のようになる。

$ n \equiv 0 \ (\text{mod} \ 2) $ のとき、 $ a_n \equiv 0 \ (\text{mod} \ 3) $。
$ n \equiv 1 \ (\text{mod} \ 4) $ のとき、 $ a_n \equiv 0 \ (\text{mod} \ 5) $。
$ n \equiv 7 \ (\text{mod} \ 12) $ のとき、 $ a_n \equiv 0 \ (\text{mod} \ 7) $。
$ n \equiv 11 \ (\text{mod} \ 12) $ のとき、 $ a_n \equiv 0 \ (\text{mod} \ 13) $。
$ n \equiv 3 \ (\text{mod} \ 36) $ のとき、 $ a_n \equiv 0 \ (\text{mod} \ 73) $。
$ n \equiv 15 \ (\text{mod} \ 36) $ のとき、 $ a_n \equiv 0 \ (\text{mod} \ 19) $。
$ n \equiv 27 \ (\text{mod} \ 36) $ のとき、 $ a_n \equiv 0 \ (\text{mod} \ 37) $。

証明

はるか

さきほど、推測した７つの規則性が正しければ合成数であることを証明できる。

素数で割り切れることを示したいので、フェルマーの小定理を利用しています。フェルマーの小定理はpが素数、aとpが互いに素であるとき、次のような合同式成り立つことです。

$$a^{p-1}\equiv \pmod{p}$$

また、 $$2^{9} \equiv 1 \pmod{73}$$を利用します。

$ n \equiv 0 \pmod{2} $ の場合

$ n \equiv 0 \pmod{2} $ のとき、$n=2l$と置くと、$ 2^2 \equiv 1 \pmod{3} $ より、

\[ a_n \equiv 78557 \times 2^{2l} + 1 \pmod{3} \]

\[ a_n \equiv 2\times 1 + 1 \pmod{3} \]

\[ a_n \equiv 0 \pmod{3} \]

$ a_n $ は $ 3 $ の倍数であり、合成数であることがわかります。

$ n \equiv 1 \pmod{4} $ の場合

$ n \equiv 1 \pmod{4} $ のとき、$n=4l+1$と置くと、$ 2^4 \equiv 1 \pmod{5} $ より、

\[ a_n \equiv 78557 \times 2^{4l+1} + 1 \pmod{5} \]

\[ a_n \equiv 2\times (4)^{2l}\times 2 + 1 \pmod{5} \]

\[ a_n \equiv 2 \times 2 + 1 \pmod{5} \]

\[ a_n \equiv 0 \pmod{5} \]

したがって、$ a_n $ は $ 5 $ の倍数であり、合成数であることがわかります。

$ n \equiv 7 \pmod{12} $ の場合

$ n \equiv 7 \pmod{12} $ のとき、$n=12l+7$と置くと、$ 2^6 \equiv 1 \pmod{7} $ より、

\[ a_n \equiv 78557 \times 2^{12l+7} + 1 \pmod{7} \]

\[ a_n \equiv 3\times (2^6)^{2l+1}\times 2 + 1 \pmod{7} \]

\[ a_n \equiv 3 \times 2 + 1 \pmod{7} \]

\[ a_n \equiv 0 \pmod{7} \]

従って、$ a_n $ は $ 7 $ の倍数であり、合成数です。

$ n \equiv 11 \pmod{12} $ の場合

$ n \equiv 11 \pmod{12} $ のとき、$n=12l+11$と置くと、$ 2^{12} \equiv 1 \pmod{13} $ より、

\[ a_n \equiv 78557 \times 2^{12l+11} + 1 \pmod{13} \]

\[ a_n \equiv 11\times 2^{12l}\times 2^{11} + 1 \pmod{13} \]

\[ a_n \equiv 11 \times 7 + 1 \pmod{13} \]

\[ a_n \equiv 0 \pmod{13} \]

従って、$ a_n $ は $ 13 $ の倍数であり、合成数です。

$ n \equiv 3 \pmod{36} $ の場合

$ n \equiv 3\pmod{36} $ のとき、$n=36l+3$と置くと、$ 2^{9} \equiv 1 \pmod{73} $ より、

\[ a_n \equiv 78557 \times 2^{36l+3} + 1 \pmod{73} \]

\[ a_n \equiv 9\times (2^{9})^{4l}\times 2^3 + 1 \pmod{73} \]

\[ a_n \equiv 9\times 8+ 1 \pmod{73} \]

\[ a_n \equiv 0 \pmod{73} \]

従って、$ a_n $ は $ 73 $ の倍数であり、合成数です。

$ n \equiv 15 \pmod{36} $ の場合

$ n \equiv 3\pmod{36} $ のとき、$n=36l+15$と置くと、$ 2^{18} \equiv 1 \pmod{19 } $ より、

\[ a_n \equiv 78557 \times 2^{36l+15} + 1 \pmod{19 } \]

\[ a_n \equiv 11\times (2^{9})^{4l}\times 2^15 + 1 \pmod{19 } \]

\[ a_n \equiv 11\times 12+ 1 \pmod{19 } \]

\[ a_n \equiv 0 \pmod{19 } \]

従って、$ a_n $ は $ 19 $ の倍数であり、合成数です。

$ n \equiv 27 \pmod{36} $ の場合

$ n \equiv 3\pmod{36} $ のとき、$n=36l+27$と置くと、$ 2^{36} \equiv 1 \pmod{37 } $ より、

\[ a_n \equiv 78557 \times 2^{36l+3} + 1 \pmod{37 } \]

\[ a_n \equiv 6\times (2^{36}\times 2^{27} + 1 \pmod{37 } \]

\[ a_n \equiv 6\times 6+ 1 \pmod{37 } \]

\[ a_n \equiv 0 \pmod{37 } \]

従って、$ a_n $ は $ 37 $ の倍数であり、合成数です。

これらの証明により、すべての $ n $ に対して $ a_n = 78557 \times 2^n + 1 $ が合成数であることが示されました。

メルセンヌ数とメルセンヌ素数とは？2ⁿ-1の性質や完全数との関連を解説！

特殊な数

三角数の定義・三角数の定理・具体例・漸化式について

特殊な数

ハーシャッド数とは何か？基本から詳しく解説してpythonでチェック

特殊な数

完全数pq、p²qを背景にした不定方程式

発展特殊な数

完全数とは？約数の和が作り出す特別な数の性質について解説！

発展特殊な数

フェルマーの小定理と巡回数ー 142857の仕組みと性質について

特殊な数

ホームに戻る

シェルピンスキー数と78557・合成数・証明について

シェルピンスキー数とは

シェルピンスキー数の具体例

使用したプログラム

合成数であることの証明

証明の前の準備

規則性の推測

証明

\( n \equiv 0 \pmod{2} \) の場合

\( n \equiv 1 \pmod{4} \) の場合

\( n \equiv 7 \pmod{12} \) の場合

\( n \equiv 11 \pmod{12} \) の場合

\( n \equiv 3 \pmod{36} \) の場合

\( n \equiv 15 \pmod{36} \) の場合

\( n \equiv 27 \pmod{36} \) の場合

関連記事