流れる空の中で数学を。

とある数学好きの「手作りすうがく」と「気ままな雑記」。

2012マケドニアTSTの問題を解いてみた

twitter 数学 整数問題bot②

数学関連の絶版本・品切れ本をコチラから購入できます！

2012マケドニアTST

今日もtwitterで見かけた問題を解いてみた。以下の問題である。

 この問題、いかにもフェルマーの小定理を使ってくれと言わんばかりの顔をしていたので、そうしたら泥沼にはまった。もし、フェルマーの小定理を使って問題を解けた人がいたら教えてください。

解答

問題は、素数の組(p,q)であって、

(p+q)^p=(q-p)^{2q-1}……(1)

を満たすようなものを全て求めよである。まず、明らかに、

q \gt p

である。大事なことなので何度も言うがフェルマーの小定理を使うと泥沼にはまるので、式をじっと見てやる。すると、両辺はある自然数の冪乗になっていないといけないことに気づくので、p+qとp-qはそれぞれある同じ自然数の冪乗でなければいけない。*1そこで、その自然数をdとおく。まず、(1)式より、dは明らかに1ではない。つぎに、p+qとp-qの冪を自然数k,l \; (k \gt l)とおくと、

p+q=d^k
p-q=d^l

となる。2式の和と差をとると、

2p=d^l(d^{k-l}+1)……(2)
2q=d^l(d^{k-l}-1)……(3)

となる。

2p,2qでdが割り切れないこと

(2)式より、2p|d*2と仮定すると、素因数分解の一意性より*3、

d=2p
d^{k-l}+1=1
\Rightarrow d^{k-l}=0

となりk \gt lより矛盾。よって、

2p\not|d

同様に、(3)式より、2q|d

d=2q
d^{k-l}-1=1
\Rightarrow d^{k-l}=2
\Rightarrow (2q)^{k-l}=2

ここで、q \gt pは共に素数であったので、q\ge 3となり矛盾。

p,qでdが割り切れないこと

 2\not|dかつp|dと仮定すると、(2)式より、

d=p
d^{k-l}+1=2
\Rightarrow d^{k-l}=1

となり、k \gt lであったので矛盾。よって、 p\not|dである。

同様に、 2\not|dかつq|dと仮定すると、 2|(d^{k-l}-1)なので、(3)式より、

 d^{k-l}-1=2
 \Rightarrow d^{k-l}=3

より、

d=q=3
k=l+1

このとき、3より小さな素数は2しかないので、p=2。ところが、(1)式より、

3^{(l+1)\times 2}=3^{l(2\times3-1)}
\Rightarrow 2(l+1)=5l
\Rightarrow 3l=2

この式を満たす自然数lは存在しないので、矛盾。よって、 q\not|dである。

2でdが割り切れることと求める解

dが、pでもqでも割り切れないことが判明したので、残るは、2|dの場合である。このとき、(2)式より

d=2
l=1

である。従って、

p+q=2^k……(4)
p-q=2……(5)

下の式より、p=2とすると、q=0となるので矛盾。よって、p,qは奇素数である。(4)(5)式の和と差をとって、

2p=2^k+2
\Rightarrow p=2^{k-1}+1……(6)
2q=2^k-2
\Rightarrow q=2^{k-1}-1……(7)

ここで、k\gt l \ge 1であったので、k\ge 2である。また、(1)式より、

2^{kp}=2^{2q-1}
\Rightarrow kp=2q-1

より、pが奇素数であったので、kは奇数でなければならない。
k=3のとき、(6)(7)式より、

(p,q)=(5,3)

となり、これは題意をみたす。最後に、k \ge 5 のとき、kが奇数であったことに注意して、m \ge 2を整数としてk=2m+1とおくと、(7)式より、

q=2^{2m}-1
\Rightarrow q=(2^m-1)(2^m+1)

m \ge 2であったので、

2^m+1 \gt 2^m-1 \ge 3

となり、qが合成数となり矛盾。以上より、求める解は、

(p,q)=(5,3)

のみである。

 

*1:素因数分解の一意性より、自明。

*2:a|bは自然数aが自然数bを割り切るという意味である。

