こんにちは。今回は2025東北大理系後期数学の大問1を解説します。よろしくお願いします。
問題
\(a=31243\) 、 \(b=17711\) とし、 \(a\) と \(b\) の最大公約数を \(d\) とする。このとき、以下の問に答えよ。
(1) \(d\) の値を求めよ。
(2) \(ax+by=d\) と \(|2x+y|\le 400\) を同時に満たす整数 \((x,y)\) の総数を求めよ。
答案例
(1)
自然数 \(A,B\) の最大公約数を \(gcd(a,b)\) で表す。ユークリッドの互除法により、 \(a,b\) の最大公約数は、
$$gcd(a,b)=gcd(31243,17711)$$
$$=gcd(31243-17711,17711)=gcd(13532,17711)$$
$$=gcd(13532,17711-13532)=gcd(13532,4179)$$
$$=gcd(13532-4179\times 4,4179)=gcd(995,4179)$$
$$gdc(995,4179-995\times 4)=gcd(995,199)=gcd(199\times 5,199)$$
$$=199$$
と計算できるので、 \(d=199\) である。
(2)
$$ax+by=d\tag{1}$$
(1)の結果から、
$$式(1)\Leftrightarrow 199\times 157\times x+199\times 89\times y=199\Leftrightarrow 157x+89y=1\tag{2}$$
と変形できる。(2)式より、
$$-21x\equiv 1 \pmod {89}$$
なので、 \(m\) を整数として \(-21x=89m+1\tag{3}\) とおくことができ、
$$式(3)\Leftrightarrow 0\equiv 5m+1 \Leftrightarrow 5m\equiv -1\pmod {21}$$
より、 \(n\) を整数として
$$5m=21n-1 \tag{4}$$
とおける。式(4)より、
$$0\equiv n-1\Leftrightarrow n\equiv 1 \pmod 5$$
ゆえ \(p\) を整数として \(n=5p+1\) と表せる。よって、(4)式より、
$$5m=21(5p+1)-1\Leftrightarrow m=21p+4$$
これを式(3)に代入して、
$$-21x=89(21p+4)+1\Leftrightarrow x=-89p-17\tag{5}$$
を得る。式(5)を式(1)に代入して、
$$157(-89p-17)+89y=1\Leftrightarrow y=157p+30 \tag{6}$$
を得る。式(5)(6)より、式(1)の一般解として
$$(x,y)=(-89p-17,157p+30) \tag{7}$$
が得られる。これを \(|2x+y|\le400\) に代入すると、
$$|2(-89p-17)+(157p+30)|\le 400\Leftrightarrow |21p+4|\le 400$$
$$\Leftrightarrow -400\le 21p+4\le 400\Leftrightarrow -404\le 21p\le 396$$
$$-19-\frac{5}{21}\le p\le 18+\frac{6}{7}\Leftrightarrow -19\le p\le 18\tag{8}$$
と変形でき、-19以上18以下の整数の個数は38なので、求める個数は38である。
解説
ユークリッドの互除法と一次不定方程式がテーマの整数問題です。やること自体は教科書の例題レベルの平易なものですが、出てくる整数がデカいので、計算ミスがないよう丁寧に計算しましょう。
(1)
31243と17711の最大公約数を求める問題です。最大公約数を求める方法は、①がんばって探す②ユークリッドの互除法を利用する、の2通りあります。1~3桁の小さい数のペアなら両方割り切る自然数をがんばって探す方が効率的ですが、試験問題で出題されるようなデカい数の場合は直接求めるのは無謀なので、互除法を利用するのが無難です。
ユークリッドの互除法は、「自然数 \(A\) を自然数 \(B\) で割った商と余りをそれぞれ \(q,r\) とすると、(AとBの最大公約数)=(Bとrの最大公約数) が成立する」という定理です。この定理は文面だけ眺めてもよくわからんので実際に手を動かして慣れていくことが重要です。
練習として、42と77の最大公約数を互除法を用いて求めてみます。77=42×1+35なので、77を42で割った商は1、余りは35となります。これをユークリッドの互除法に当てはめれば、(42と77の最大公約数)=(42と35の最大公約数) ということになります。42と77の最大公約数をgcd(42,77)のように表すと、
$$gcd(42,77)=gcd(42,35)$$
のように表せます。これを繰り返すと、
$$gcd(42,77)=gcd(42,35)=gcd(7,35)=gcd(7,7\times 5)=7$$
と最大公約数を計算できるわけです。
同じ計算を(31243,17711)で実行すると、
$$gcd(31243,17711)=199$$
となります。念のため検算すると 31243=199×157、17711=199×89 となるので、d=199で間違いなさそうです。
(2)
「\(ax+by=d\) と \(|2x+y|\le 400\) を同時に満たす整数 \((x,y)\) の総数を求めよ。」というお題です。
計算を始める前に、最終的なゴールについてイメージを固めておきましょう。与式 \(ax+by=d\) は(x,y)の一次方程式の形式なので、xy平面では直線となります。この直線上で(整数、整数)となっている点が本式の整数解(x,y)ということになります。この整数解は整数 \(p\) を用いて \((x,y)=(pの一次式,pの一次式)\) といった具合に余すことなく表現でき、コレを与式 \(|2x+y|\le 400\) に代入すると \(p\) に関する不等式が得られます。得られた不等式をpについて解けば、２つの与式を同時に満たす整数(x,y)の条件がpを経由して求まるので、あとは不等式を満たす整数pの個数をカウントすれば終わり、という流れです。
まず、与式 \(ax+by=d\) ですが、両辺を199で割ると \(157x+89y=1\) と変形できます。これはxy平面で直線を表す方程式なので、この直線上でxとyがともに整数となるような点（=格子点）が本式を満たす整数解(x,y)ということになります。このように、整数の未知数を複数個含む一次方程式を「一次不定方程式」、その整数解を「一般解」と呼びます。
\(157x+89y=1\) の一般解を求めます。今回はmodを利用した解法を紹介します。右辺の係数(157,89)の小さい方89に注目し、 \(\pmod {89}\) を適用すると、
$$157x+89y\equiv 1\Leftrightarrow 68x\equiv1\Leftrightarrow -21x\equiv 1 \pmod {89}$$
となるので、 \(157x+89y=1\) を満たす \(x\) は \(m\) を整数として \(-21x=89m+1\) と表せることが必要です。同様に、
$$-21x\equiv 89m+1\Leftrightarrow 0\equiv 5m+1 \Leftrightarrow 5m\equiv -1\pmod {21}$$
$$\Rightarrow 5m=21n-1$$
$$5m\equiv 21n-1 \Leftrightarrow 0\equiv n-1\Leftrightarrow n\equiv 1 \pmod 5$$
$$\Rightarrow n=5p+1$$
というふうに整数解に関する必要条件を書き下すことができます。最終的に得られた整数pに関する式を直前のnに関する式に代入すると、
$$5m=21(5p+1)-1\Leftrightarrow 5m=21\times 5p+20\Leftrightarrow m=21p+4$$
となりこれをもう一個前の式に代入すれば、
$$-21x=89(21p+4)+1\Leftrightarrow x=-89p-17$$
と求まります。この式により、\(157x+89y=1\) を満たす整数 \(x\) は、整数 \(p\) を用いて \(x=-89p-17\) と表せる必要があることがわかります。 \(y\) については、
$$157(-89p-17)x+89y=1\Leftrightarrow y=157p+30$$
より、yに関する必要条件が得られます。以上より、与式 \(ax+by=d\) を満たす整数(x,y)は整数pを用いて \((x,y)=(-89p-17,157p+30)\) と表せる必要があります(→必要条件)。逆に、
$$157(-89p-17)+89(157p+30)=-157\times 89p+89\times 157p-157\times17+89\times 30=1$$
より、\((x,y)=(-89p-17,157p+30)\) は与式を満たす(→十分条件)ので、\(ax+by=d\) の一般解(→必要十分条件)は \((x,y)=(-89p-17,157p+30)\) ということになります。上の答案例では十分性の検討は省いていますが、高校の教科書の例題とかでも省略されてるので多分OKだと思います。
次に、\((x,y)=(-89p-17,157p+30)\) をもう一方の与式 \(|2x+y|\le 400\) に代入してみます。
$$|2(-89p-17)+(157p+30)|\le 400 \Leftrightarrow |-21p-4|\le 400$$
$$\Leftrightarrow |21p+4| \le 400 $$
$$\Leftrightarrow -400 \le 21p+4 \le 400$$
$$\frac{-404}{21}\le p\le \frac{396}{21}=\frac{132}{7}$$
となり、 \(\frac{-404}{21}=-19.2…\)、 \(\frac{132}{7}=18.8…\) なので、整数pに関する上式は
$$\Leftrightarrow -400 \le 21p+4 \le 400\Leftrightarrow -19\le p\le 18$$
と変形でき、これを満たすpの個数は-19,-18,…,17,18の38個なので、求める個数は38個ということになります。
以上です。この手の問題はやること自体は単純ですが、途中で何やってるかわからなくなりがちなので、どこに向かって計算しているのかよく意識して計算を進めるとよいでしょう。
お疲れ様でした。
コメント