-
![]()
→□は成り立つ
CHART 互いに素であることの証明
530
基本例題
121 互いに素に関する証明問題 (2)
00000
自然数 α に対して, αともが互いに素ならば, α+bと abは互いに素である
ことを証明せよ。
/p.525 基本事項 重要 121
指針 atb と abの最大公約数が1となることを直接示そうとしても見通しが立たない。
背理法>
そこで, 背理法 (間接証明法)
コは成り立たないと仮定→atbabが互いに素でない, すなわち, a + b と αb はある素数を公約数
・矛盾
にもつ, と仮定して矛盾を導く。
なお、次の素数の性質も利用する。 ただし, m, n は整数である。
考
※素数
る方
しつ
mn が素数の倍数であるとき, mまたはnはかの倍数である。
1
最大公約数が1を導く
2
背理法(間接証明法)の利用
n
a+b と ab が互いに素でない, すなわち, a +6とabは
T
a+b=pk
解答 ある素数を公約数にもつと仮定すると
①, ab=pl
②
と表される。 ただし, k, lは自然数である。
② から, α または は の倍数である。
k-m は整数。
aがpの倍数であるとき,a=pm となる自然数 mがある
このとき,①から,b=pk-a=pk-pm=p(k-m) とな
りもの倍数である。 (+1)8=8+18=8+(1+a
これはaとbが互いに素であることに矛盾している。
bがの倍数であるときも, 同様にしてαはかの倍数であα=pk-b
とが互いに素で
......
ない
mnが素数を
公約数にもつ
り αとが互いに素であることに矛盾する。
したがって, a+babは互いに素である。
W/S
10=p(k-m')
(m' は整数)
[参考] 前ページの基本例題 120 (2)の結果 「連続する2つの自然数は互いに素である」は,整数
の問題を解くのに利用できることがある。 興味深い例を1つあげておこう。
問題 素数は無限個存在することを証明せよ。
証明 n」 を2以上の自然数とすると+1は互いに素であるから,(1)は異な
る素因数を2個以上もつ。
同様にして, ns=nz (n+1)=(n+1)(n+1) は異なる素因数を3個以上もつ。
この操作は無限に続けることができるから, 素数は無限個存在する。
素数が無限個存在することの証明は, ユークリッドが発見した背理法を利用する方法が有名で
あるが,上の証明は, 21世紀に入って (2006年), サイダックによって提示された とても簡潔
な方法である。 次ページで詳しく取り上げたので参照してほしい。