*3:以後、同様の状況において、素因数分解の一意性については自明なので断らない。

一般化されたマスターデーモンの解のリスト

数学 オリジナル プチ研究 数学オリンピック

Amazon.co.jp: Yoshiki Ueoka:作品一覧、著者略歴

数学関連の絶版本・品切れ本をコチラから購入できます！

一般化されたマスターデーモン

今回扱う一般化されたマスターデーモンは次の問題である。

自然数r,n,k\ge2に対して、

\frac{r^n+1}{n^k}

が自然数となうるようなnを全て求めよ。
このような解の集合を以後、

D(n,k)

と書くことにする。

D(n,k)=\phi

は解なしという意味である。*1
今回公開する解のリストは、計算過程で素因巣分解ができたものの内、数が大きくなりすぎないものを集めたものである。よって、リストは一部の例外をのぞいて不完全である。不完全な場合は「\cdots」記号で示しておく。*2つまり、「\cdots」記号がないものはそれで全ての解である。ちなみに、最小解はリストの最初に必ず入っている。また、証明は過去記事を見ればほとんど明らかなので省略する。ちなみに、n^2がn^kになっているが、この違いは簡単な不等式の評価ですむ。

 

sky-time-math.hatenablog.jp

 今回紹介するリストは、r=2,\cdots,50までと、興味深いr=80の場合である*3*4。
なお、万が一リストに間違いを見つけた方がいたら優しく教えてほしい。

r=2,\cdots,10までのリスト

r=2の場合

D(2,2)=\{3\}
D(2,k)=\phi \; (k \ge 3)

r=3の場合

D(3,k)=\phi \; (k \ge 2)

r=4の場合

D(4,2)=\{5,205,\cdots\}
D(4,k)=\phi \; (k \ge 3)

r=5の場合

D(5,2)=\{3,21,609,903,2667,9429,159663,\cdots\}
D(5,k)=\phi \; (k \ge 3)

r=6の場合

D(6,2)=\{7,203,1379,\cdots\}
D(6,k)=\phi \; (k \ge 3)

r=7の場合

D(7,k)=\phi \; (k \ge 2)

r=8の場合

D(8,2)=\{3,57,9,171,784899,32547,9961491,\cdots\}
D(8,3)=\{3\}
D(8,k)=\phi \; (k \ge 4)

r=9の場合

D(9,2)=\{5,5905,\cdots\}
D(9,k)=\phi \; (k \ge 3)

r=10の場合

D(10,2)=\{11,253,45023,96569,\cdots\}
D(10,k)=\phi \; (k \ge 3)

r=11,\cdots,20までのリスト

r=11の場合

D(11,2)=\{3,111,\cdots\}
D(11,k)=\phi \; (k \ge 3)

r=12の場合

D(12,2)=\{13,1027,468481,2890927,\cdots\}
D(12,k)=\phi \; (k \ge 3)

r=13の場合

D(13,2)=\{7,203,154553,\cdots\}
D(13,k)=\phi \; (k \ge 3)

r=14の場合

D(14,2)=\{3,15,183,5,355,505,\cdots \}
D(14,k)=\phi \; (k \ge 3)

r=15の場合

D(15,k)=\phi \; (k \ge 2)

r=16の場合

D(16,2)=\{17,6029713,\cdots\}
D(16,k)=\phi \; (k \ge 3)

r=17の場合

D(17,2)=\{3,21,39,9,63,117,12807,50877,\cdots\}
D(17,3)=\{3\}
D(17,k)=\phi \; (k \ge 4)

r=18の場合

D(18,2)=\{19,372742,\cdots\}
D(18,k)=\phi \; (k \ge 3)

r=19の場合

D(19,2)=\{5,55,11255,\cdots\}
D(19,k)=\phi \; (k \ge 3)

r=20の場合

D(20,2)=\{3,21,381,7,5789,73703,\cdots\}
D(20,k)=\phi \; (k \ge 3)

r=21,\cdots,30までのリスト

r=21の場合

D(21,2)=\{11,253,66803,113987819,\cdots\}
D(21,k)=\phi \; (k \ge 3)

r=22の場合

