スダンダードな整数問題 – 2019年東大 数学 第1問

2024年1月8日2024年2月18日

2019年東大 数学 第1問 は一見ぎょっとしますが、実は標準的な手法で比較的サクッと解けます。問題文は以下のとおりです。

n を 1 以上の整数とする。

(1) n²+1 と 5n²+9 の最大公約数 d_nを求めよ。
(2) (n²+1)(5n²+9) は整数の2乗にならないことを示せ。

　文字式の最大公約数とか、考えたくもありありませんが、比較対象の式が因数分解できないことから、最大公約数 d_n は n の式ではない固定的な数であるかも知れません。案外あっさり解けるかも知れませんので、まずはチェックしましょう。

2019年東大 数学 第1問 の解法

　比較対象の2つの式の次数はどちらも２で、しかも1次の項がないところから、

5 n^2 + 9 = 5(n^2 +1) +4

と思いつくことが第1歩です。このように変形できれば、2つの式の最大公約数 d_nは4の約数であることが、ソッコーわかります。実際、

\begin{aligned}
n^2 +1 & = ad_n \\
 5n^2+9 & = bd_n \\
 & (a,b\text{は自然数}) 
\end{aligned}

と置くとき、

bd_n = 5ad_n +4

なので

(b-5a) d_n = 4

であり、 d_n は4の約数すなわち、１か２か４のいずれかです。予想通り d_nは n と関係ない値になりました。

　したがってまず n が偶数のとき、 n²+1 も 5n²+9 も奇数になるので、 d_n は１しかあり得ないことがただちにわかります。

　つぎに n が奇数の場合ですが、 d_n が４の約数のいずれかであることから、 n を4の剰余類で考えてみます。すると

\begin{aligned}
n & \equiv 1 ( \mod 4) \text{　または} \\
n  & \equiv 3 ( \mod 4)
\end{aligned}

なので、

n^2 \equiv 1 ( \mod 4)

です。よって、

n^2+1 \equiv 5 n^2 +9 \equiv 2( \mod 4)

であり、 n²+1 も 5n²+9 も２の倍数だが4では割り切れないので、 d_n =2 です。

　以上をまとめると、

d_n = \left \{  \begin{aligned}& 1 &  (n \text{が偶数})  \\ 
  &  2 & (n \text{が奇数})  \end{aligned} \right .

を得ます。

2019年東大 数学 小問2の解法

　まず、 n²+1 が絶対に自然数の２乗にならないことに気が付きましょう。実際、もしある自然数 m が存在して

n^2 + 1 = m^2

が成り立つとすると、

m^2 - n^2 = 1

なので

(m-n) (m+n)= 1

すなわち

\left \{
\begin{aligned}
m-n=1 \\
m + n= 1
\end{aligned}
\right .

であり、 m=1, n=0 となりますが、これは n が１以上の整数であることに矛盾します。

　小問１により n が偶数のとき n²+1 と 5n²+9 は互いに素なので、 (n²+1)(5n²+9) が整数の２乗になるためには n²+1 と 5n²+9 の双方が平方数になる必要が有ります（もしどちらかが平方数でない場合、その数の素因数の中に奇数個のものがあり、その素数は (n²+1)(5n²+9) の中でも同じ奇数個しか無いので、 (n²+1)(5n²+9) は平方数ではない）。ところが、 n²+1 は平方数でないので (n²+1)(5n²+9) は平方数でないことがわかりました。

　次に n が奇数のときです。小問1より、 \displaystyle\frac{n^2+1}2 と \displaystyle\frac{5 n^2 +9}2 は互いに素なので、 n が偶数のときと同様に、 \displaystyle\frac{n^2+1}2 が平方数にならないことが証明できれば、一件落着です。

　ところが、 n=7 のとき、 \displaystyle\frac{7^2+1}2=5^2 です。世の中そんなに甘くありませんでした orz。

　それではということで気を取り直して、ある自然数 m が存在して \displaystyle\frac{n^2+1}2 = m^2 であったときに、 \displaystyle\frac{5 n^2 +9}2 = 5m^2 +2 が平方数にならないことを証明することにします。

　ある自然数 l が存在して

5 m^2 + 2 = l^2

と置いた時に矛盾が出ることを示したいのですが、文字列を左辺に集めて

l^2 - 5m^2 =2

と式変形してみたときに左辺は因数分解できないので、 n²+1 が平方数でないことを証明したときと同じ方法は通用しません。

　これは一筋縄ではいかないことが分かってきました。ここで、ある数が素数であるかどうかの判定によく剰余類を利用していたことを思い出しましょう。例えば2018年京大 数学 第2問当たりがそうですが、このやりかたが平方数の判定に使えないか、試してみることにします。

　これまでの流れから、4の剰余類を考えます。 a を自然数とします。

\begin{aligned}
a \equiv 0 ( \mod 4)  \text{　なら　} a^2 \equiv 0  ( \mod 4) \\
a \equiv 1 ( \mod 4)  \text{　なら　} a^2 \equiv 1  ( \mod 4) \\
a \equiv 2 ( \mod 4)  \text{　なら　} a^2 \equiv 0  ( \mod 4) \\
a \equiv 3 ( \mod 4)  \text{　なら　} a^2 \equiv 1  ( \mod 4) \\

\end{aligned}

なので、ある自然数 b が平方数であるための必要条件は

b \equiv 0(\mod 4) \text{　または　}  b \equiv 1(\mod 4)

です。

　ところが n=2j+1 （j は非負整数）のとき、

\begin{aligned}
 m^2 & =\frac{n^2 + 1 }2  \\
 & =\frac{(2j+1)^2 + 1 }2  \\
& = 2j^2+2j +1 \\
 &  = 2j(j+1) +1 \\
 & \equiv 1 ( \mod 4)

\end{aligned}

なので（j と j+1 の一方は必ず偶数であることに注意）

5m^2+2 \equiv 3 (\mod 4)

です。すなわち、 5m²+2 は平方数ではないことが証明できました。

　ゆえに n が奇数の時も (n²+1)(5n²+9) が整数の２乗にならないことが証明できました。

解法のポイント

　まず、 n が自然数の時に n²+1 が平方数にならないことに気が付きましょう。これは重宝する性質なので、覚えておいてください。

　一般に平方数かどうかの判定は素数かどうかの判定と同様に、難しいです。入試問題で突拍子もないことを要求されることは普通ないので、特段のヒントがない場合は、剰余類を使って判定してみましょう。