第6問
第6問
2a+5b が平方数となるような正整数の組 (a,b) を全て求めよ。
入力するときは次の手順に従って得られる A,B を入力せよ。
- a が小さい順に解を並べる。a が等しいときは, b の値が小さいほうを先に書く。
- こうして並べた解を (a1,b1),(a2,b2),⋯ とおく。
- n 番目の素数を pn として,
A=p1a1⋅p2a2⋯=2a1⋅3a2⋯pnan⋯B=p1b1⋅p2b2⋯=2b1⋅3b2⋯pnbn⋯
と定める。
整数問題の中でも,方程式の整数解を求める(いわゆるディオファントス方程式の)問題です.整数問題へのアプローチとしては基本的な3つの手法
を押さえておきましょう.今回は1つ目と3つ目をフル活用します.
考察
まずは問題を整理します.
問題
2a+5b=n2を満たす整数 n と正の整数 a,b の組 (n,a,b) を全て求めよ.
とりあえず小さい整数 a,b でいろいろ試してみると,次のような解が見つかります.
(n2,a,b)=(9,2,1),(9,3,0)このうち a,b>0 を満たすのは (a,b)=(2,1)です.またこれ以外の整数解はなかなか見つかりません.そこで整数解はこれらしかないのではないかというのを念頭に,因数分解やmodを使って情報を引き出していきます.
mod演算
初めにできることとして,いろいろな数で mod をとって情報を引き出します.基本的には「素数と(小さい)素数べき」として mod2,3,4,5,7,9,11,13 あたりを総当たりでみるのですが,今回は(5b という形から)mod5 でうまくいきます.
考察1
b>0 より,2a+5b=n2の mod5 をみると2a≡n2mod5となる.これは
- n≡0mod5 のとき 2a≡0mod5
- n≡1,4mod5 のとき 2a≡1mod5
- n≡2,3mod5 のとき 2a≡4mod5
となる.また 2 べき 2,4,8,16,… の mod5 は2,4,3,1,…を繰り返すから,2a≡0,1,4mod5 となるのは a が偶数のとき.
よって正の整数 c により a=2c となります.
因数分解
前の考察により 22c+5b=n2という方程式の整数解を考えればよいことがわかりました.これは5b=n2−22cとすることで因数分解でき,さらに情報を得ることができます.
考察2
5b=(n−2c)(n+2c)と因数分解すると,右辺の n±2c は( n≥0 としてよく,そのとき両方とも正の整数であることに注意すると)どちらも 5 べきとなることがわかる.よってn−2c=5sn+2c=5tとなる.(s,t は s+t=b を満たす 0 以上の整数.)
よって c,s,t がわかれば n,a,b もわかって問題が解けます.
ではこれらの式から n を消去して c,s,t の条件を求めましょう.
考察3
n−2c=5sn+2c=5tの差をとって2c+2c=5t−5sつまり2c+1=5s(5t−s−1)がわかる.n−2c<n+2c より s<t だから,5t−s−1 は整数.よってこの式は整数の因数分解を表しており,左辺は 5 の倍数でないから s=0 となる.すると s+t=b より t=b である.
つまり c>0,b>0 かつ2c+1=5b−1を満たす整数 (c,b) を求める問題に帰着できました.
mod 再び
方程式2c+1=5b−1の c>0,b>0 となる整数解を求めます.再びmod2,3,4,5,… で条件を絞り込んでいきます.
考察4
2c+1=5b−1はmod3 で見ると(−1)c+1≡(−1)b−1mod3である.b,c の偶奇で場合分けすると,これが成り立つのは b,c が両方奇数のとき.よって正の整数 b′,c′ により b=2b′−1c=2c′−1となる.つまり方程式は22c′=52b′−1−1である.次に mod5 で見ると,b=2b′−1>0 だから(−1)c′≡4c′≡22c′≡−1mod5となる.よって c′ は奇数.
よって正の整数 c′′ により c′=2c′′−1,c+1=4c′′−2 となり,方程式は24c′′−2=52b′−1−1となります.だんだんと情報が得られてきました.さらに mod で調べることができます.
考察5
24c′′−2=52b′−1−1をmod8 で見ると,c′′≥2 のとき
0≡52b′−1−1mod8となるが,5 べき 5,25,… のmod8 は 5,1,… を繰り返すから,(2b′−1 :奇数より)右辺は常に 5−1≡4mod8である.よって c′′≥2 のときこの方程式は b′>0 となる整数解を持たない.
よって24c′′−2=52b′−1−1の b′,c′′>0 となる整数解は c′′=1 のときの (b′,c′′)=(1,1) のみ,と解くことができます.これは元の方程式の (a,b)=(2,1) に対応するので,問題を解くことができました.
解答
以上を答案にまとめます.
第6問
2a+5b=n2を満たす整数 n と正の整数 a,b の組 (n,a,b) を求める.
mod5で考えると,右辺は 0 か 1 か 4 である.aが奇数 2c+1 のとき左辺は2a+5b≡22c+1≡(−1)c×2≡2,3mod5だから不適.よってaは偶数だから,a=2c (c は正の整数)とおける.すると方程式は5b=(n−2c)(n+2c)と変形でき,整数 0≤s<tによりs+t=bn+2c=5sn−2c=5tとかけることがわかる.下2つの式より2c+1=5t−5s=5s(5t−s−1)となり,左辺は5の倍数でないから右辺もそう.よってs=0だから,2c+1=5b−1が成り立つ.
これをmod3 でみると,(−1)c+1≡(−1)b−1mod3である.これが成り立つのは b,c がともに奇数のときのみ.
次にmod5 でみると,b>0 より2c+1≡−1mod5となる.2 べき 2,4,8,16,… を 5 で割った余りは 2,4,3,1,… を繰り返すから,c+1 は 4c′′−2 の形の整数(c′′ は正の整数).よって正の奇数 b と正の整数 c′′ が存在し 24c′′−2=5b−1 を満たす.
最後にmod8でみる.c′′≥2 と仮定すると上の式の左辺は 64 の倍数だが,5 べき 5,25,… を 8 で割った余りは5,1,5,1,… を繰り返すから,5b−1 が 8 の倍数になるのは b が偶数のときのみ,これは b が奇数だったことに反する.
よってc′′=1,つまりc+1=4c′′−2=2で,このとき (a,b)=(2,1)である.
以上より求める解は (a,b)=(2,1) である.また解答欄に入力する値は A=22=4B=21=2である.
また b=0 であるような解が (a,b)=(3,0) しかないことも次のようにして証明できます.
証明
方程式 2a+1=n2の整数解を求める.
2a=(n−1)(n+1)だから,0≤s<t となる整数 s,t によりs+t=anー1=2sn+1=2tとかける.すると 2=2t−2s=2s(2t−s−1) だから,s=1 かつ t−s=1 となり,a=s+t=3 である.
まとめ
整数問題の中でも,このような「方程式の整数解」を求めるタイプの問題には因数分解して素因数を見る,mod により情報を集めることが有効なことが多いです.よくある展開としては
- 因数分解された式=素数 or 素数べき という式を作ることで新しい方程式が得られる.
- 小さい数や素数で mod をとって両辺の値を比べることで変数の条件が絞れる.
といったものが多い印象です.また今回出てきた平方数の mod での値については,mod3,4 の結果が頻出なので覚えておきましょう.(→平方剰余と基本的な問題)