D(22,2)=\{23,1081,10603,31763,44459,\cdots\}
D(22,k)=\phi \; (k \ge 3)

r=23の場合

D(23,2)=\{3,39,507,33501,\cdots\}
D(23,k)=\phi \; (k \ge 3)

r=24の場合

D(24,2)=\{5,55,28955,25,275,3775,144775,198775,2162525,\cdots\}
D(25,3)=\{5\}
D(25,k)=\phi \; (k \ge 4)

r=25の場合

D(25,2)=\{13,689,\cdots\}
D(25,k)=\phi \; (k \ge 3)

r=26の場合

 D(26,2)=\{3,21,93,9,63,279,27,189,837,42309,651,

                       ,903,1491,4431,105861,\cdots\}
D(26,3)=\{3\}
D(26,4)=\{3\}
D(26,k)=\phi \; (k \ge 5)

r=27の場合

D(27,2)=\{ 7,301,3829,15883,\cdots \}
D(27,k)=\phi \; (k \ge 3)

r=28の場合

D(28,2)=\{29,1172383,\cdots \}
D(28,k)=\phi \; (k \ge 3)

r=29の場合

D(29,2)=\{3,15,813,5,55,155,2005,465,4065,6015,\cdots\}
D(29,k)=\phi \; (k \ge 3)

r=30の場合

D(30,2)=\{31,126883,603539,1510723,3601859,\cdots\}
D(30,k)=\phi \; (k \ge 3)

r=31,\cdots,40までのリスト

r=31の場合

D(31,k)=\phi \; (k \ge 2)

r=32の場合

D(32,2)=\{3,33,993,11,7513,32681,538037401,2211,10923,22539,\cdots\}
D(32,k)=\phi \; (k \ge 3)

r=33の場合

D(33,2)=\{17,\cdots\}
D(33,k)=\phi \; (k \ge 3)

r=34の場合

D(34,2)=\{5,35,1298155,7,203,497,728833,2485,\cdots\}
D(34,k)=\phi \; (k \ge 3)

r=35の場合

D(35,2)=\{3,39,111,291,9,117,333,657,873,4869,496053

                      ,3783,6123,12207,\cdots\}
D(35,3)=\{3\}
D(35,k)=\phi \; (k \ge 4)

r=36の場合

D(36,2)=\{37,\cdots\}
D(36,k)=\phi \; (k \ge 3)

r=37の場合

D(37,2)=\{19,3629,\cdots\}
D(37,k)=\phi \; (k \ge 3)

r=38の場合

D(38,2)=\{39,\cdots\}
D(38,k)=\phi \; (k \ge 3)

r=39の場合

D(39,2)=\{5,55,205055,\cdots\}

r=40の場合

D(40,2)=\{41,\cdots\}
D(40,k)=\phi \; (k \ge 3)

r=41,\cdots,50までのリスト

r=41の場合

D(41,2)=\{3,21,1641,7,497,1491,11487,\cdots\}
D(41,k)=\phi \; (k \ge 3)

r=42の場合

D(42,2)=\{43,\cdots\}
D(42,k)=\phi \; (k \ge 3)

r=43の場合

D(43,2)=\{11,253,737,\cdots\}
D(43,k)=\phi \; (k \ge 3)

r=44の場合

D(44,2)=\{3,15,1893,9,45,5679,136251,5,2105,8705,465,6315,9465,\cdots\}
D(44,3)=\{3\}
D(44,k)=\phi \; (k \ge 4)

r=45の場合

D(45,2)=\{23,1081,10603,635881,749087,\cdots\}
D(45,k)=\phi \; (k \ge 3)

r=46の場合

D(46,2)=\{47,\cdots\}
D(46,k)=\phi \; (k \ge 3)

r=47の場合

D(47,2)=\{3,21,309,2163,74109,123501,\cdots\}
D(47,k)=\phi \; (k \ge 3)

r=48の場合

D(48,2)=\{7,49,\cdots\}
D(48,3)=\{7\}
D(48,k)=\phi \; (k \ge 4)

r=49の場合

D(49,2)=\{15,1405,20105,25,2525,7025,100525,325025,632525,\cdots\}
D(49,3)=\{5\}
D(49,k)=\phi \; (k \ge 4)

