入試数学コンテスト第6回第6問解答解説

更新日時 2022/02/05
目次
  • 第6問

第6問

第6問

2a+5b2^a + 5^b が平方数となるような正整数の組 (a,b)(a,b) を全て求めよ。

入力するときは次の手順に従って得られる A,BA,B を入力せよ。

  1. aa が小さい順に解を並べる。aa が等しいときは, bb の値が小さいほうを先に書く。
  2. こうして並べた解を (a1,b1),(a2,b2),(a_1,b_1) , (a_2 , b_2) , \cdots とおく。
  3. nn 番目の素数を pnp_n として, A=p1a1p2a2=2a13a2pnanB=p1b1p2b2=2b13b2pnbnA = p_1^{a_1} \cdot p_2^{a_2} \cdots = 2^{a_1} \cdot 3^{a_2} \cdots p_n^{a_n} \cdots \\ B = p_1^{b_1} \cdot p_2^{b_2} \cdots = 2^{b_1} \cdot 3^{b_2} \cdots p_n^{b_n} \cdots と定める。

整数問題の中でも,方程式の整数解を求める(いわゆるディオファントス方程式の)問題です.整数問題へのアプローチとしては基本的な3つの手法

を押さえておきましょう.今回は1つ目と3つ目をフル活用します.

考察

まずは問題を整理します.

問題

2a+5b=n22^a + 5^b=n^2を満たす整数 nn と正の整数 a,ba,b の組 (n,a,b)(n, a, b) を全て求めよ.

とりあえず小さい整数 a,ba,b でいろいろ試してみると,次のような解が見つかります. (n2,a,b)=(9,2,1),(9,3,0)(n^2, a, b) = (9, 2, 1), (9, 3, 0)このうち a,b>0a,b>0 を満たすのは (a,b)=(2,1)(a,b) = (2,1)です.またこれ以外の整数解はなかなか見つかりません.そこで整数解はこれらしかないのではないかというのを念頭に,因数分解やmodを使って情報を引き出していきます.

mod演算

初めにできることとして,いろいろな数で mod をとって情報を引き出します.基本的には「素数と(小さい)素数べき」として mod2,3,4,5,7,9,11,13\mod 2,3,4,5,7,9,11,13 あたりを総当たりでみるのですが,今回は(5b5^b という形から)mod5\mod 5 でうまくいきます.

考察1

b>0b>0 より,2a+5b=n22^a + 5^b=n^2mod5\mod{5} をみると2an2mod52^a \equiv n^2 \mod{5}となる.これは

  • n0mod5n \equiv 0 \mod{5} のとき 2a0mod52^a \equiv 0 \mod{5}
  • n1,4mod5n \equiv 1, 4 \mod{5} のとき 2a1mod52^a \equiv 1 \mod{5}
  • n2,3mod5n \equiv 2, 3 \mod{5} のとき 2a4mod52^a \equiv 4 \mod{5}

となる.また 22 べき 2,4,8,16,2,4,8,16,\dotsmod5\mod{5}2,4,3,1,2, 4, 3, 1,\dotsを繰り返すから,2a0,1,4mod52^a \equiv 0, 1, 4 \mod{5} となるのは aa が偶数のとき.

よって正の整数 cc により a=2ca=2c となります.

因数分解

前の考察により 22c+5b=n22^{2c}+5^b=n^2という方程式の整数解を考えればよいことがわかりました.これは5b=n222c5^b =n^2-2^{2c}とすることで因数分解でき,さらに情報を得ることができます.

考察2

5b=(n2c)(n+2c)5^b = (n-2^c)(n+2^c)と因数分解すると,右辺の n±2cn \pm 2^c は( n0n\geq 0 としてよく,そのとき両方とも正の整数であることに注意すると)どちらも 55 べきとなることがわかる.よってn2c=5sn - 2^c = 5^sn+2c=5tn+2^c=5^tとなる.(s,ts,ts+t=bs+t=b を満たす 00 以上の整数.)

よって c,s,tc,s,t がわかれば n,a,bn, a, b もわかって問題が解けます. ではこれらの式から nn を消去して c,s,tc,s,t の条件を求めましょう.

考察3

n2c=5sn - 2^c = 5^sn+2c=5tn+2^c=5^tの差をとって2c+2c=5t5s2^c+2^c=5^t-5^sつまり2c+1=5s(5ts1)2^{c+1}=5^s(5^{t-s}-1)がわかる.n2c<n+2cn-2^c < n+2^c より s<ts < t だから,5ts15^{t-s}-1 は整数.よってこの式は整数の因数分解を表しており,左辺は 55 の倍数でないから s=0s=0 となる.すると s+t=bs+t=b より t=bt=b である.

つまり c>0c>0b>0b>0 かつ2c+1=5b12^{c+1}=5^b-1を満たす整数 (c,b)(c,b) を求める問題に帰着できました.

mod 再び

方程式2c+1=5b12^{c+1}=5^b-1c>0c>0b>0b > 0 となる整数解を求めます.再びmod2,3,4,5,\mod{2, 3, 4, 5, \dots} で条件を絞り込んでいきます.

考察4

