JMO予選1990問9

正の整数\(n\)に対し,

$$a_n=n^2+50, \ d_n={\rm{gcd}}(a_n,a_{n+1})$$

とする.\(n\)が正の整数全体を動くとき,\(d_n\)の最大値を求めよ.ここで,\({\rm{gcd}}(a,b)\)で\(a\)と\(b\)の最大公約数を表す.

【思考・方針】

下手なことをせず,\(a_n,a_{n+1}\)は\(n\)の式で表せます.あとは最大公約数を求めるときの基本方針の1つである互除法を使えば解決です.

\begin{eqnarray} {\rm{gcd}}(a_n,a_{n+1}) &=&{\rm{gcd}}(n^2+50,n^2+2n+51)\cdots①\\ &=&{\rm{gcd}}(n^2+50,2n+1)\cdots②\\ &=&{\rm{gcd}}(4n^2+200,2n+1)\cdots③\\ &=&{\rm{gcd}}(201,2n+1)\cdots④ \end{eqnarray}

と計算できますね.

①は一般項から,②,③は互除法です.

③に式変形をするところで戸惑うかもしれませんが,これは,②で互除法を使おうとすると分数式が出てしまうので,\(2n+1\)が奇数であるから,\(n^2+50\)を\(4\)倍しても最大公約数は代わらないことを利用した式変形です.

ここまでくれば,\(d_n={\rm{gcd}}(201,2n+1)\)の最大値は\(201\ (2n+1\)が\(201\)の倍数のとき)とわかります.実際に

\begin{eqnarray}a_{100}&=&10050=201\times50\\ a_{101}&=&10251=201\times51 \end{eqnarray}

と計算して確かめておくとよいでしょう.文字の絡んだ互除法になれたい人は以下の類題でも考えてみてください.記念すべき第1回IMOの第1問です.

Q.\(\ \ \)任意の正の整数に対し,\(\frac{21n+4}{14n+3}\)は既約分数であることを示せ.

(IMO1959問1)

【略解】

\(21n+4\)と\(14n+3\)の最大公約数が\(1\)であることを確かめればいいですね.互除法を使うと

\begin{eqnarray}{\rm{gcd}}(21n+4,14n+3)={\rm{gcd}}(7n+1,14n+3)={\rm{gcd}}(7n+1,1)=1 \end{eqnarray}

となりますから,これで無事,示せました!

ちなみに,互除法を使うとこんな簡単に示せてしまう問題で互除法を使っていいのか!という人は,

\begin{eqnarray} -2(21n+4)+3(14n+3)=1\cdots①\end{eqnarray}

であり,もし,\({\rm{gcd}}(21n+4,14n+3)=d\ge 2\)とすると,\(21n+4,14n+3\)は両方\(d\)の倍数なので①の左辺は\(d\)の倍数となるが,①の右辺は\(d\)の倍数でないというふうに説明した方がいいかもしれません.

記念すべき第1回IMOの最初の1問は今と比べ物にならないくらい簡単なのですね.

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です