問題#Ⅰ006


問題#Ⅰ006 ★★☆☆

整数 $n \geqq 0$ に対し、$b(n)=2n$、$a_n=2^{b(n)}+1$ とする。

(1)数学的帰納法を用いて、$$a_0 a_1 \cdots a_n=2^{b(n+1)}−1 \ (n \geqq 1)$$を示せ。

(2)$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$は「フェルマー数」と呼ばれる数で、様々な性質が知られています。(2)は異なるフェルマー数は互いに素であるという性質の証明問題となっています。

公約数はまず仮定して文字で置くところから始めましょう。矛盾を導くにしろ、範囲を絞るにしろ、文字で置かないことには議論できません(勿論、文字で表現せずに互いに素であることを証明しても良いですが・・・)。


《解答例》

(1)

$$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$について$(*)$が成り立つことが示された。

 

(2)

(1)より、$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年)


戻る