r=50の場合

D(50,2)=\{3,51,57,129,17\}
D(50,k)=\phi \; (k \ge 3)

r=80の場合

D(80,2)=\{3,21,129,147,609,903,2667,100569,387,1161,\cdots\}
D(80,3)=\{3,63,129,9,387,\cdots \}
D(80,4)=\{3\}
D(80,5)=\{3\}
D(80,k)=\phi \; (k \ge 6)

 

 

*1:ちなみに、r=2^m-1と表せるとき、つまりrがメルセンヌ数のときは、常に解なしである。

*2:ちなみに、残りの解は必ず、リストに含まれる素数の倍数になっている。

*3:なんと、D(80,5) \neq \phiである!

*4:一般に、pを奇素数として、r=p^m-1とあらわされるとき、mが大きければ、大きなkまで解を持つ傾向にある。

【第1回】FoxQからの出題第1回の解答【2019/08/25出題】

twitter オリジナル 数学

数学関連の絶版本・品切れ本をコチラから購入できます！

FoxQからの出題(第１回)

twitterにて2019/08/25に出題した以下の問題の解答例をあげます。

小さなn

問題の19の倍数の条件は実は外せるので、外して解く。つまり、

2以上の自然数nに対して、

\frac{8^n+1}{n^3}

が自然数になるようなnを全て求めよ。
まず、nが偶数であると仮定すると、分母が偶数、分子が奇数になって題意の数が自然数にならないので矛盾。よって、nは奇数である。
小さなnについて見てみると、n=2で65/8,n=3で19となるので、n=3は1つの解になっている。これ以外に解がないとあたりをつけて証明する方針で行く。

因数分解

簡単のためr=8として

\frac{r^n+1}{n^3}……(1)

と書き直す。pをnを素因数分解したときの最小の奇素数として、

n=p^kN……(2)

とおくと、

 r^n+1=(r+1)\frac{r^p+1}{r+1} \frac{r^{p^2}+1}{r^p+1}\cdots \frac{r^{p^k}+1}{r^{p^{k-1}}+1} \frac{r^{p^kN}+1}{r^{p^k}+1} ……(3)

と分解できる。このとき、自然数xと奇数mに対して、f_m(x)を

f_m(x)=\frac{x^m+1}{x+1}=1-x+x^2-\cdots+x^{m-1}……(4)

とおくと、f_m(x)は自然数となっている。これを用いて、(3)式を書き直すと、

r^n+1=(r+1) f_p(r) \cdot f_p(r^p) \cdot f_p(r^{p^2})\cdots f_p(r^{p^{k-1}}) f_N(r^{p^k})

と表せる。まず、 f_p(r^{p^j})) \; (j=0,1,\cdots,k-1)がp=3でちょうど一回ずつ割り切れることを証明する。次に、 f_N(r^{p^k})がp=3で割り切れないことを証明する。これにより、nの最小の素因数の候補がp=3となる。

  f_p(r^{p^j}) \; (j=0,1,\cdots,k-1)がp=3でちょうど一回ずつ割り切れること

以後、p=3とする。まず、フェルマーの小定理より、

r^p \equiv r \; (\bmod p)……(5)

なので、

f_p(r^{p^j}) \equiv f_p(r)……(6)

である。よって、f_p(r)がp=3でちょうど一回だけ割れることを示せばよい。r=8であったので、法を3として

f_3(8)=1-8+8^2 \equiv 1-(-1)+(-1)^2 =3 \equiv 0 \; (\bmod 3) ……(7)

より、 f_p(r^{p^j}) \; (j=0,1,\cdots,k-1)はp=3で少なくとも一回は割り切れる。

次に、法を9として

f_3(8)=1-8+8^2 \equiv 1-(-1)+(-1)^2 =3 \not\equiv 0 \; (\bmod 9) ……(8)

なので、 f_p(r^{p^j}) \; (j=0,1,\cdots,k-1)はp=3でちょうど一回だけ割り切れる。

f_N(r^{p^k})がp=3で割り切れないこと

フェルマーの小定理((5)式)より、

