『割り切れる？ Part6』解答

◆愛知県の高校生　Sparking　さんからの解答。

【問題１】

２^ｎ＋１が奇数であること、つまり２の倍数の倍数にはなれないことから明らか。

【問題２】

数学的帰納法を用いて示す。

ｅ＝０のとき…自明。

ｅ＝ｅ’のとき題意が成り立つとすると
（ｅ’≧０）

２^{（３のe’乗）}≡−１＋３^e’+1（mod　３^e’+2）

∴ある整数ｍを用いて、

　２^{（３のe’乗）}
＝−１＋３^e’+1＋ｍ・３^e’+2
＝−１＋３^e’+1（１＋３ｍ）　と表される。

両辺を３乗して、

　２（３の3’乗）×3
＝−１＋３・３e’+1（１＋３ｍ）−３・｛３・３e’+1（１＋３ｍ）｝2＋｛３e’+1（１＋３ｍ）｝3
＝−１＋３e’+2＋３e’+3・（ｍ＋…−…＋…）
≡−１＋３e’+2　（mod　３e’+3）

２（３の（e’+1）乗）≡−１＋３（e’+1）＋１（mod　３e’+3）

【問題３】

背理法で示す

“ｍがｎの倍数であるとき、ｍはすべてのｎの約数の倍数である”（定理１）は自明。

いま、ｎが９の倍数であるとき、
ａ，ｂ（ａ，ｂ∈Ζ但しａ≧２，ｂは３と互いに素）を用いて、

ｎ＝ｂ・３^a　とあらわせる。

このとき、

ｎ²＝３^a+2・３^a-2ｂ²より、
３^a+2はｎ²の約数。

いま、

　２ⁿ
＝２^{（３のa乗）b}
（問題２より）
≡（−１＋３^a+1）^b　（mod　３^a+2）

ｂが奇数であること（∵問題１よりｎは奇数）に気をつけ，二項展開して整理すると、

≡−１＋ｂ・３a+1＋３a+2・（−bＣ2・３a＋…−…＋…）

≡−１＋ｂ・３a+1　（mod　３a+2）

∴　２n＋１≡ｂ・３a+1　（mod　３a+2）

よって左辺：２ⁿ＋１も３^a+2で割り切れない。

∴定理１から　２ⁿ＋１はｎ²で割り切れない。
背理法から、題意は示された。

【問題４】

（１）ａ^m≡１（mod　ｐ）　⇒　ｍはｋの倍数

背理法で示す。

いまａ^m≡１（mod　ｐ）をみたすｍが、

ｍ＝ｃｋ＋ｄ（０＜ｄ＜ｋ、ｃ，ｄ∈Ζ）と書けたとする。（仮定）

すると

　ａ^m≡１（mod　ｐ）
⇔（ａ^k）^c・ａ^d≡１　（mod　ｐ）
⇔１^c・ａ^d≡１　（mod　ｐ）
⇔ａ^d≡１　（mod　ｐ）

ところで、０＜ｄ＜ｋより、これはｋの定義に反し不合理。
よって仮定は誤り。よってｍはｋの倍数。

（２）ｍはｋの倍数　⇒　ａ^m≡１　（mod　ｐ）

ｍ＝ｆｋとすると、

　ａ^m
＝（ａ^k）^f
≡（１）^f　（mod　ｐ）
≡１（mod　ｐ）

よって示された。

∴ａ^m≡１（mod　ｐ）⇔ｍはｋの倍数　は成立する。

【問題５】

（１）ｋが２ｍの約数であることを示す。

　２n＋１≡０　（mod　ｎ）
⇒２n＋１≡０　（mod　ｐ）（定理１）
⇒２pm≡−１　（mod　ｐ）
⇒（２(p-1)）m・２m≡−１　（mod　ｐ）
⇒（１）・２m≡−１　（mod　ｐ）　（フェルマーの定理）
（両辺２乗）
⇒２2m≡１（mod　ｐ）

（２）ｋがｐ−１の約数であることを示す。

フェルマーの定理より
　２^(p-1)≡１（mod　ｐ）

ところで問題４の右矢印から　ｐ−１はｋの倍数、
言い換えるとｋはｐ−１の約数であることがいえる。

よってｋは、２ｍとｐ−１の公約数である。

【問題６】

問題５で　２^m≡−１（mod　ｐ）よりｍはｋの倍数でない。（問題４）

また、２^2m≡１　（mod　ｐ）よりｍはｋの倍数。
よってｋは２・（偶数）で表される偶数。　（定理２）

