入試数学コンテスト第6回第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=b n2c=5sn-2^c=5^s n+2c=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=a n1=2snー1=2^s n1=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} の結果が頻出なので覚えておきましょう。(→平方剰余と基本的な問題