マスジョイ
PR
整数
python 特殊な数
更新:2024/09/27

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

はるか
はるか
シェルピンスキー数って面白い。
ふゅか
ふゅか
そうね。すべてのnに対して合成数であることがわかっているのってなかなか特徴的だよね！
目次

1. シェルピンスキー数とは

自然数 \( k \) がシェルピンスキー数であるとは、全ての自然数 \( n \) に対して、\( k \times 2^n + 1 \) が合成数（素数ではない）である。

この概念は、ポーランドの数学者ワツワフ・シェルピンスキーによって提案されました。

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

シェルピンスキー数の具体例として、\( k = 78557 \) が知られています。これは、全ての \( n \) に対して \( 78557 \times 2^n + 1 \) が合成数であることが証明されています。

ふゅか
ふゅか
n=1から10まで実際に合成数であることを確認してみよう！
はるか
はるか
計算だるいから、プログラムで解く。

\( 78557 \times 2^n + 1 \) の \( n = 1 \) から \( 10 \) までの結果とその素因数分解は次のようになります。

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. \( 157115 = 5 \times 7 \times 67^2 \)0の場合: \( 157115 = 5 \times 7 \times 67^2 \)1
7. \( 157115 = 5 \times 7 \times 67^2 \)2の場合: \( 157115 = 5 \times 7 \times 67^2 \)3
8. \( 157115 = 5 \times 7 \times 67^2 \)4の場合: \( 157115 = 5 \times 7 \times 67^2 \)5
9. \( 157115 = 5 \times 7 \times 67^2 \)6の場合: \( 157115 = 5 \times 7 \times 67^2 \)7
10. \( 157115 = 5 \times 7 \times 67^2 \)8の場合: \( 157115 = 5 \times 7 \times 67^2 \)9

1.2. 使用したプログラム

はるか
はるか
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))

2. 合成数であることの証明

2.1. 証明の前の準備

はるか
はるか
まぁ、証明の準備の前に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. \( 157115 = 5 \times 7 \times 67^2 \)0: \( 157115 = 5 \times 7 \times 67^2 \)1
7. \( 157115 = 5 \times 7 \times 67^2 \)2: \( 157115 = 5 \times 7 \times 67^2 \)3
8. \( 157115 = 5 \times 7 \times 67^2 \)4: \( 157115 = 5 \times 7 \times 67^2 \)5
9. \( 157115 = 5 \times 7 \times 67^2 \)6: \( 157115 = 5 \times 7 \times 67^2 \)7
10. \( 157115 = 5 \times 7 \times 67^2 \)8: \( 157115 = 5 \times 7 \times 67^2 \)9
11. \( n = 2 \)0: \( n = 2 \)1
12. \( n = 2 \)2: \( n = 2 \)3
13. \( n = 2 \)4: \( n = 2 \)5
14. \( n = 2 \)6: \( n = 2 \)7
15. \( n = 2 \)8: \( n = 2 \)9
16. \( 314229 = 3 \times 104743 \)0: \( 314229 = 3 \times 104743 \)1
17. \( 314229 = 3 \times 104743 \)2: \( 314229 = 3 \times 104743 \)3
18. \( 314229 = 3 \times 104743 \)4: \( 314229 = 3 \times 104743 \)5
19. \( 314229 = 3 \times 104743 \)6: \( 314229 = 3 \times 104743 \)7
20. \( 314229 = 3 \times 104743 \)8: \( 314229 = 3 \times 104743 \)9
21. \( n = 3 \)0: \( n = 3 \)1
22. \( n = 3 \)2: \( n = 3 \)3
23. \( n = 3 \)4: \( n = 3 \)5
24. \( n = 3 \)6: \( n = 3 \)7
25. \( n = 3 \)8: \( n = 3 \)9
26. \( 628457 = 73 \times 8609 \)0: \( 628457 = 73 \times 8609 \)1
27. \( 628457 = 73 \times 8609 \)2: \( 628457 = 73 \times 8609 \)3
28. \( 628457 = 73 \times 8609 \)4: \( 628457 = 73 \times 8609 \)5
29. \( 628457 = 73 \times 8609 \)6: \( 628457 = 73 \times 8609 \)7
30. \( 628457 = 73 \times 8609 \)8: \( 628457 = 73 \times 8609 \)9
31. \( n = 4 \)0: \( n = 4 \)1
32. \( n = 4 \)2: \( n = 4 \)3
33. \( n = 4 \)4: \( n = 4 \)5
34. \( n = 4 \)6: \( n = 4 \)7
35. \( n = 4 \)8: \( n = 4 \)9
36. \( 1256913 = 3^2 \times 7 \times 71 \times 281 \)0: \( 1256913 = 3^2 \times 7 \times 71 \times 281 \)1

はるか
はるか
んー。よく見ると、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 \)
\( 157115 = 5 \times 7 \times 67^2 \)0: \( 157115 = 5 \times 7 \times 67^2 \)1
\( 157115 = 5 \times 7 \times 67^2 \)2: \( 157115 = 5 \times 7 \times 67^2 \)3
\( 157115 = 5 \times 7 \times 67^2 \)4: \( 157115 = 5 \times 7 \times 67^2 \)5
\( 157115 = 5 \times 7 \times 67^2 \)6: \( 157115 = 5 \times 7 \times 67^2 \)7
\( 157115 = 5 \times 7 \times 67^2 \)8: \( 157115 = 5 \times 7 \times 67^2 \)9
\( n = 3 \)0: \( n = 3 \)1
\( n = 3 \)2: \( n = 3 \)3
\( n = 3 \)4: \( n = 3 \)5
\( n = 3 \)6: \( n = 3 \)7
\( n = 3 \)8: \( n = 3 \)9
\( 628457 = 73 \times 8609 \)0: \( 628457 = 73 \times 8609 \)1
\( 628457 = 73 \times 8609 \)2: \( 628457 = 73 \times 8609 \)3
\( 628457 = 73 \times 8609 \)4: \( 628457 = 73 \times 8609 \)5

ふゅか
ふゅか
んー。あれ、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 \)
\( 628457 = 73 \times 8609 \)0: \( 628457 = 73 \times 8609 \)1
\( 628457 = 73 \times 8609 \)2: \( 628457 = 73 \times 8609 \)3
\( 628457 = 73 \times 8609 \)4: \( 628457 = 73 \times 8609 \)5
\( 628457 = 73 \times 8609 \)6: \( 628457 = 73 \times 8609 \)7

はるか
はるか
ここまでくると、規則性が見えてきたな。$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で割り切れそうね！
はるか
はるか
ということで、規則性の推測をまとめる。

2.2. 規則性の推測

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

\( 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) \)。
\( a_n \equiv 0 \ (\text{mod} \ 3)0 \) のとき、 \( a_n \equiv 0 \ (\text{mod} \ 3)1 \)。
\( a_n \equiv 0 \ (\text{mod} \ 3)2 \) のとき、 \( a_n \equiv 0 \ (\text{mod} \ 3)3 \)。

2.3. 証明

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

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

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

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

2.3.1. \( 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 \) の倍数であり、合成数であることがわかります。

2.3.2. \( 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 \) の倍数であり、合成数であることがわかります。

2.3.3. \( 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 \) の倍数であり、合成数です。

2.3.4.  \( 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 \) の倍数であり、合成数です。

2.3.5. \( 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 \) の倍数であり、合成数です。

2.3.6. \( 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 \) の倍数であり、合成数です。

2.3.7. \( 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 \) が合成数であることが示されました。

PR
ホームに戻る