（１）ｎ＝１のとき　確かに題意を満たす。

（２）ｎ≧２のとき
ｎを素因数分解することで、
素数ｐ1＜ｐ2＜ｐ3＜……，
自然数x1，
０以上の整数x2，x3，……を用いて、

ｎ＝ｐ1^x1・ｐ2^x2・……　と表せる。
（ｐ1は奇数）

ここでｐ1，ｐ1^x1-1・ｐ2^x2・……　を問題５におけるｐ，ｍとすることで、
k1を２の法ｐ1の位数とすると、k1は、

A1＝２・ｐ1^x1-1・ｐ2^x2・……，

B1＝ｐ1−１　の公約数であるといえる。

ところで、A1の約数は，
｛１，２，p1，p2，２・p1，p3，……，A1｝だが、
この中でB1＝ｐ1−１以下である（公約数になり得る）のは
ｐ1＜ｐ2＜ｐ3＜……　より、１，２のみ。

これと定理２より　k1＝２

これはB1の約数でもある。

k1の定義から

　２^k1≡１（mod　p1）
⇔４≡１（mod　p1）
⇔p1＝１，３　但しｐ1が素数であることからｐ1＝１は有り得ない。

∴k1＝２，ｐ1＝３　が必要。

ところで問題３よりx1＜２　

∴x1＝１

今度は、x2≧１と仮定して、ｐ2をｐとして問題５にあてはめる（k2を２の法ｐ2の位数とする）と、公約数となり得るのは
｛１，２，ｐ1，２・ｐ1｝、
k2は偶数だから　k2＝　２，
２・ｐ1　＝　２，６

k2＝２のときは　上と同様にｐ2＝３が出るが、ｐ1＜ｐ2に反する。

k2＝６のとき、

２^k2≡１（mod　ｐ2）
⇔６４≡１（mod　ｐ2）
⇔７・９≡０　（mod　ｐ2）

ｐ2＝１，３，７

ｐ1＝３＜ｐ2より、ｐ2＝７

∴ｎ＝３・７ｔ　と書ける。

ところで、このとき

２ⁿ＋１
＝２^3・7t＋１
＝（２³）^7t＋１
＝８^7t＋１
≡１^7t＋１（mod　７）
≡２（mod　７）

７は明らかにｎ²の約数なので、これもまた不合理（定理１）。
よって仮定は誤り。x2＝０。

よって、ｎ＝３とならねばならない。
またこのとき確かに題意を満たす。

以上より，

２ⁿ＋１≡０（mod　ｎ²）　⇔　ｎ＝１，３

◆愛知県　ノースダウン　さんからの解答。

【問題１】

２ⁿ＋１は奇数になるので、２ⁿ＋１を割り切る数は奇数である。

【問題２】

最初に、
と置く

題意の合同式が成り立つ ⇔ a(e)-b(e)がc(e)の倍数

であるので、帰納法でこれを示す。
（b(e)＜c(e)で有ることは自明として証明略）

1) e=0の時、a(0)=2、b(0)=2で有るので、
a(0)-b(0)=0となり、ｃ(0)の倍数
→題意を満足する

2)e=nの時、a(n)-b(n)がc(n)の倍数であるならば、
a(n+1)-b(n+1)がc(n+1)の倍数であることを示す。

a(n)-b(n)がc(n)の倍数であるので、

a(n)-b(n)=k*c(n)...(kは負でない整数)

と表すことができる。

変形して、a(n)=b(n)+k*c(n)

a(e+1)=a(e)³、b(e+1)=3*b(e)+2であるので、

　a(n+1)-b(n+1)
=a(n)³-{3*b(n)+2}
={b(n)+k*c(n)}³-3*b(n)-2

=b(n)3+3*b(n)2*k*c(n)+3*b(n)*{k*c(n)}2+{k*c(n)}3-3*b(n)-2...a)

3*b(n)²*k*c(n)+3*b(n)*{k*c(n)}²
={b(n)²*k+b(n)*k²*c(n)}*3*c(n)

と変形できるが、

c(n+1)=3*c(n)であるので、この式は、c(n+1)の倍数である。

また、c(n)が必ず３の倍数であるので

{k*c(n)}³=k³*c(n)²*c(n)も
c(n+1)の倍数となる。

よって、a)の式で、

b(n)³-3*b(n)-2がc(n+1)の倍数

であることを示すことで、題意が満足されることを示すことができる。

ここで、b(n)=-1+3ⁿ⁺¹を使うと、

