問題
正の整数とが互いに素であるとき，正の整数からなる数列を， で定める．このときすべての正の整数に対してとが互いに素であることを示せ．
出典：名古屋大学 2004年度 前期日程 第2次学力試験 理系 第4問(b)
方針
隣り合う2項が互いに素であることだけを帰納法で示そうとすると、漸化式の の部分を処理するために との互いに素性も必要になる。そこで、 と が互いに素であること、さらに と が互いに素であることを同時に帰納法で示す。 と が互いに素である条件は、 と の共通約数を調べるところで使う。
解答
次の2つの主張を同時に帰納法で示す。 であるから、 ではどちらも成り立つ。
ある で、 と が互いに素であり、かつ と が互いに素であると仮定する。まず と が互いに素であることを示す。 を と の公約数とする。漸化式 より、 は を割り、また を割るので、 である。ところが と は互いに素であり、 と も互いに素である。 は の約数だから、 は とも とも互いに素である。よって である。したがって と は互いに素である。
次に と が互いに素であることを示す。 を と の公約数とする。このとき である。一方、 であり、仮定より と は互いに素であるから、 と も互いに素である。したがって でなければならない。
しかし、上で示したように と は互いに素であり、 は も割る。よって である。したがって と は互いに素である。
以上により、帰納法で任意の について と は互いに素である。