Evolton

名古屋大学 2004年度 前期日程 第2次学力試験 整数・数列理系数学 第4問(b)

選択問題 (b)

正の整数aとbが互いに素であるとき,
正の整数からなる数列{xn}を
x1=x2=1,xn+1=axn+bxn−1 (n≧2)で定める.
このときすべての正の整数nに対して
xn+1とxnが互いに素であることを示せ.

難易度5/ 10計算量4/ 10目安15分

整数、数列、論証・証明 数学的帰納法、最大公約数、式変形

方針

隣り合う2項が互いに素であることだけを帰納法で示そうとすると、漸化式の bxn−1 の部分を処理するために b との互いに素性も必要になる。そこで、xn と xn−1 が互いに素であること、さらに xn と b が互いに素であることを同時に帰納法で示す。a と b が互いに素である条件は、xn+1 と b の共通約数を調べるところで使う。

解答

次の2つの主張を同時に帰納法で示す。 (A)xn と xn−1 は互いに素である, (B)xn と b は互いに素である. x1=x2=1 であるから、n=2 ではどちらも成り立つ。

ある n≧2 で、xn と xn−1 が互いに素であり、かつ xn と b が互いに素であると仮定する。まず xn+1 と b が互いに素であることを示す。d を xn+1 と b の公約数とする。漸化式 xn+1=axn+bxn−1 より、d は b を割り、また xn+1 を割るので、d∣axn である。ところが a と b は互いに素であり、xn と b も互いに素である。d は b の約数だから、d は a とも xn とも互いに素である。よって d=1 である。したがって xn+1 と b は互いに素である。

次に xn+1 と xn が互いに素であることを示す。e を xn+1 と xn の公約数とする。このとき e∣xn+1−axn=bxn−1 である。一方、e∣xn であり、仮定より xn と xn−1 は互いに素であるから、e と xn−1 も互いに素である。したがって e∣b でなければならない。

しかし、上で示したように xn+1 と b は互いに素であり、e は xn+1 も割る。よって e=1 である。したがって xn+1 と xn は互いに素である。

以上により、帰納法で任意の n≧1 について xn+1 と xn は互いに素である。

別解

解法2(合同式と最大公約数の降下)

方針

漸化式を法bで見るとxnとbが互いに素であることが一度に分かる。その後、隣接2項の最大公約数を漸化式で1段ずつ前へ戻し、初期値まで降下させる。

解答

漸化式を法bで見るとxn+1≡axn(modb).x2=1だから、帰納的にxn≡an−2(modb)(n≧2)である。aとbは互いに素なのでgcd⁡(xn,b)=1(n≧2)を得る。

次にn≧2についてgcd⁡(xn+1,xn)=gcd⁡(axn+bxn−1,xn)=gcd⁡(bxn−1,xn).gcd⁡(b,xn)=1であるからgcd⁡(bxn−1,xn)=gcd⁡(xn−1,xn).よって同じ操作を繰り返せばgcd⁡(xn+1,xn)=gcd⁡(xn,xn−1)=⋯=gcd⁡(x2,x1)=1.したがって、すべての正の整数nについて
xn+1とxnは互いに素である。

総評

難度5、計算量4。目安時間は14〜18分。最大公約数と漸化式を組み合わせる標準的な証明問題である。隣り合う項だけの互いに素性を示そうとすると、bxn−1 の b が邪魔になるため、xn と b も互いに素であることを同時に示すのが要点である。a,b が互いに素である条件は、xn+1 と b の公約数が axn を割る場面で使う。証明では、公約数を1つ置き、どの式を割るかを順に書くと論理が崩れにくい。

Evolton Pro

月額
2,480円(税込)
保存・印刷
公開過去問PDF・オーダーメイド問題集PDF
プランを確認・登録

冊子PDFで見る名大の整数の問題で問題集を作る

出典: 名古屋大学 2004年度 前期 数学。問題文はHTML表示のために再入力・数式組版しています。