f_N(r^{p^k})=f_N(r)……(9)

である。法を3として

f_N(8)=1-8+8^2-\cdots+8^{N-1}

      =1-(-1)+(-1)^2-\cdots+(-1)^{N-1}=N \; (\bmod 3)……(10)

ここで、3とNは互いに素であったので、

f_N(8) \not\equiv 0 \; (\bmod 3)……(11)

が言えた。つまり、f_N(r^{p^k})は3で割り切れない。

分子・分母が3で何回割れるか

以上より、

r+1=9=3^2……(12)

であるから、n=3^kNとするとき、(1)式の分子は3でk+2回割り切れる。
分母は3で3k回割り切れるので、題意を満たすためには次の不等式が成り立つ必要がある。

k+2 \ge 3k
\Rightarrow 2k \le 2
\Rightarrow k=0,1……(13)

nが3以外の素因子を持たないこと

nが3以外の素因子を持たないことを証明する。
nの3より大きいnの最小の素因数をqとし、Mをqより大きな素因数の積のみからなる自然数とする。つまり、qとMは互いに素である。このとき、mを自然数としてnは、

n=3^k q^m M……(14)

と表せる。まず、

R=8^{3^k}……(15)

とおくと、

R=8,512……(16)

である。法をqとしてフェルマーの小定理を使うと、R^q \equiv Rなので、

8^n+1=R^{q^m M}+1 \equiv R^M \; (\bmod q)……(17)

となる。仮定より、8^n+1\equiv 0 \; (\bmod q)なので、

R^M+1\equiv 0 \; (\bmod q)
R^{2M}\equiv 1 \; (\bmod q)……(18)

である。また、フェルマーの小定理より、

R^{q-1}\equiv 1 \; (\bmod q)……(19)

であった。ここで、

R^\mu \equiv 1 \; (\bmod q)……(20)

が成り立つ最小の自然数を\muとすると、(18)(19)式より、ある自然数s,tが存在して、

2M=s\mu……(21)
q-1=t\mu……(22)

と表せる。(21)式の両辺にtをかけると、

2Mt=s(q-1)……(23)

を得る。ここで、Mの素因子は全てqより大きいか、またはM=1なので、ある自然数uが存在して、

 s=Mu……(24)

となる。これを(21)式に代入して、

2=u\mu
\Rightarrow \mu=1,2……(25) 

を得る。ここで、場合分けを行う。

①\mu=1の場合

8^n+1\equiv R^M+1 \equiv 1+1 =2 \; (\bmod q)

となり矛盾。

②\mu=2の場合

R \not\equiv 1であったので、

R\equiv -1
\Rightarrow R+1 \equiv 0 (\bmod q)……(26)

を得る。(14)(16)式でk=0のとき、

R+1=9 \equiv \; (\bmod q)……(27)

を得るが、qは3より大きな素数なので矛盾。以後、k=1、R=512とすると、

R+1=513=3^3 \times 19 \; (\bmod q)……(28)

を得る。これより、

q=19……(29)

でなければいけないが、(3)式より、R^{q^m M}は

8^n+1=R^{q^m M}+1
     =(R+1) f_q(R) \cdot f_q(R^q) \cdot f_q(R^{q^2})\cdots f_q(R^{q^{k-1}}) f_M(R^{q^k})……(30)

と因数分解できるので、(26)式に注意すると、p=3のときの議論と全く同様にして、8^n+1が19でちょうどm+1回だけ割り切れることがわかる。ところが、分母はn^3なので、19で3m回割り切れる。(28)式より、(1)式が自然数となるためには、次の不等式が成り立つ必要がある。

m+1 \ge 3m
\Rightarrow m \le \frac{1}{2}……(31)

これを満たす自然数mは存在しないので矛盾。したがって、nは3よりおおきな素因子を持たない。よって、求める解は、

n=3

のみであることが示された。

 

2009スペイン数学オリンピック

twitter 数学 数学オリンピック 整数問題bot②

数学関連の絶版本・品切れ本をコチラから購入できます！

2009スペイン数学オリンピック

twitterで見かけた以下の問題を解いてみた。たまには簡単めの問題を解くのもいいだろう。

