「東大」「才能」「全教科」ver2.0
>>38 あまり自信なく・・
以下、次をみたす自然数nについて考える。
2^n+1≡0 mod n
このとき、nは奇数である。
定義
[ I ]
自然数aとbが次をみたすとき、a*→bと表す。
2^a+1≡0 mod p をみたす素数p、またはp=1に対して、b=ap
[ II ]
自然数aとbが次をみたすとき、a→bと表す。
自然数列c(1), c(2),..,c(K)が存在して、
c(1)=a, c(K)=b, k=1,2,..,K-1に対してc(k)*→c(k+1)
とくに、a→aと、a→b，b→cならばa→c、が成り立つ。
定理
自然数nに対して、つぎの[A],[B]は同値である。
[A] 1→n
[B] 2^n+1≡0 mod n
以下、次をみたす自然数nについて考える。
2^n+1≡0 mod n
このとき、nは奇数である。
定義
[ I ]
自然数aとbが次をみたすとき、a*→bと表す。
2^a+1≡0 mod p をみたす素数p、またはp=1に対して、b=ap
[ II ]
自然数aとbが次をみたすとき、a→bと表す。
自然数列c(1), c(2),..,c(K)が存在して、
c(1)=a, c(K)=b, k=1,2,..,K-1に対してc(k)*→c(k+1)
とくに、a→aと、a→b，b→cならばa→c、が成り立つ。
定理
自然数nに対して、つぎの[A],[B]は同値である。
[A] 1→n
[B] 2^n+1≡0 mod n
|
|
|
以下、定理の証明の準備。
命題１
自然数m,nが、2^m+1 mod m かつ m→n をみたすなら、
2^n+1 mod n
命題１の証明
pを奇素数として、m*→n=mp ; 2^m+1≡0 mod p の場合について示せばよい。
f(a)=2^a+1とおく。
f(mp)={f(m)-1}^p+1=∑/k=1..p/C[p,k]*{f(m)^k}*{(-1)^(p-k)}
=f(m)∑/k=1..p/C[p,k]*{f(m)^(k-1)}*{(-1)^(p-k)}
=f(m)[ p+f(m)∑/k=2..p/C[p,k]*{f(m)^(k-2)}*{(-1)^(p-k)}]
f(m)≡0 mod p であるので、[ p+f(m)∑/k=2..p/C[p,k]*{f(m)^(k-2)}*{(-1)^(p-k)}]/p
自然数になる。したがって、これをg(m,p)とおくと、f(mp)=pf(m)g(m,p)≡0 mod mp []
なお、g(m,p)=1+f(m)[(p-1)/2+{f(m)/p}∑/k=3..p/C[p,k]*{f(m)^(k-3)}*{(-1)^(p-k)}]
であるので、f(m)とg(m,p)は互いに素。したがって、>>240の答えはyes.
定理[A] ⇒[B]の証明
2^1+1≡0 mod 1 であるから、命題１により成立。
命題１
自然数m,nが、2^m+1 mod m かつ m→n をみたすなら、
2^n+1 mod n
命題１の証明
pを奇素数として、m*→n=mp ; 2^m+1≡0 mod p の場合について示せばよい。
f(a)=2^a+1とおく。
f(mp)={f(m)-1}^p+1=∑/k=1..p/C[p,k]*{f(m)^k}*{(-1)^(p-k)}
=f(m)∑/k=1..p/C[p,k]*{f(m)^(k-1)}*{(-1)^(p-k)}
=f(m)[ p+f(m)∑/k=2..p/C[p,k]*{f(m)^(k-2)}*{(-1)^(p-k)}]
f(m)≡0 mod p であるので、[ p+f(m)∑/k=2..p/C[p,k]*{f(m)^(k-2)}*{(-1)^(p-k)}]/p
自然数になる。したがって、これをg(m,p)とおくと、f(mp)=pf(m)g(m,p)≡0 mod mp []
なお、g(m,p)=1+f(m)[(p-1)/2+{f(m)/p}∑/k=3..p/C[p,k]*{f(m)^(k-3)}*{(-1)^(p-k)}]
であるので、f(m)とg(m,p)は互いに素。したがって、>>240の答えはyes.
定理[A] ⇒[B]の証明
2^1+1≡0 mod 1 であるから、命題１により成立。
補題
（１）
mを自然数とする。2^a≡1 mod m をみたす自然数aのなかで最小のものをnとおく。
このとき、自然数Nに関して次の[A], [B]は同値。
[A] nはNの約数。
[B] 2^N≡1 mod m
（２）
a,b,nを自然数、pを素数とすると、
(a+b)^(p^n)≡a^(p^n)+b^(p^n) mod p
補題の証明
（１）
[A]⇒[B]
N=nbとすると2^N=2^(nb)=(2^n)^b≡1^b=1 mod m
[B]⇒[A]
N=bn+c, (0≦c≦n-1) とおくと、
2^N=2^(bn+c)≡1 mod m
{2^(bn)}(2^c)≡1 mod m
2^c≡1 mod m
であるから、nの最小性により、c=0 []
（２）
nに関する帰納法。
( i ) n=0のときは成立。
( ii ) n=kのとき成立を仮定する。n=k+1のとき
二項係数C[p,k]=p(p-1)...(p-k+1)/k(k-1)...1は分子のpが約分されないので、
k=1,..,p-1にたいして、C[p,k]≡0 mod p
帰納法の仮定により(a+b)^(p^(k+1))={(a+b)^(p^k)}^k≡{a^(p^k)+b^(p^k)}^p mod p
=∑C[p,i]{a^(p^k)}^i{b^(p^k)}^(p-i)≡a^(p^(k+1))+b^(p^(k+1)) mod p
従って成立。 []
（１）
mを自然数とする。2^a≡1 mod m をみたす自然数aのなかで最小のものをnとおく。
このとき、自然数Nに関して次の[A], [B]は同値。
[A] nはNの約数。
[B] 2^N≡1 mod m
（２）
a,b,nを自然数、pを素数とすると、
(a+b)^(p^n)≡a^(p^n)+b^(p^n) mod p
補題の証明
（１）
[A]⇒[B]
N=nbとすると2^N=2^(nb)=(2^n)^b≡1^b=1 mod m
[B]⇒[A]
N=bn+c, (0≦c≦n-1) とおくと、
2^N=2^(bn+c)≡1 mod m
{2^(bn)}(2^c)≡1 mod m
2^c≡1 mod m
であるから、nの最小性により、c=0 []
（２）
nに関する帰納法。
( i ) n=0のときは成立。
( ii ) n=kのとき成立を仮定する。n=k+1のとき
二項係数C[p,k]=p(p-1)...(p-k+1)/k(k-1)...1は分子のpが約分されないので、
k=1,..,p-1にたいして、C[p,k]≡0 mod p
帰納法の仮定により(a+b)^(p^(k+1))={(a+b)^(p^k)}^k≡{a^(p^k)+b^(p^k)}^p mod p
=∑C[p,i]{a^(p^k)}^i{b^(p^k)}^(p-i)≡a^(p^(k+1))+b^(p^(k+1)) mod p
従って成立。 []
命題２
e,mを自然数、pをmのどの素因数よりも大きな素数とする。
2^(mp^e)+1≡0 mod mp^e が成り立つとき、つぎの（１）、（２）が成立する。
（１）2^m+1≡0 mod m
（２）m→mp^e かつ 2^m(p^k)+1 mod m ; k=1,2,..,e
命題２（１）の証明
2^(mp^e)+1≡0 mod mp^e であるので、
2^(mp^e)+1≡0 mod m
2^(mp^e)≡-1 mod m ...(*)
2^(2mp^e)≡1 mod m ...(**)
ここで、2^a≡1 mod m みたすaのなかで最小のものをnとおく。
2^n ≡1 mod m
補題（１）と(*), (**)により、nは2mp^eの約数であるが、mp^eの約数ではない。
したがって、nは2を素因数にもつ。
pがnの約数であると仮定する。オイラーの定理により、2^φ(m)≡1 mod m であるので、
補題（１）により、pはφ(m)の素因数である。ところが、φ(m)の素因数は全てmの素因数以下であるから、
pの最大性に反する。したがって、nはpを素因数にもたない。
n=2μ, m=μα（μ、αは自然数）とおく。
2^(2m)=2^(2μα)≡1 mod m であるから
(2^m-1)(2^m+1)≡0 mod m となり、
mの素因数は、2^m-1、2^m+1のどちらかを割り切る。
mのある素因数qが2^m-1を割り切る、と仮定する。
2^m≡1 mod m なので、2^(mp^e)≡1 mod q
一方、(*)により2^(mp^e)≡-1 mod q であるので、
2≡0 mod q, q=2となり矛盾。
したがって、mの素因数はすべて2^m+1を割り切るので、2^m+1≡0 mod m []
e,mを自然数、pをmのどの素因数よりも大きな素数とする。
2^(mp^e)+1≡0 mod mp^e が成り立つとき、つぎの（１）、（２）が成立する。
（１）2^m+1≡0 mod m
（２）m→mp^e かつ 2^m(p^k)+1 mod m ; k=1,2,..,e
命題２（１）の証明
2^(mp^e)+1≡0 mod mp^e であるので、
2^(mp^e)+1≡0 mod m
2^(mp^e)≡-1 mod m ...(*)
2^(2mp^e)≡1 mod m ...(**)
ここで、2^a≡1 mod m みたすaのなかで最小のものをnとおく。
2^n ≡1 mod m
補題（１）と(*), (**)により、nは2mp^eの約数であるが、mp^eの約数ではない。
したがって、nは2を素因数にもつ。
pがnの約数であると仮定する。オイラーの定理により、2^φ(m)≡1 mod m であるので、
補題（１）により、pはφ(m)の素因数である。ところが、φ(m)の素因数は全てmの素因数以下であるから、
pの最大性に反する。したがって、nはpを素因数にもたない。
n=2μ, m=μα（μ、αは自然数）とおく。
2^(2m)=2^(2μα)≡1 mod m であるから
(2^m-1)(2^m+1)≡0 mod m となり、
mの素因数は、2^m-1、2^m+1のどちらかを割り切る。
mのある素因数qが2^m-1を割り切る、と仮定する。
2^m≡1 mod m なので、2^(mp^e)≡1 mod q
一方、(*)により2^(mp^e)≡-1 mod q であるので、
2≡0 mod q, q=2となり矛盾。
したがって、mの素因数はすべて2^m+1を割り切るので、2^m+1≡0 mod m []
366 ：ヘタレかかろと：03/09/01 01:14 ID:ZxZ6LbV3
連投するとアク禁食らうよ。回避
命題２（２）の証明
kに関する帰納法で、次の命題を証明する。
k=0,1,..,e-1に対して、mp^k*→mp^(k+1), 2^(mp^k)+1≡0 mod mp^k
(i) k=0 のとき
補題（２）より、(2^m+1)^(p^e)≡2^(m(p^e))+1≡0 mod p
したがって、2^m+1≡0 mod pであるから、m→mp
また、命題２（１）により2^m+1≡0 mod m
(ii) k=j についての成立を仮定する。k=j+1 のとき、
帰納法の仮定から、2^(mp^j)+1≡0 mod mp^j、mp^j→mp^(j+1)であるから、
命題１により、2^mp^(j+1)+1 mod mp^(j+1),
さらに、2^mp^(j+1)+1 mod p であるから、mp^(j+1)→mp^(j+2) []
定理[B]⇒[A]の証明。
nの相異なる素因数の数をNとし、Nに関する帰納法で証明する。
(i) N=0のとき、n=1であるので、成立。
(ii) N=kのときの成立を仮定する。
nの素因数の中で最大のものをpとする。n=mp^e （pはmのどの素因数よりも大きい）としたとき、
命題２（１）により、2^m+1 mod mであるので、帰納法の仮定により、1→m.
また、命題２（２）によりm→n であるから、1→n []
kに関する帰納法で、次の命題を証明する。
k=0,1,..,e-1に対して、mp^k*→mp^(k+1), 2^(mp^k)+1≡0 mod mp^k
(i) k=0 のとき
補題（２）より、(2^m+1)^(p^e)≡2^(m(p^e))+1≡0 mod p
したがって、2^m+1≡0 mod pであるから、m→mp
また、命題２（１）により2^m+1≡0 mod m
(ii) k=j についての成立を仮定する。k=j+1 のとき、
帰納法の仮定から、2^(mp^j)+1≡0 mod mp^j、mp^j→mp^(j+1)であるから、
命題１により、2^mp^(j+1)+1 mod mp^(j+1),
さらに、2^mp^(j+1)+1 mod p であるから、mp^(j+1)→mp^(j+2) []
定理[B]⇒[A]の証明。
nの相異なる素因数の数をNとし、Nに関する帰納法で証明する。
(i) N=0のとき、n=1であるので、成立。
(ii) N=kのときの成立を仮定する。
nの素因数の中で最大のものをpとする。n=mp^e （pはmのどの素因数よりも大きい）としたとき、
命題２（１）により、2^m+1 mod mであるので、帰納法の仮定により、1→m.
また、命題２（２）によりm→n であるから、1→n []