(解いてみた その3) Shortlist 2013 N3

今回はIMO shortlist(IMOの候補問題)の整数問題からです。すごく面白い問題だったので書こうと思いました。

問題3.

正の整数 $ n $であって, $ n^4+n^2+1 $ の最大の素因数と, $ (n+1)^4  + (n+1)^2 + 1$ の最大の素因数が等しいようなものが無限に存在することを示せ。

解答

$ f(n) = n^2+n+1 $とおく。このとき, $f(n^2) = n^4+n^2 + 1$であって, 因数分解すると $f(n^2) = f(n)f(n-1)$であることが分かる。そこで, $f(n)$の最大の素因数を$ p_n $とする。 (便宜上, $p_0 = 1$とする。)問題は$p_{n^2} = p_{(n+1)^2}$となる$ n $が無限に存在するかである。

このとき, $f(n^2) = f(n)f(n-1)$から $p_{n^2} = \max{\{ p_n, p_{n-1}\}}$ がすべての$n\in \mathbb{N}$ で成り立つことに注意すると, 次のことが分かる:

($\ast$) ・・・ いかなる自然数$ K $をあたえても, $ i>j>M $を満たす自然数$ i,j $であって, $p_{i} = p_{j}$を満たすものが存在する。

もし, $p_{n^2} = p_{(n+1)^2}$を満たす$ n $が有限個だとするなら, そのような $ n $ の最大値を$ N_0 $とおく。このとき, $ m>N_0 $を自然数$ m $が満たすならば, 常に$p_{m^2} > p_{(m+1)^2}$ または $p_{m^2} < p_{(m+1)^2}$ を満たさなければならない。

素数の真の無限減少列を作ることはできないから, $ m>N_0 $ なるすべての$ m $で 常に $ p_{m^2} > p_{(m+1)^2} $ となることはあり得ない。したがって, ある $ m_0 > N_0 $が存在して,  $p_{m_{0}^2} < p_{(m_0 + 1)^2}$ となる。

$p_{m_0}\leq  \max{\{ p_{m_0}, p_{m_0 -1}\} } < \max{\{ p_{m_0+1}, p_{m_0}\}} $ であるから, 右辺は$p_{m_0}$に等しくなっては成らないので, $\max{\{ p_{m_0+1}, p_{m_0}\} } = p_{m_0+1}$が分かる。すると, $p_{m_0}<p_{m_0 + 1}$ となる。

このとき, $p_{(m_0+1)^2} > p_{(m_0 + 2) ^2}$であると仮定すると不合理である。なぜなら,  $p_{(m_0+1)^2} = p_{m_0+1}$であったから, $p_{m_0 + 1} > \max{\{ p_{m_0+2}, p_{m_0+1}\} }$ は成り立たない。よって, $p_{(m_0+1)^2} < p_{(m_0+2)^2}$ となり, ここから同様な議論より $ p_{m_0+1} < p_{m_0+2}$ が分かる。

帰納的に, $m_0\leq n$ を満たす任意の$ n $に対して, $p_{n} < p_{n+1}$ でなければならないことが分かる。これは, $(\ast)$ で$K=m_0$とした内容に矛盾する。

よって$p_{n^2} = p_{(n+1)^2}$ を満たす$ n $が無限に存在する。