東大理系数学'02年前期[2]

nは正の整数とする。で割った余りを
とおく。
(1) 数列
を満たすことを示せ。
(2) に対して、は共に正の整数で、互いに素であることを証明せよ。

解答 多項式の除算数学的帰納法の融合問題です。(2)では、整数もからんできますが、背理法を用いることで証明ができます。
なお、この問題で登場する数列は、を満たし、東大で頻出のフィボナッチの数列です。


(1) 題意より、に対して、
・・・@ (多項式の除算を参照)
とおくことができます。
ここで、とすると、
・・・A

@両辺にxをかけて変形します。

・・・B
Aは、で割った余りがだと言っています。
Bは、で割った余りがだと言っています。
A,Bを比較することにより、に対して、
・・・C

(2) 数学的帰納法により証明します。
i) のとき、
@において、とすると、
より、
よって、は共に正の整数で、互いに素
(最大公約数が1)です。

ii) のとき、成り立つとして、は共に正の整数で、互いに素です。 ・・・D
このとき、も共に正の整数です。
ここで、が互いに素ではないと仮定します。
・・・E (背理法については、証明の技巧を参照)
すると、2以上の公約数sをもつはずです。
このとき、
pqを正の整数として、とおくことができます。Cより、
ですから、2以上の公約数sをもつことになり、が互いに素であるとした数学的帰納法の仮定Dと矛盾します。
従って、が互いに素ではないとした仮定Eは誤りで、は互いに素です。
よって、のときも成り立ちます。

1)ii)より、に対して、は共に正の整数で、互いに素であることが示されました。(証明終)


   東大理系数学TOP   数学TOP   CHALLENGE from the VOID   TOPページに戻る

(C)2005,2006,2007,2008,2009
(有)りるらる
CFV21 随時入会受付中!
CFV21ご入会は、まず、
こちらまでメールをお送りください。
 雑誌「大学への数学」購入