【第1回東大実戦】文系数学第1問：整数
2020年度第1回東大実戦 第1問は整数問題でした。典型的な形の問題から入り、後半では整数を積の形に変換することに気づけたか、さらにきちんと場合わけができたかで差がついたと思います。
難易度、所感はこちら↓
問題
(1) \( 23x + 19y = 2\) を満たす整数\(x,y\)をすべて求めよ。
(2) 1以上437以下の整数\(n\)で、\(n^2\)を437で割った余りが1であるものを全て求めよ。
方針
(1)は似たような形を見たことがある方がほとんどだと思います。
整数解を1つ見つける→式同士で引き算
の順番でしたね。そして見つける際にユークリッドの互除法を使うのでした。
(2)は一見(1)と異なる趣旨の問題にも見えますが、437 = 19×23 の素因数分解にたどり着ければ(1)の内容が使えることに気づけます。
解答
整数解
$$ 23 x + 19 y = 2 $$ $$ \Leftrightarrow 4 x + 19 (x + y) = 2 $$ $$ \Leftrightarrow 4x + 16 (x+y) + 3(x+y) = 2 $$ $$ 4(5x+4y) + 3(x+y) = 2 $$ というように、2つのカタマリの係数が小さくなるように変形して行きます。そして、ある程度係数が小さくなるとカタマリの整数解がわかるので、連立方程式が解けたら終わりです。$$ \left\{ \begin{array}{1} 5x + 4y = 2 \\ x + y = -2 \end{array} \right. $$ $$ \Leftrightarrow \color{red}{x = 10 , y = -12} ・・・[検] $$
【ここまでは解答に書かなくてよい】
\( x = 10, y = -12 \) のとき、\( 23x + 19y = 230 – 228 = 2 \) は確かに成り立つので、これは求める解の1つである。 【検算ポイント】
ここで、$$ \left\{ \begin{array}{1} 23x+19y = 2 \\ 23×10+19×( – 12)= 2 \end{array} \right. $$ の辺々を引くと、$$ 23(x -10) + 19 (y+2) = 0 $$ $$ \Leftrightarrow 23(x – 10) = – 19(y+ 12) $$ 23と19は互いに素であるので、整数\(k\)を用いて $$ \color{red}{x-10 = 19k , y+ 12 = -23k} $$ と表せる。以上より、求める整数解は \( (x,y) = (19k + 10, y = -23k – 12) \) (\(k\)：整数)
437 = 19×23
まずは問題文を数式に変換しないことには始まりません。
\(n^2 \)を437で割って1余るような\(n\)は、商を\(A\)とすると、$$ n ^2 = 437 A + 1 $$
ここで整数問題の定跡を思い出してください。
整数問題は「積」の形にしたい！！
積の形を念頭に変形すると、$$ n^2 -1 = 437 A $$ $$ \Leftrightarrow \color{red}{(n-1)(n+1) = 19×23×A} $$
積の形まで持っていければ、あとは素因数の割り振りですね！
ユークリッドの互除法により、\((n-1, n+1) = (n-1, 2) \)なので、\(n-1 \)と\( n+1 \)の最大公約数は1 または 2である。
\( (i) \) ：\( n-1 \) が19, 23の素因数を持つとき、整数\(a\)を用いて、\( n-1 = 19×23×a = 437 a \) と表せる。
これを満たす1以上437以下の整数\(n\)は、\(a=0\)のときの\(\color{red}{n=1}\)のみである。
\((ii) \) ： \( n+1 \) が19, 23の素因数を持つときも同様にして、\(\color{red}{ n = 436} \)
\( (iii) \) ： \( n-1 \)が19の素因数、\( n+1 \)が23の素因数を持つとき、整数\(a,b \) を用いて、$$ \left\{ \begin{array}{1} n-1 = 19a \\ n+1 = 23b \end{array} \right. $$ これより、辺同士を引くと $$ \color{red}{23b + 19 (- a) = 2} $$ (1)より、この式を満たす整数\(a,b\)は\((a,b) = ( 23k + 12, 19k + 10) \)
つまり、\( n = 19a + 1 = 23b – 1 = 437k + 229 \)なので、これを満たす1以上437以下の整数は\(k = 0\)のときの\(\color{red}{n = 229} \)である。
\( (iv) \) ：\( n-1 \) が23の素因数、\( n+1 \)が19の素因数を持つとき、整数\(c,d \)を用いて、 $$ \left\{ \begin{array}{1} n – 1 = 23 c \\ n + 1 = 19 d \end{array} \right. $$ これより、辺同士を引くと $$ \color{red}{23 (- c) + 19 d = 2} $$ (1)より、この式を満たす整数\(c,d\)は\((c,d) = (-19k – 10, -23k – 12)\)
つまり、\( n = 23c+1 = 19 d – 1 = – 437 k – 229 \) であるので、これを満たす1以上437以下の整数は\(k = -1 \)のときの\( n = 437 – 229 = \color{red}{208} \)である。
検算
求めた値が4つしかないので、2乗して437で割るのも1 〜2分程度で済みそうです。
\( n = 1, 436 \)のとき、\( \color{red}{mod 437} \) で考えると、$$ 1^2 \equiv 1, {436}^2 \equiv (-1)^2 \equiv 1 $$
\( n = 208, 229 \)のとき、2乗の値はそれぞれ43264, 52441 であり、$$ 43264 = 99×437 + 1, 52441 = 120×437 + 1 $$
以上より、全て437で割って1余るという条件を満たしていることが分かります。
実践では
他の問題の難易度にもよりますが、標準的な問題であるように思えます。
(1) でユークリッドの互除法を知らなかった場合は少し求値が難しいですが、高々10〜20個の値を試して探すことで答えが求まります。
入試では素早く・キレイに答えが求まるに越したことはありませんが、それができないときでも泥臭く点を取りに行く力は必要です。整数問題のこの問題の形「\(ax + by = c\)の整数解」を知っている方は、答えが\(\color{red}{a,b}\)個ごとにくることも知っていると思いますので、泥臭くてもまだ頑張りどころがあります！
(2)では始めるときに437=19×23に気づいていなくても進められますし、場合分け\((ii)\)のところまでは(1)と独立に解答できます。したがって、(1)が解けなくても(2)を諦める、といってことでは取れるはずの部分点を逃してしまいますので、ぜひこのことは覚えておいてください。
整数の実践問題
下の記事でも整数の実践的な問題を紹介していますので、ぜひご覧ください！