b(n)³-3*b(n)-2
=(-1+3ⁿ⁺¹)³-3*(-1+3ⁿ⁺¹)-2
=-1+3*3ⁿ⁺¹-3*(3ⁿ⁺¹)²+(3ⁿ⁺¹)³+3-3*3ⁿ⁺¹-2
=-3²ⁿ⁺³+3³ⁿ⁺³
=(-3ⁿ*3²ⁿ)*(3*3ⁿ⁺²)
=(-3ⁿ*3²ⁿ)*{3*c(n)}

よって、c(n+1)の倍数である。
→ e=nの時、a(n)-b(n)がc(n)の倍数であるならば、
a(n+1)-b(n+1)がc(n+1)の倍数であることが示された。

3) 上記、1))より、任意の整数e≧0に対して題意の合同式が正しいことが示された。

【問題３】

ｎが9の倍数の時、
n=y*3^x+2
(xは負でない整数、yは５以上の素数又は５以上の素数のみを因数にもつ合成数）
と表すことができる。

z=3^x+2とおくと、
n=y*zとなる。

この時、

と表すことができる

又【問題２】より、

２^z=(-1+3*z)+9*c*z (cは負でない整数）

と表すことができる。

よって、

={(-1+3*z)+9*c*z}y+1
=(-1+3*z)y+y*(-1+3*z)y-1*9*c*z+…+y*(-1+3*z)*(9*c*z)y-1+(9*c*z)y+1

この式が、n²(=y²*z²)で割り切れるためには、
少なくとも、
(-1+3*z)^y+y*{(-1+3*z)^y-1}*9*c*z+1がz²で割り切れなければならない。

ここで、

1)(-1+3*z)y=(-1)y+y*(-1)y-1*3*z+y*(y-1)*(-1)y-2*(3*z)2+…

2) y*{(-1+3*z)^y-1}*9*c*z
=9*c*y*z*{(-1+3*z)^y-1}
=9*c*y*z*[(-1)^y-1+(y-1)*{(-1)^y-2}*(3*z)+…]
であるので、

z²で割り切れない因子が有るとしたら、
9*c*y*zのみである。

以上により、
-1+3*y*z+9*c*y*z+1がz²で割り切れる場合のみ、
2ⁿ+1がn²で割り切れる。

しかしながら、

-1+3*y*z+9*c*y*z+1
=3*y*z+9*c*y*z
=3*y*z(1+3*c)

であるが、yは3の倍数でないので、
3*(1+3*c)がｚの倍数とならなければならないが、zの倍数にはなり得ない。
(なぜなら、3*(1+3*c)=3+9*c≡3 (mod 9).であり、ｚは9の倍数である。)

よって、
ｎ²が２ⁿ＋１を割り切れば、
ｎは３²(＝９)の倍数でないことが示された。

【問題４】

前提条件のａとｐの関係を書き直すと、
a^k=1+b*p (bは負でない整数）と表すことができる。

ａ^m≡1 (mod p) ⇔ mはkの倍数

を言い換えると、

「mはkの倍数の時、a^m≡1 (mod p) を満足し、kの倍数でないときには
a^m≡1 (mod p) を満足しない」である。

1) mがkの倍数でない時にはa^m≡1 (mod p) が成立しない事を、背理法を用いて示す。

a) ｋの定義より、
m＜kかつa^m≡1 (mod p) を満足するmは存在しない。

b) k＜m＜2*kかつa^m≡1 (mod p) を満足するmが存在すると仮定する。

この時、m=k+x (ｘは、0＜x＜kを満足する整数)と表す事ができる。

a^m=a^k+xであるから、
ａ^k+x≡1 (mod p)を満足する事になる。

しかしながら、
a^k+x
=a^k*a^x
=(1+b*p)*a^xであるので、
ａ^k+x≡1 (mod p)を満足するためには、
a^x=1+cpを満足しなければならない。

これは、a^x≡1 (mod p)を意味しており、kの定義を満足しない。

よって、 k＜m＜2*kかつa^m≡1 (mod p)を満足するmは存在しない。

c) b)と同じ手順で、
n*k＜m＜(n+1)*kかつa^m≡1 (mod p)　が成立するmは存在しない事が証明できる。
（nは2以上の整数）

→mがkの倍数でないときは、a^m≡1 (mod p)　が成立しないことが示された。

2) mがkの倍数の時、a^m≡1 (mod p)　が成立する事を示す。

mがkの倍数であるので、m=k*n（nは自然数）と表すことができる。