解答

問題は、

x^2-y^4=2009

を満たすような整数の組(x,y)を全て求めよである。
問題がx^2,y^2の形になっているので、x \ge 0,y\ge 0として一般性を失わない。まず、

2009=7^2 \times 41

と素因数分解できる。次に

x^2-y^4=(x+y^2)(x-y^2)

なので、x+y^2 \ge 0 とx+y^2 \ge x-y^2より、可能な因数分解は

(x+y^2,x-y^2)=(2009,1),(287,7),(49,41)

の3通りである。ところで、因数の差を見ると、

(x+y^2)-(x-y^2)=2y^2……(1)

となっている。そこで因数の差を調べると、

2009-1=2008=2^3\times 251
287-7=280=2^3\times 5 \times 7
49-41=8=2\times 2^2

となり、

(x+y^2,x-y^2)=(49,41)

 のみが(1)式の条件を満たす、また同時にy=2であることもわかる。このときx=45である。

x \ge 0,y\ge 0として一般性を失わないとしていたので、求める整数解は、

(x,y)=(\pm 45,\pm 2)

である。ここでは、複号任意である。

1997南アフリカ数学オリンピックの問題を解いてみた。

twitter 数学オリンピック 数学 整数問題bot②

数学関連の絶版本・品切れ本をコチラから購入できます！

1997南アフリカ数学オリンピック

たまには簡単めのこんな問題を解いてみました。方針は、ひたすらmodをとるだけです。

解答

問題は、

1+3^x=2^y

であるような正の整数の組(x,y)を全て求めよである。

x=0のとき、1+1=2^yより、求める解の１つは

(x,y)=(0,1)

以後、

x \ge 1

とする。y=0のとき、3^x=0となるがこれを満たすxは明らかに存在しない。よって、

y \ge 1

法を3として、

1\equiv 2^y

より、yは偶数で、

y=2k \; (k \ge 1)

とかける。したがって、

1+3^x=4^k

ここで、x=1のとき、k=1は明らかに求める解の１つである。よって、

(x,y)=(1,2)

は求める解のうちの１つである。以後、x\gt 1 とする。
法を4として

1+3^x \equiv 0
\Rightarrow 3^x \equiv 3

これより、xは奇数で

x=2l+1 \; (l \ge 1)

とおける。したがって、

1+3 \cdot 9^l =4^k

法を9として、

1\equiv 4^k

これより、kは３の倍数である。そこで、

k=3m \; (m\ge 1)

とおくと、

1+3 \cdot 9^l =64^m

最後に法を8とすると、

1+3 \equiv 0
4\equiv 0 \; (\bmod 8)

となり矛盾。よって、x\gt 1の解は存在しない。
以上より、求める解は、

(x,y)=(0,1),(1,2)

のみである。

整数問題botの自作問題を解いてみた1

twitter 数学 整数問題bot

整数問題botの自作問題

昨日見かけた問題を解いてみた。難易度、易とあるがとてもそうは思えない、歯ごたえのある問題だった。ひょっとすると、別の解法があるのかも。

範囲の絞り込み

問題は、

5^a+12^b=13^c……(1)

を満たす正の整数の組を全て求めるというもの。
まずは、a,b,cの小さな値から絞り込んでいく。
c=0とすると、

1=5^a+12^b \ge2

となり矛盾。よって、c\ge1。
次に、b=0とすると、

5^a=13^c-1

法を5にとると、a\ge1のとき、

0\equiv 3-1=2

となり矛盾。a=0とき、

1 =13^a-1
13^a=2

となりやはり矛盾。よって、b\ge 1。
最後にa=0とおき、写像f(b,c)を次の式によって定義する。

1=f(b,c) \equiv 13^c-12^b

この写像が単射であることを証明する。ある組(b,c),(b',c')に対して

f(b,c)=f(b',c')

となったとすると、

13^c-12^b=13^{c'}-12^{b'}……(2)

これは、c \ge c'のとき、一般性を失わずに次のように変形できる。*1

13^{c'}(13^{c-c'}-1)=12^{b'}(12^{b-b'}-1)

ここで、

b \neq b'

