基本例題 113 互いに素に関する証明問題 (2)
00000
自然数 α, bに対して, aとbが互いに素ならば, a+babは互いに素であるこ
とを証明せよ。
p.476 基本事項 [②] 重要 114
指針a+b と ab の最大公約数が1となることを直接示すのは糸口を見つけにくい。
そこで,背理法(間接証明法)を利用する。 →a+b と ab が互いに素でない,すなわち
a+b と ab はある素数』を公約数にもつ,と仮定して矛盾を導く。
なお,次の素数の性質も利用する。 ただし, m, nは整数である。
mnが素数」の倍数であるとき, mまたはn はかの倍数である。
CHART 互いに素であることの証明
① 最大公約数が1を導く
② 背理法 (間接証明法) の利用
解答
a+b と ab が互いに素でない, すなわちa+b ab ある素
数』を公約数にもつと仮定すると
② (k, lは自然数)
a+b=pk...・・･ ①, ab=pl
と表される。
② から, a または6の倍数である。
aがpの倍数であるとき, a=pm となる自然数mがある。
このとき, ①から6=pk-a=pk-pm=p(k-m) となり,
ももかの倍数である。
これはaとbが互いに素であることに矛盾している。
bがpの倍数であるときも、同様にしてαはpの倍数であり,
aとbが互いに素であることに矛盾する。
したがって,a+b と αb は互いに素である。
mとnが互いに素でない
⇒ m nが素数を公約
数にもつ
<k-mは整数。
<a=pk-b
=p(k-m')
( m'は整数)
[参考] 前ページの基本例題112 (2) の結果 「連続する2つの自然数は互いに素である」 は, 整数
の問題を解くのに利用できることがある。 興味深い例を1つあげておこう。
問題 素数は無限個あることを証明せよ。
[証明]
を2以上の自然数とすると+1は互いに素であるから,(n+1) は異な
」
る素因数を2個以上もつ。
同様にして, n=n(n+1)=n(n+1) (n2+1) は異なる素因数を3個以上もつ。
この操作は無限に続けることができるから, 素数は無限個存在する。
※各自=2や=3などの場合で,このことを検証してみるとよい。
素数が無限個あることの証明は, ユークリッドが発見した背理法を利用する方法が有名である
が、上の証明は、21世紀に入って (2006年), サイダックによって提示された, とても簡潔な方
法で
481
4章
17
約数と倍数、最大公約数と最小公倍数