よって、
a^m
=a^k*n=(a^k)ⁿ
=(1+b*p)ⁿ

この式を２項定理を用いて展開すれば、
1+d*p (dは自然数)と表すことが可能なことが示される。

a^m=1+d*p⇔a^m≡1 (mod p)で有り、題意が示された。

【問題５】

１）p-1がkの倍数であることを示す。

pが素因数（素数）であるので、２^p-1≡1 (mod p)　が成立する。
よって【問題４】の結果を使用して、p-1がkの倍数であることが示された。

２）２ｍがkの倍数であることを示す。

2ⁿ+1
=2^p*m+1
=(2^p)^m+1
=(2^p-2+2)^m+1

ここで、2^p-2=b*p (bは負でない整数）と表す事ができるので、
2ⁿ+1=(2+b*p)^m+1と表すことができる。

右式を２項定理を用いて展開すると

2^m+m*2^m-1*(b*p)+…+m*2*(b*p)^m-1+(b*p)^m+1

となるが、
m*2^m-1*(b*p)+…+m*2*(b*p)^m-1+(b*p)^mは
pの倍数であるので、2ⁿ+1がｎの倍数になるためには、
2^m+1がpの倍数になる必要がある。

よって、2^m+1=c*p (cは負でない整数）と表すことができる。
(２^m≡-1 (mod p)

ここで、(2^m+1)²を展開すると、

(2^m)²+2*2^m+1
=2^2*m+2*(c*p-1)+1　 (2^m=c*p-1)
=2^2*m+2*c*p-1

となり、2^2*m-1はｐの倍数である。
よって、2^2*m≡1 (mod p)

【問題４】の結果を使用して、2mがkの倍数であることが示された。
以上により、kは2mとp-1の公約数であることが示された。

【問題６】

n=1のとき、2ⁿ+1=3で有るので、n²(=1)で割り切れる

n=3のとき、2ⁿ+1=9で有るので、n²(=9)で割り切れる

ｎが偶数の時は割り切れないことが証明ずみ
よって、ｎが５以上の奇数の時に割り切れないことを示すことで、題意を示すことができる。

1) nが5以上の素数の累乗の時
n=p^x (pは５以上の素数、xは自然数）
と表すことができる。

2n+1
=2(pのx乗)+1
=2p*p*p*...*p(x個）+1
=2p*p*p*...*p(x個)-2p*p*...p(x-1個)+2p*p*...*p(x-1個)-2p*...*p(x-2個)+...+2p*p-2p+2p-2+2+1

よって、
2ⁿ+1=bp+3(bは自然数)となり、nでは、割り切れない。

2） nが3を因数に持たない合成数の場合
ｎの素因数の内、最も小さい素因数をｐとする。

n²が2ⁿ+1を割り切るとしたら、
2の法pの位数kはp-1と2*n/pの公約数になる。
（【問題５】の結果より）

kを求めると、p-1とn/pの公約数は1であるので、
k=1又はk=2となる。

k=1とすると、
2¹≡1 (mod p)となり、この合同式を満足するpは存在しない。

又k=2とすると
2²(=4)≡1 (mod p)となり、この合同式を満足するpは３のみであるが、ｎが３を因数に持つことになり矛盾が生ずる。

よって、ｎが３を因数に持たない合成数の場合
n²が2ⁿ+1を割り切ることが無いことが示された。

3) nが因数として3²を持つ合成数の場合は、解を持たないことは
【問題３】で証明済み。

よって、n=9*xの場合、2ⁿ+1はn²で割り切れない。

4) n=3*x (xは５以上の素数を因数に持つ素数又は合成数の場合）

2n+1
=23*x+1
=(23)x+1
=8x+1
=(9-1)x+1
=9x+x*9x-1*(-1)+x*(x-1)*9x-2*(-1)2+...+x(x-1)*92*(-1)x-2+x*9*(-1)x-1-1+1
=9x-x*9x-1+x(x-1)*9x-2-...-x(x-1)*92+x*9

しかしながら、xの因数は、5以上の素数のみであるので、
9^xがxの倍数となる事はない。

→n=3*xの時、2ⁿ+1はn²の倍数にはならない。

1)から4)により、5以上の全ての奇数の場合において、
2ⁿ+1がn²で割り切れないことが示された

以上により、
ｎ²が２ⁿ＋１を割り切るための必要十分条件は、
ｎ＝１または３であることが証明された。

　『割り切れる？ Part6』へ

　数学の部屋へもどる