と仮定すると*2、13と12は互いに素なので

13^{c'}=12^{b-b'}-1

となるので、法を12にとると、

1\equiv -1 \; (\bmod 12)

となり矛盾。よって、b=b'である。(2)式より、直ちにc=c'が従う。
よって、fは単射である。したがって、a=0のとき

b=c=1

は唯１つの解となる。以後、a \ge 1とする。まずは、1組の解

(a,b,c)=(0,1,1)

が求まった。

原始ピタゴラス数へ

b\ge1より、

5^a \equiv 1 \; (\bmod 12)

これより、a=1,2,3\cdotsに対して5^a \equiv 5,1,5,\cdotsが従うので、aは偶数である。そこで、自然数k\ge1をとって

a=2k

とおく。次に法を13として、

(-1)^k+(-1)^b \equiv 0 \; (\bmod 13)

より、nを正の整数として

b=2n+k+1……(3)

が従う。次は、法を24にして、

1+12^{k+1} \cdot 12^{2n} \equiv 13^c \; (\bmod 24)

ここで、k \ge 1であったので、

1\equiv 13^c \; (\bmod 24)

これより、c=1,2,3,\cdotsに対して13^c \equiv 13,1,13,\cdotsが従うので、cも偶数である。そこで、自然数l \ge 1をとって

c=2l

とおく最後に法を5として、

12^{k+2n+1} \equiv 13^{2l} \; (\bmod 5)
4^n 12^{k+1} \equiv 13^{2l} \; (\bmod 5)
2^{k+1} \equiv 3^{2l} \; (\bmod 5)

ここで、l=1,2,3,\cdotsに対して、3^{2l}\equiv 4,1,4,\cdotsとなり、また、k+1=1,2,3,4,5,\cdotsに対して、2^{k*1}=2,4,3,1,2,\cdotsとなるので、k+1は偶数である。(3)式より、bも偶数となるので、自然数m \ge 1をとって、

b=2m

とおける。以上をまとめて、(1)式に代入すると、

(5^k)^2+(12^m)^2=(13^l)^2

となり、5,12,13は全て互いに素なので、これは原始ピタゴラス数となっている。

原始ピタゴラス数を紐解く

原始ピタゴラス数は、互いに素で偶奇の異なる2数s,tによって、

5^k=s^2-t^2……(4)
12^m=2st……(5)
13^l=s^2+t^2……(6)

と表せる。(4)(5)式より、s \gt tとs,tが互いに素なことに注意すると、

s=3^m……(5)
t=2^{2m-1}……(6)

となる。これを(4)式に代入すると

5^k=9^m-4^{2m-1}

ここで、

k=1,m=1

は１つの解になっている。このとき、

s=3,t=2

となっており、

l=1

となる。以上をまとめると、

k=l=m=1

であり、これに対応して、解

(a,b,c)=(2,2,2)

が求まる。

これ以外に解のないこと

 数学的帰納法を用いて、上述した解以外の解が存在しないことを証明する。
まず、(4)(5)(6)式から、m=2のとき、

9^2-4^3=17

は5の冪乗ではないので不適。
ここで、m=3のとき、

9^3-4^5 =-295

なので、m\ge3のとき、sとtを入れ替える必要がある。

m\ge3のとき、関数g(m)を

g(m) \equiv4^{2m-1}- 9^m=2^{4m-2}-9^m 

と定義すると、微分して

g'(m)= 16^m \log 2 -9^m \log 9

となるが、

g'(m)=0 \Rightarrow 2.0052...

である。また、g'(3)=1237.35 \gt 0であるから、m \ge 3のとき、g(m)は単調増加関数である。特に

g(3)=295=5 \times 59 \gt 5

であったので、m \ge 3のとき、

g(m) \gt 5

である。

