Evolton

東京大学 2002年度 前期日程 第2次学力試験文系数学 第2問

nは正の整数とする.
xn+1をx2−x−1で割った余りをanx+bnとおく.

(1) 数列an,bn,n=1,2,3,⋯,は
{an+1=an+bnbn+1=an
を満たすことを示せ.

(2) n=1,2,3,⋯に対して,
an,bnは共に正の整数で,
互いに素であることを証明せよ.

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

数と式、数列、整数 漸化式の変形、数学的帰納法、最大公約数、式変形

方針

余りだけを追うため、x2≡x+1(modx2−x−1) と見て計算する。xn+2=x⋅xn+1 なので、余り anx+bn にxを掛けてから x2 を x+1 に置き換えれば漸化式が出る。(2)は初期値 a1=b1=1 を確認し、正の整数性は漸化式で、互いに素であることは公約数が一段前の an,bn も割ることから帰納法で示す。

解答

(1) xn+1 を x2−x−1 で割った余りが anx+bn であるから、ある多項式 Q(x) を用いて xn+1=(x2−x−1)Q(x)+anx+bn と書ける。両辺にxを掛けると xn+2=x(x2−x−1)Q(x)+anx2+bnx である。したがって、xn+2 を x2−x−1 で割った余りは、anx2+bnx を同じ式で割った余りに等しい。

ここで x2−x−1=0 とみなして余りを計算すれば x2≡x+1 である。よってanx2+bnx≡an(x+1)+bnx=(an+bn)x+anである。したがって an+1=an+bn,bn+1=an を得る。

(2)
まず n=1 では、x2 を x2−x−1 で割った余りは x+1 である。したがって a1=1,b1=1 であり、どちらも正の整数で互いに素である。

次に、ある n で an,bn が正の整数であるとする。このとき(1)より an+1=an+bn,bn+1=an であるから、an+1,bn+1 も正の整数である。よって帰納法により、すべての n で an,bn は正の整数である。

互いに素であることを示す。an,bn が互いに素であると仮定し、d を an+1,bn+1 の公約数とする。このとき d∣an+1=an+bn,d∣bn+1=an である。したがって d∣(an+bn)−an=bn である。つまり d は an,bn の公約数である。仮定より an,bn は互いに素なので d=1 である。

よって an+1,bn+1 も互いに素である。初期値 a1=b1=1 から帰納法により、すべての正の整数 n について an,bn は互いに素である。

【余りの係数を更新する写像】

別解

解法2

方針

係数の組をフィボナッチ数列と同定する。連続するフィボナッチ数の最大公約数は、ユークリッドの互除法で一つ前の組へ戻すと1になる。

解答

(1) xn+1≡anx+bn(modx2−x−1)の両辺に x を掛け、x2≡x+1 を用いるとxn+2≡(an+bn)x+an.余りの一意性からan+1=an+bn,bn+1=an.(2)F1=F2=1, Fj+2=Fj+1+Fj とする。(1)と(a1,b1)=(1,1)から帰納的にan=Fn+1,bn=Fnである。したがって両者は正の整数である。

またユークリッドの互除法によりgcd⁡(Fn+1,Fn)=gcd⁡(Fn,Fn+1−Fn)=gcd⁡(Fn,Fn−1).これを繰り返すとgcd⁡(Fn+1,Fn)=gcd⁡(F2,F1)=1.よって an,bn は互いに素である。

総評

難度は10段階中5、計算量は10段階中4。目安時間は12分。採点ポイントは、x2≡x+1 として余りだけを更新すること、初期値 a1=b1=1 を明記すること、互いに素の証明で公約数を一段前へ戻すことである。誤りやすいのは、xn+1 と xn+2 の添字を1つずらすこと、また正の整数性と互いに素性を同じ帰納法の中で曖昧に混ぜることである。

Evolton Pro

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

冊子PDFで見る東大の数と式の問題で問題集を作る

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