 | 背理法を用いて証明すると、以下のようになります。
<証明>
mを自然数とし、2つの整数2^m−1…(P), 2^(m−1)−1…(Q)について、
(i) m＝1のとき、
(P)は2^1−1＝1, (Q)は2^(1−1)−1＝0となり、(P)と(Q)は1以外の公約数をもたない。
(ii) m＝2のとき、
(P)は2^2−1＝3, (Q)は2^(2−1)−1＝1となり、(P)と(Q)は1以外の公約数をもたない。
(iii) m>=3のとき、
(P)と(Q)に2以上の公約数gが存在すると仮定すると、
(P)は2^m−1＝ga, (Q)は2^(m−1)−1＝gb(ただし、g, a, b:自然数, g>=2)と表すことができ、
(P)より、ga＝2・2^(m−1)−1＝2・(gb＋1)−1＝2gb＋1＝g(2b＋1／g)となり、
a＝2b＋1／gとなるが、2b＋1／gは自然数とならず、aが自然数であることと矛盾するので、
(P)と(Q)には2以上の公約数が存在せず、(P)と(Q)は1以外の公約数をもたない。
(i), (ii), (iii)より、(P)と(Q)は1以外の公約数をもたない。
つまり、mを自然数とするとき、2つの整数2^m−1と2^(m−1)−1は互いに素である。(終)
|
