名古屋大学前期(理4b)
正の整数 a と b が互いに素であるとき、正の整数からなる数列 {xn} を
x1 = x2 = 1,
xn+1 = axn + bxn-1 (n ≥ 2)
で定める。このときすべての正の整数 n に対して xn+1 と xn
が互いに素であることを示せ。
解答
まず、すべての正の整数 n に対して xn が b と互いに素であることを、
n についての数学的帰納法で示す。
x1 = x2 = 1 なので n = 1, 2 のときは xn は b
と互いに素である。
m を 2 以上の整数として xm が b と互いに素と仮定する。このとき xm+1 も b と互いに素であることを
示す
b と xm+1 をともに割り切る素数 p が存在したと仮定すると
xm+1 = axm + bxm-1 なので p
axm をわりきる。
p は素数なので p は a を割り切るかまたは xm を割り切る。
このことは、 a と b が互いに素及び xm と b が互いに素であることに矛盾する。
よって b と xm+1 が互いに素であることが示された。
以上より すべての正の整数 n に対して xn が b と互いに素であることが
わかった。
すべての正の整数 n に対して xn+1 と xn が互いに素であること
n に関する数学的帰納法で示す。
x1 = x2 = 1 なので n = 1 のときは
xn+1 と xn は互いに素である。
m を 1 以上の整数とし、xm+1 と xm が互いに素と仮定する。
このとき xm+2 と xm+1 が互いに素であることを示す。
xm+2 と xm+1 の両方の約数となる素数 p が存在したと仮定する。
xm+2 = axm+1 + bxm なので p
は bxm を割り切ることになる。
p は素数なので b を割り切るか xm を割り切ることになる。
ところが p は xm+1 を割り切り b は xm+1 と互いに素なので p は b を割り切らない。
また p は xm+1 を割り切り xm+1 と xm が互いに素
なので p は xm を割り切らない。
これは矛盾である。従って、xm+2 と xm+1 が互いに素であることが
示された。
以上より、
すべての正の整数 n に対して xn+1 と xn
が互いに素であることが示せた。
解
戻る