530
|基本例題 121 互いに素に関する証明問題 (2) 000
自然数 α, bに対して, aとbが互いに素ならば, a + b と abは互いに素である。
ことを証明せよ。
p.525 基本事項
2 重要 121
a+b abの最大公約数が1となることを直接示そうとしても見通しが立たない。
そこで,背理法(間接証明法)を利用する。
→a+b と ab が互いに素でない, すなわち, a+bとαbはある素数」を公約数
にもつ,と仮定して矛盾を導く。
なお、次の素数の性質も利用する。 ただし,m, n は整数である。
mn が素数 』 の倍数であるとき,またはnはかの倍数である。
1 最大公約数が1を導く
CHART 互いに素であることの証明
背理法 (間接証明法)の利用
a+b と ab が互いに素でない, すなわち, a + b と αbは
解答ある素数を公約数にもつと仮定すると
とnが互いに素で
ない
a+b=pk
D, ab=pl ②
と表される。 ただし, k, lは自然数である。
......
mnが素数を
公約数にもつ
② から, α または は の倍数である。
α
a=pmとなる自然数がある。
の倍数であるとき,
=
1
このとき,①から,b=pk-a=pk-pm=p(k-m) となk-mは整数。
りもの倍数である。 (I+\)8=8+18=8+ (I+s)=(
これはaとbが互いに素であることに矛盾している。(+0)
Ict
bがpの倍数であるときも,同様にしてαはの倍数であa=pk-b
り,aとbが互いに素であることに矛盾する。
=pk-m')
したがって, a+bとabは互いに素である。)=+
( ' は整数)
参考 前ページの基本例題120 (2) の結果 「連続する2つの自然数は互いに素である」は,整数
の問題を解くのに利用できることがある。 興味深い例を1つあげておこう。
問題 素数は無限個存在することを証明せよ。
[証明]
2以上の自然数とする。 +1は互いに素であるから, n=n (n+1) は異な
る素因数を2個以上もつ。
同様にして, n=n(n+1)=ni(n+1) (n2+1) は異なる素因数を3個以上もつ。
「この操作は無限に続けることができるから,素数は無限個存在する
素数が無限個存在す
