問題#Ⅰ006 ★★☆☆
整数 $n \geqq 0$ に対し、$b(n)=2n$、$a_n=2^{b(n)}+1$ とする。
（１）数学的帰納法を用いて、$$a_0 a_1 \cdots a_n=2^{b(n+1)}−1 \ (n \geqq 1)$$を示せ。
（２）$a_{n+1}=a_0 a_1 \cdots a_{n}+2 \ (n \geqq 1)$ を示し、$l>m \geqq 1$ のとき、$a_l$と$a_m$は$1$より大きい公約数を持たないことを示せ。
《ポイント》
本問の$a_n$は「フェルマー数」と呼ばれる数で、様々な性質が知られています。（２）は異なるフェルマー数は互いに素であるという性質の証明問題となっています。
公約数はまず仮定して文字で置くところから始めましょう。矛盾を導くにしろ、範囲を絞るにしろ、文字で置かないことには議論できません（勿論、文字で表現せずに互いに素であることを証明しても良いですが･･･）。
《解答例》
（１）
$$a_0 a_1 \cdots a_n=2^{b(n+1)}−1 \ (n \geqq 1) \tag*{･･･(*)}$$と置く。
$b(0)=1$、$b(1)=2$ より、$(*)$式の左辺は$$a_{0}a_{1}=(2^1+1)(2^2+1)=3\cdot5=15$$となり、$b(2)=4$ より、$(*)$式の右辺は$$2^4-1=15$$となるので、$n=1$ のとき、$(*)$が成り立つ。
$n=k$（$k$は$2$以上の自然数）のとき$(*)$が成り立つと仮定すると、$n=k+1$ のとき $a_{k+1}=$ $(*)$式の左辺は$$\begin{align}a_0 a_1 \cdots a_k a_{k+1} &=(2^{b(k+1)}-1)(2^{b(k+1)}+1) \\ &=2^{2b(k+1)}-1 \end{align}$$となる。ここで $2b(k+1)=2^{k+2}=b(k+2)$ であるから、$$a_0 a_1 \cdots a_k a_{k+1}=2^{b(k+2)}-1$$となる。これより $n=k+1$ のときも$(*)$が成立するから、以上よりすべての$n$について$(*)$が成り立つことが示された。
□
（２）
（１）より、$n \geqq 1$ のとき$(*)$が成り立つから、$$\begin{align} a_0 a_1 \cdots a_n &=2^{b(n+1)}-1 \\ \\ \therefore a_0 a_1 \cdots a_n &=(a_{n+1}-1)-1 \\ \\ \therefore a_{n+1} &=a_0 a_1 \cdots a_{n}+2 \end{align}$$となる。これより、$l>m \geqq 1$ のとき、ある整数$N$を用いて$$a_l=a_m \cdot N+2\tag*{･･･ (★)}$$と表すことができる。ここで$a_l$と$a_m$の最大公約数を$g$とし、$a_l=gL$、$a_m=gM$（$L$、$M$は互いに素である正の整数）と置くと、$(★)$は$$g(L-MN)=2\tag*{･･･ (#)}$$と式変形できる。$L-MN$ は整数なので$g$は$2$の約数となるが、$a_n$は任意の正の整数$n$に対して奇数であるから $g=1$ である。したがって$a_l$と$a_m$は$1$より大きい公約数を持たない。
□
《コメント》
「$a_n$は任意の正の整数$n$に対して奇数である」という部分に気付ければ $g=1$、即ち異なるフェルマー数が互いに素であることが証明できます。
フェルマー数に関する問題はたまに入試問題で見かけます。
（出典：北海道大学 1993年）