スポンサーリンク

2002東京大学・文理共通[第2問整数・数列] 余り、互いに素、数学的帰納法、背理法

数学(大学入試問題)

【2002東京大学・第4問・文理共通】

\(n\) は正の整数とする.\(x^{n+1}\) を \(x^2-x-1\) で割った余りを \(a_{n}x+b_{n}\) とおく.

(1) 数列 \(a_{n}\)、\(b_{n}\)、\(n = 1 , 2 , 3 , \cdots\) は

\(\begin{cases}a_{n+1}=a_{n}+b_{n}\\b_{n+1}=a_{n}\end{cases}\)

を満たすことを示せ.

(2) \(n = 1 , 2 , 3 , \cdots\) に対して、 \(a_{n}\)、\(b_{n}\) は共に正の整数で、互いに素であることを証明せよ.

(1) 考え方

たしかめ算について

小学生で割り算を学習した際に、「たしかめ算」を学習したことかと思います。

例:\(14\) を \(4\) で割ると、商が \(3\) で余りが \(2\) のとき

『 \(14=4\times3+2\) 』とかける式のことです.

一般に、『割られる数(式)=割る数(式)×商+余り』の関係が成り立ちます.

こんな当たり前だと思うかもしれませんが、ちなみに「たしかめ算」を利用して考えるのが「剰余の定理」や「因数定理」になります.

本問においても解答の1行目は「たしかめ算」からスタートです!

 

(1) 解答

\(x^{n+1}\) を \(x^2-x-1\) で割った商を \(Q(x)\) とおく.

このとき、

\(x^{n+1}=(x^2-x-1)\cdot Q(x)+a_{n}x+b_{n}\) ・・・① とおける.

①の両辺を \(x\) 倍すると、

\(x^{n+2}=x(x^2-x-1)\cdot Q(x)+a_{n}x^2+b_{n}x\)

\(a_{n}x^2+b_{n}x\) は \(x^2-x-1\) でまだ割れる!

ここで、\(a_{n}x^2+b_{n}x=a_{n}(x^2-x-1)+(a_{n}+b_{n})x+a_{n}\) であるから、

\(x^{n+2}=x(x^2-x-1)\cdot Q(x)+a_{n}(x^2-x-1)+(a_{n}+b_{n})x+a_{n}\)

したがって、

\(x^{n+2}=(x^2-x-1)\left\{x\cdot Q(x)+a_{n}\right\}+(a_{n}+b_{n})x+a_{n}\) ・・・②

②において、\((a_{n}+b_{n})x+a_{n}\) は高々 \(1\) 次式であるから、これ以上 \(x^2-x-1\) では割れない.

ゆえに、\(x^{n+2}\) を \(x^2-x-1\) で割った余りが \((a_{n}+b_{n})x+a_{n}\) であるから、

\(\begin{cases}a_{n+1}=a_{n}+b_{n}\\b_{n+1}=a_{n}\end{cases}\)

が成立する.

(2) 考え方

(2)の問題は、

Ⅰ. \(a_{n}\)、\(b_{n}\) は共に正の整数であることの証明.

Ⅱ. \(a_{n}\)、\(b_{n}\) は互いに素であることを証明.

の2つの問題がある.もちろん同時に扱える方はそれに越したことはないが、ここでは丁寧に、それぞれの証明を考える.

\(n = 1 , 2 , 3 , \cdots\)(自然数) に対しての証明

⇒ 数学的帰納法を利用

(2) 解答

Ⅰ. \(a_{n}\)、\(b_{n}\) は共に正の整数であることの証明

数学的帰納法を用いて証明する.

(ⅰ) \(n=1\) のとき

\(x^2=(x^2-x-1)\times 1 +x+1\) より、\(x^2\) を \(x^2-x-1\) で割った余りは \(x+1\) であるから、\(a_{1}=1\)、\(b_{1}=1\)

よって共に正の整数となる.

 

(ⅱ) \(n=k\) のとき

\(a_{k}\)、\(b_{k}\) が共に正の整数となると仮定する.

(1)の結果より、

\(\begin{cases}a_{k+1}=a_{k}+b_{k}\\b_{k+1}=a_{k}\end{cases}\)

が成立するので、仮定より \(a_{k+1}\)、\(b_{k+1}\) は共に正の整数となる.

(ⅰ)、(ⅱ)より、すべての自然数 \(n\) において、\(a_{n}\)、\(b_{n}\) は共に正の整数である

 

Ⅱ. \(a_{n}\)、\(b_{n}\) は互いに素であることを証明

(ア) \(n=1\) のとき

(ⅰ)の結果より、\(a_{1}=1\)、\(b_{1}=1\)

よって \(a_{1}\)、\(b_{1}\) は互いに素である.

 

(イ) \(n=k\) のとき

\(a_{k}\)、\(b_{k}\) が互いに素であると仮定する.

目標・方針:背理法を利用

\(a_{k+1}\)、\(b_{k+1}\) の最大公約数を \(g≧2\) とおき、矛盾を導く

ここで、\(a_{k+1}\)、\(b_{k+1}\) の最大公約数を \(g≧2\) とすると、

\(a_{k+1}=gs\)、\(b_{k+1}=gt\) ・・・③ とおける.

ただし、\(s , t\) は互いに素な正の整数.

(1)の結果より、

\(\begin{cases}a_{k+1}=a_{k}+b_{k}\\b_{k+1}=a_{k}\end{cases}\)

が成立するので、③を代入して

\(gs=a_{k}+b_{k}\)、\(gt=a_{k}\)

よって、\(b_{k}=gs-a_{k}=gs-gt=g(s-t)\)

したがって、\(b_{k}\) は \(g\) を約数にもつ.

また、\(gt=a_{k}\) より \(a_{k}\) は \(g\) を約数にもつ.

よって、\(a_{k}\)、\(b_{k}\) は共に約数 \(g≧2\) を持つが、

これは、\(a_{k}\)、\(b_{k}\) が互いに素であることに矛盾する.

したがって、\(a_{k+1}\)、\(b_{k+1}\) は互いに素となる.

(ア)、(イ)よりすべての自然数 \(n\) において、\(a_{n}\)、\(b_{n}\) は互いに素である

 

【2005東京大学】3 以上 999 以下の奇数aで、a^2-aが 10000 で割り切れる整数
整数問題の中でも頻出の「互いに素」に関する問題。「連続する2つの整数が互いに素」である性質をただ知っているだけでなく、使いこなせるかどうかが差を分ける問題。数学A。2次試験対策。東大過去問演習
2018東京大学・理系[第2問整数]anが整数となるn|規約分数・減少数列
既約分数(互いに素)であることの証明。整数問題の極意である実験の大切さ、また単調に増加・減少する数列に関する整数問題。 総合力が問われる、2次試験対策として良問。

コメント

タイトルとURLをコピーしました