g(3)\equiv 5 \; (\bmod 25)
g(4) \equiv 3 \; (\bmod 25)
g(5) \equiv 20 \; (\bmod 25)
g(6) \equiv 13 \; (\bmod 25)
g(7) \equiv 20 \; (\bmod 25)
g(8) \equiv 3 \; (\bmod 25)
g(9) \equiv 20 \; (\bmod 25)
g(10) \equiv 18 \; (\bmod 25)
g(11) \equiv 20 \; (\bmod 25)
g(12) \equiv 8 \; (\bmod 25)
g(13) \equiv 20 \; (\bmod 25)
g(14) \equiv 23 \; (\bmod 25)
g(15) \equiv 20 \; (\bmod 25)
g(16) \equiv 13 \; (\bmod 25)
g(17) \equiv 20 \; (\bmod 25)
g(18) \equiv 3 \; (\bmod 25)
g(19) \equiv 20 \; (\bmod 25)
g(20) \equiv 18 \; (\bmod 25)
g(21) \equiv 20 \; (\bmod 25)
g(22) \equiv 8 \; (\bmod 25)
g(23) \equiv 20 \; (\bmod 25)
g(24) \equiv 23 \; (\bmod 25)
g(25) \equiv 20 \; (\bmod 25)

以上の観察から、m \ge 5が奇数のとき、

g(m)=20

mが偶数のとき、m=6,8,10,12,14,\cdotsの場合、

g(m)=13,3,18,8,23

を繰り返すことが予想される。すなわち、

g(m) \equiv g(m+10) \; (\bmod 25) 

が予想される。実際、

g(m+10) \equiv=2^{4m+38}-9^{m+10} 

ここで、

9^{10} \equiv 1 \; (\bmod 25)
2^{40} \equiv 1 \; (\bmod25)

より、m \ge 5に対して、

g(m+10)=g(m)

が示された。よって、m\ge 5のとき、g(m)は5より大きく25で割り切れないので、

g(m)は5の冪乗ではない。
また、直接確認したように-g(2),g(3),g(4)も5の冪乗ではない。

解答

よって、求める解は

(a,b,c)=(0,1,1),(2,2,2)

である。

 

 

*1:c \lt c' のときも、13^{c}(13^{c'-c}-1)=12^{b'}(12^{b-b'}-1)として同様の議論ができる。

*2:一般性を失わずにb \gt b'とできる。

2009JMO本選1を解いてみた

数学オリンピック 数学 twitter 整数問題bot

数学関連の絶版本・品切れ本をコチラから購入できます！

追記(2019/08/25):(4)式を少し修正しました。

2019JMO本選1

どうも「おはようございます」すると、「とある自然数を全て求めなければいけない」呪いにかかったようなので、以下の問題を解く。

解答

問題は

f(n) \equiv \frac{8^n+n}{2^n+n}……(1)

が「自然数になる場合を求めよ」である。

まずは、8^n+nを2^n+nで割る。すると、

8^n+n=(2^n+n)(4^n-2^n n+n^2)+\frac{n-n^3}{2^n+n}……(2)

 となるので、

 \frac{n-n^3}{2^n+n}……(3)

が整数となるようなnを求めればよい。

g(n)=|2^n+n|-|n^3-n|=2^n-n^3+2n……(4)

とおく。nで微分して、\log(2)\ge 1/2に注意して、

g'(n)=2^n \log (2)-3n^2 +2 \ge 2^{n-1} -3n^2 +2

ここで、g'(9) \gt 15 \gt 0なので、n \ge 9 でg'(n) \gt 0より、g(n)はn \ge 9で単調増加関数となる。
ところで、

g(9)=-199
g(10)=44

なので、n \ge 10でg(n)は正となる。従って、n \ge 10で

  \left| \frac{n-n^3}{2^n+n} \right| \lt 1

となる。よって、n=1,2,\cdots,9の場合のみを調べればいい。(2)式より、

h(n) \equiv \frac{n-n^3}{2^n+n}

とおくと、

h(1)=0
h(2)=-1
h(3)=-\frac{24}{11}
h(4)=-3
h(5)=-\frac{120}{37}
h(6)=-3
h(7)=-\frac{112}{45}
h(8)=-\frac{21}{11}
h(9)=-\frac{720}{521}

上に現れている分数は全て既約分数である。よって、(2)式の右辺が整数になるn=1,2,4,6の場合を調べれば良い。

f(1)=3
f(2)=11
f(4)=205
f(6)=3745
したがって、求めるnは

n=1,2,4,6

である。