2c+1=5b12^{c+1}=5^b-1mod3\mod{3} で見ると(1)c+1(1)b1mod3(-1)^{c+1} \equiv (-1)^b-1 \mod{3}である.b,cb, c の偶奇で場合分けすると,これが成り立つのは b,cb,c が両方奇数のとき.よって正の整数 b,cb',c' により b=2b1b=2b'-1c=2c1c=2c'-1となる.つまり方程式は22c=52b112^{2c'}=5^{2b'-1}-1である.次に mod5\mod{5} で見ると,b=2b1>0b=2b'-1>0 だから(1)c4c22c1mod5(-1)^{c'}\equiv 4^{c'}\equiv 2^{2c'}\equiv -1 \mod{5}となる.よって cc' は奇数.

よって正の整数 cc'' により c=2c1c'=2c''-1c+1=4c2c + 1=4c''-2 となり,方程式は24c2=52b112^{4c''-2}=5^{2b'-1}-1となります.だんだんと情報が得られてきました.さらに mod で調べることができます.

考察5

24c2=52b112^{4c''-2}=5^{2b'-1}-1mod8\mod{8} で見ると,c2c'' \geq 2 のとき 052b11mod80\equiv 5^{2b'-1}-1 \mod{8}となるが,55 べき 5,25,5,25,\dotsmod8\mod{8}5,1,5,1,\dots を繰り返すから,(2b12b'-1 :奇数より)右辺は常に 514mod85 - 1 \equiv 4\mod{8}である.よって c2c'' \geq 2 のときこの方程式は b>0b'>0 となる整数解を持たない.

よって24c2=52b112^{4c''-2}=5^{2b'-1}-1b,c>0b',c''>0 となる整数解は c=1c''=1 のときの (b,c)=(1,1)(b', c'')=(1,1) のみ,と解くことができます.これは元の方程式の (a,b)=(2,1)(a,b)=(2,1) に対応するので,問題を解くことができました.

解答

以上を答案にまとめます.

第6問

2a+5b=n22^a + 5^b=n^2を満たす整数 nn と正の整数 a,ba,b の組 (n,a,b)(n, a, b) を求める.

mod5\mod 5で考えると,右辺は 001144 である.aaが奇数 2c+12c+1 のとき左辺は2a+5b22c+1(1)c×22,3mod52^a+5^b \equiv 2^{2c+1} \equiv (-1)^c \times 2 \equiv 2,3 \mod{5}だから不適.よってaaは偶数だから,a=2ca=2ccc は正の整数)とおける.すると方程式は5b=(n2c)(n+2c)5^b = (n-2^c)(n+2^c)と変形でき,整数 0s<t0 \leq s < tによりs+t=bs+t=bn+2c=5sn+2^c=5^sn2c=5tn-2^c=5^tとかけることがわかる.下2つの式より2c+1=5t5s=5s(5ts1)2^{c+1}=5^t-5^s=5^s(5^{t-s} - 1)となり,左辺は55の倍数でないから右辺もそう.よってs=0s=0だから,2c+1=5b12^{c+1}=5^b-1が成り立つ.

これをmod3\mod 3 でみると,(1)c+1(1)b1mod3(-1)^{c+1} \equiv (-1)^b-1 \mod{3}である.これが成り立つのは b,cb,c がともに奇数のときのみ.

次にmod5\mod 5 でみると,b>0b>0 より2c+11mod52^{c+1}\equiv -1 \mod{5}となる.22 べき 2,4,8,16,2,4,8,16,\dots55 で割った余りは 2,4,3,1,2,4,3,1,\dots を繰り返すから,c+1c+14c24c''-2 の形の整数(cc'' は正の整数).よって正の奇数 bb と正の整数 cc'' が存在し 24c2=5b12^{4c''-2}=5^b-1 を満たす.

最後にmod8\mod 8でみる.c2c'' \geq 2 と仮定すると上の式の左辺は 6464 の倍数だが,55 べき 5,25,5,25,\dots88 で割った余りは5,1,5,1,5,1,5,1,\dots を繰り返すから,5b15^b-188 の倍数になるのは bb が偶数のときのみ,これは bb が奇数だったことに反する.

よってc=1c''=1,つまりc+1=4c2=2c+1=4c''-2=2で,このとき (a,b)=(2,1)(a,b)=(2,1)である.

以上より求める解は (a,b)=(2,1)(a,b)=(2,1) である.また解答欄に入力する値は A=22=4A=2^2=4B=21=2B=2^1=2である.

また b=0b=0 であるような解が (a,b)=(3,0)(a,b)=(3,0) しかないことも次のようにして証明できます.

証明

方程式 2a+1=n22^a+1=n^2の整数解を求める. 2a=(n1)(n+1)2^a=(n-1)(n+1)だから,0s<t0 \leq s<t となる整数 s,ts,t によりs+t=as+t=an1=2snー1=2^sn1=2tn+1=2^tとかける.すると 2=2t2s=2s(2ts1)2=2^t-2^s=2^s(2^{t-s}-1) だから,s=1s=1 かつ ts=1t-s=1 となり,a=s+t=3a=s+t=3 である.

まとめ

整数問題の中でも,このような「方程式の整数解」を求めるタイプの問題には因数分解して素因数を見る,mod により情報を集めることが有効なことが多いです.よくある展開としては

  • 因数分解された式=素数 or 素数べき\text{因数分解された式} = \text{素数 or 素数べき} という式を作ることで新しい方程式が得られる.
  • 小さい数や素数で mod をとって両辺の値を比べることで変数の条件が絞れる.

といったものが多い印象です.また今回出てきた平方数の mod での値については,mod3,4\mod{3,4} の結果が頻出なので覚えておきましょう.(→平方剰余と基本的な問題