Integer n such that n|(2^n+1)
[2006.02.18]n|(2^n+1)となる正整数n
■2006年2月12日の朝日新聞朝刊の天声人語で紹介された数学五輪の問題を解いてみる。
問題１：(2n+1)がnで割り切れ、相異なる2000個の素因数を持つ整数nは存在するか？
■定義
正整数nの相異なる素因数の数をω(n)とする。
■1000000以下の正整数nで、n|(2n+1)を満たすものは、以下のように39個あることが確認できる。
[pari/gpによる計算]
gp> read("cn.gp")
time = 7 ms.
gp> find(1000000)
1:[3, [Mat([3, 1])]]
2:[9, [Mat([3, 2])]]
3:[27, [Mat([3, 3])]]
4:[81, [Mat([3, 4])]]
5:[171, [[3, 2; 19, 1]]]
6:[243, [Mat([3, 5])]]
7:[513, [[3, 3; 19, 1]]]
8:[729, [Mat([3, 6])]]
9:[1539, [[3, 4; 19, 1]]]
10:[2187, [Mat([3, 7])]]
11:[3249, [[3, 2; 19, 2]]]
12:[4617, [[3, 5; 19, 1]]]
13:[6561, [Mat([3, 8])]]
14:[9747, [[3, 3; 19, 2]]]
15:[13203, [[3, 4; 163, 1]]]
16:[13851, [[3, 6; 19, 1]]]
17:[19683, [Mat([3, 9])]]
18:[29241, [[3, 4; 19, 2]]]
19:[39609, [[3, 5; 163, 1]]]
20:[41553, [[3, 7; 19, 1]]]
21:[59049, [Mat([3, 10])]]
22:[61731, [[3, 2; 19, 3]]]
23:[87723, [[3, 5; 19, 2]]]
24:[97641, [[3, 2; 19, 1; 571, 1]]]
25:[118827, [[3, 6; 163, 1]]]
26:[124659, [[3, 8; 19, 1]]]
27:[177147, [Mat([3, 11])]]
28:[185193, [[3, 3; 19, 3]]]
29:[250857, [[3, 4; 19, 1; 163, 1]]]
30:[263169, [[3, 6; 19, 2]]]
31:[292923, [[3, 3; 19, 1; 571, 1]]]
32:[354537, [[3, 5; 1459, 1]]]
33:[356481, [[3, 7; 163, 1]]]
34:[373977, [[3, 9; 19, 1]]]
35:[531441, [Mat([3, 12])]]
36:[555579, [[3, 4; 19, 3]]]
37:[752571, [[3, 5; 19, 1; 163, 1]]]
38:[789507, [[3, 7; 19, 2]]]
39:[878769, [[3, 4; 19, 1; 571, 1]]]
これより、以下の事実が分かる。
- n|(2n+1),ω(n)=1を満たす最小のnは、3である。
- n|(2n+1),ω(n)=2を満たす最小のnは、171=32・19である。
- n|(2n+1),ω(n)=3を満たす最小のnは、97641=32・19・571である。
ここに現れたnの素因数で、3,19,163,1459は、いずれも、"ある正整数mに対して、(23m+1)の素因数である"(*)ことが分かる。
ただし、素因数571については、簡単な特徴付けはできていない。
素数571は、23m+1の素因数にはならないことが確認できるので、条件(*)はnの素因数の一部しか特徴付けていないことに注意する。
[pari/gpによる計算]
gp> for(i=1,5,print([i,nn(i),factor([nn(i)])]))
[1, 9, [Mat([3, 2])]]
[2, 513, [[3, 3; 19, 1]]]
[3, 134217729, [[3, 4; 19, 1; 87211, 1]]]
[4, 2417851639229258349412353, [[3, 5; 19, 1; 163, 1; 87211, 1; 135433, 1; 272010961, 1]]]
[5, 14134776518227074636666380005943348126619871175004951664972849610340958209, [[3, 6; 19, 1; 163, 1; 1459, 1; 87211, 1; 135433, 1; 139483, 1; 272010961, 1; 10429407431911334611, 1; 918125051602568899753, 1]]]
time = 2,751 ms.
以下では、n=(23m+1)がn|(2n+1)を満たすことを示す。
■Nm=23m+1 (m >= 0)とする。
整数列{Nm}は以下の性質を満たす。
- (1) Nmは奇数である。
- (2) Nm | Nm+1
- (3) ord3(Nm+1/Nm) = 1
- (4) 0 <= m < k ならば、Nm | Nk
- (5) ord3(Nm) = m+1
- (6) Nm+1 | (2Nm+1)
- (7) Nm | (2Nm+1)
[証明]
(1) 23mは偶数なので、Nm=23m+1は奇数である。
(2) (Nm+1/Nm) = ((23m)3+1)/(23m+1) = (22・3m-23m+1)は整数なので、Nm|Nm+1である。
(3) (Nm+1/Nm) = (22・3m-23m+1)≡(-1)2・3m-(-1)3m+1≡(-1)2-(-1)+1≡3≡0 (mod 3)より、3 | (Nm+1/Nm)を得る。
同様に、23≡8≡-1 (mod 32)より、
m >= 0に対して、23(m+1)≡23・3m≡(23)3m≡(-1)3m≡-1 (mod 32)となる。
m > 0に関する数学的帰納法によって、
23m≡-1 (mod 32)
を得る。これより、
(Nm+1/Nm) = (22・3m-23m+1)≡(-1)2-(-1)+1≡3≠0 (mod 32)
(ただし、a≠bは¬(a≡b)を意味する)となる。
よって、3||(Nm+1/Nm)、つまり、ord3(Nm+1/Nm)=1を得る。
(4) (2)より、容易に得られる。
(5) (3)より、
ord3(Nm+1) = ord3(Nm・(Nm+1/Nm)) = ord3(Nm)+ord3(Nm+1/Nm) = ord3(Nm)+1,
を得る。また、
ord3(N0) = ord3(21+1) = ord3(3) = 1
である。よって、ord3(Nm+1) = m+1を得る。
(6)m >=0 に対して、3(m+1),Nmはどちらも奇数であり、かつ、3(m+1) | Nmなので、
Nm+1=(23(m+1)+1) | (2Nm+1)を得る。
(7) (2),(6)より、容易に得られる。
■m >= 2とする。Nmは、3以外に少なくとも(m-1)個の相異なる素因数を持つ。
つまり、ω(Nm) >= mである。
[証明]
P(m): ω(Nm) >= mとする。
m=2のとき、N2=232+1 = 29+1 = 513 = 33・19は、2個の相異なる素因数3,19を持つので、P(2)が成立する。
P(m)が成立すると仮定する。
Nm+1=Nm・(Nm+1/Nm)
である。
X=23mとおくと、
Nm=X+1,
(Nm+1/Nm)=X2-X+1,
32 | Nm,
3 | (Nm+1/Nm)
より、
gcd(Nm,(Nm+1/Nm)) = gcd(X+1,X2-X+1) = gcd(X+1,(X+1)(X-2)+3) = gcd(X+1,3) = 3
となる。
3 < (Nm+1/Nm)、かつ、3 || (Nm+1/Nm)
であるので、(Nm+1/Nm)は3以外の素因数pを(少なくとも１個)持つ。
gcd(Nm,(Nm+1/Nm)) = 3より、pとNmは互いに素である。
よって、(Nm+1/Nm)は、Nmに現れない素因数を少なくとも１個持つ。
従って、ω(Nm+1) >= (m+1)、つまり、P(m+1)が成立する。
数学的帰納法により、ω(Nm) >= m (m >= 2)を得る。
■N'=3m+1K, K | (Nm/3m+1)とする。
このとき、
N' | (2N'+1)
である。
[証明]
3m+1,N'はいずれも奇数であり、3m+1 | N'なので、
Nm+1=(23m+1+1) | (2N'+1)
である。
また、N' | Nm | Nm+1より、
N' | (2N'+1)
を得る。
■定理
n|(2n+1)かつω(n)=2000を満たす正整数nは存在する。
[証明]
N2000=232000+1を素因数分解して、
N2000=32001Πi=1M{piνi}
とする。
ここで、M = ω(N2000)-1 >= 1999, νi > 0, pi > 3, 各piは互いに異なる素数である。
これに対して、
N'=32001Πi=11999{pi}
とすると、
N'|(2N'+1)、かつ、ω(N')=2000
となる。
[注意]
N'を具体的に求めるには、N2000を素因数分解して、2000個以上の素因数を求める必要がある。
これはアルゴリズム的には計算可能であるが、実用的な時間で求めるのは難しい。
[2006.03.11追記]
素数571について、Nm=23m+1の素因数にはならない、つまり、
¬(571 | Nm) (ただし、m >= 0)
であることが証明できる。
[証明]
m=0,...,19に対して、
Nm=23m+1≠0 (mod 571)
であることは簡単に確認できる。
また、
2319≡231≡8 (mod 571)
より、任意のm >=0 に対して、
Nm+19-Nm+1=23m+19-23m+1=(2319)3m-(231)3m≡83m-83m≡0 (mod 571)
つまり、
Nm+19≡Nm+1 (mod 571)
となる。
従って、m >= 19に対して、数列{Nm mod 571}は、(N1 mod 571),...,(N18 mod 571)の繰り返しとなるので、
Nm≠0 (mod 571)
となる。
[pari/gpによる計算]
gp> for(i=0,19,print("N_{",i,"} mod 571=",f(3^i,571)))
N_{0} mod 571=Mod(3, 571)
N_{1} mod 571=Mod(9, 571)
N_{2} mod 571=Mod(513, 571)
N_{3} mod 571=Mod(182, 571)
N_{4} mod 571=Mod(478, 571)
N_{5} mod 571=Mod(222, 571)
N_{6} mod 571=Mod(249, 571)
N_{7} mod 571=Mod(441, 571)
N_{8} mod 571=Mod(508, 571)
N_{9} mod 571=Mod(517, 571)
N_{10} mod 571=Mod(358, 571)
N_{11} mod 571=Mod(301, 571)
N_{12} mod 571=Mod(266, 571)
N_{13} mod 571=Mod(165, 571)
N_{14} mod 571=Mod(541, 571)
N_{15} mod 571=Mod(473, 571)
N_{16} mod 571=Mod(402, 571)
N_{17} mod 571=Mod(456, 571)
N_{18} mod 571=Mod(219, 571)
N_{19} mod 571=Mod(9, 571)
time = 78 ms.
[参考文献]
- [1]G.H.Hardy, E.M.Wright, "An Introduction to the Theory of Numbers 5th edition", Oxford University Press, p238-239, 1979, ISBN0-19-853171-0.
- [2]山口 周, "整数論 美しき円分体論・ベルヌーイ数への旅路", 産業図書, p162-163, 1994, ISBN4-7828-9013-3, {5871円}.
| Last Update: 2006.03.11 |
| H.Nakao |