入試数学コンテスト第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=p1a1⋅p2a2⋯=2a1⋅3a2⋯pnan⋯B=p1b1⋅p2b2⋯=2b1⋅3b2⋯pnbn⋯A = 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 をとって情報を引き出します．基本的には「素数と（小さい）素数べき」として mod  2,3,4,5,7,9,11,13\mod 2,3,4,5,7,9,11,13 あたりを総当たりでみるのですが，今回は（5b5^b という形から）mod  5\mod 5 でうまくいきます．

考察1

b>0b>0 より，2a+5b=n22^a + 5^b=n^2の mod  5\mod{5} をみると2a≡n2mod  52^a \equiv n^2 \mod{5}となる．これは

  • n≡0mod  5n \equiv 0 \mod{5} のとき 2a≡0mod  52^a \equiv 0 \mod{5}
  • n≡1,4mod  5n \equiv 1, 4 \mod{5} のとき 2a≡1mod  52^a \equiv 1 \mod{5}
  • n≡2,3mod  5n \equiv 2, 3 \mod{5} のとき 2a≡4mod  52^a \equiv 4 \mod{5}

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

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

因数分解

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

考察2

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

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

考察3

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

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

mod 再び

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

考察4

2c+1=5b−12^{c+1}=5^b-1はmod  3\mod{3} で見ると(−1)c+1≡(−1)b−1mod  3(-1)^{c+1} \equiv (-1)^b-1 \mod{3}である．b,cb, c の偶奇で場合分けすると，これが成り立つのは b,cb,c が両方奇数のとき．よって正の整数 b′,c′b',c' により b=2b′−1b=2b'-1c=2c′−1c=2c'-1となる．つまり方程式は22c′=52b′−1−12^{2c'}=5^{2b'-1}-1である．次に mod  5\mod{5} で見ると，b=2b′−1>0b=2b'-1>0 だから(−1)c′≡4c′≡22c′≡−1mod  5(-1)^{c'}\equiv 4^{c'}\equiv 2^{2c'}\equiv -1 \mod{5}となる．よって c′c' は奇数．

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

考察5

24c′′−2=52b′−1−12^{4c''-2}=5^{2b'-1}-1をmod  8\mod{8} で見ると，c′′≥2c'' \geq 2 のとき 0≡52b′−1−1mod  80\equiv 5^{2b'-1}-1 \mod{8}となるが，55 べき 5,25,…5,25,\dots のmod  8\mod{8} は 5,1,…5,1,\dots を繰り返すから，（2b′−12b'-1 ：奇数より）右辺は常に 5−1≡4mod  85 - 1 \equiv 4\mod{8}である．よって c′′≥2c'' \geq 2 のときこの方程式は b′>0b'>0 となる整数解を持たない．

よって24c′′−2=52b′−1−12^{4c''-2}=5^{2b'-1}-1の b′,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) を求める．

mod  5\mod 5で考えると，右辺は 00 か 11 か 44 である．aaが奇数 2c+12c+1 のとき左辺は2a+5b≡22c+1≡(−1)c×2≡2,3mod  52^a+5^b \equiv 2^{2c+1} \equiv (-1)^c \times 2 \equiv 2,3 \mod{5}だから不適．よってaaは偶数だから，a=2ca=2c （cc は正の整数）とおける．すると方程式は5b=(n−2c)(n+2c)5^b = (n-2^c)(n+2^c)と変形でき，整数 0≤s<t0 \leq s < tによりs+t=bs+t=bn+2c=5sn+2^c=5^sn−2c=5tn-2^c=5^tとかけることがわかる．下2つの式より2c+1=5t−5s=5s(5t−s−1)2^{c+1}=5^t-5^s=5^s(5^{t-s} - 1)となり，左辺は55の倍数でないから右辺もそう．よってs=0s=0だから，2c+1=5b−12^{c+1}=5^b-1が成り立つ．

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

次にmod  5\mod 5 でみると，b>0b>0 より2c+1≡−1mod  52^{c+1}\equiv -1 \mod{5}となる．22 べき 2,4,8,16,…2,4,8,16,\dots を 55 で割った余りは 2,4,3,1,…2,4,3,1,\dots を繰り返すから，c+1c+1 は 4c′′−24c''-2 の形の整数（c′′c'' は正の整数）．よって正の奇数 bb と正の整数 c′′c'' が存在し 24c′′−2=5b−12^{4c''-2}=5^b-1 を満たす．

最後にmod  8\mod 8でみる．c′′≥2c'' \geq 2 と仮定すると上の式の左辺は 6464 の倍数だが，55 べき 5,25,…5,25,\dots を 88 で割った余りは5,1,5,1,…5,1,5,1,\dots を繰り返すから，5b−15^b-1 が 88 の倍数になるのは bb が偶数のときのみ，これは bb が奇数だったことに反する．

よってc′′=1c''=1，つまりc+1=4c′′−2=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=(n−1)(n+1)2^a=(n-1)(n+1)だから，0≤s<t0 \leq s<t となる整数 s,ts,t によりs+t=as+t=anー1=2snー1=2^sn＋1=2tn＋1=2^tとかける．すると 2=2t−2s=2s(2t−s−1)2=2^t-2^s=2^s(2^{t-s}-1) だから，s=1s=1 かつ t−s=1t-s=1 となり，a=s+t=3a=s+t=3 である．

まとめ

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

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

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