■a+bと ab が互いに素ではないと仮定すると, a+b, ab
2つの自然数aとbが互いに素であるとき, a+bと ab も互いに素である
したがって,最大公約数が1であるから, a+bと abは互
「Action》互いに素であることの証明は, 背理法を用いよ
→a+bと abが共通な素因数をもたない1難しいので, 背理法
回題
よ。
ことを証明せよ。
条件の言い換え」
a+bと abが互いに素
「~ない」 の証明は
は素数の公約数pを用いて
a+b= pm … ①,
とおける。ただし, m, nは整数である。
背理法(例題52, 53) を
用いる。
ab = pn …2
第232
O
ゆを素数の公約数とせず,
単に公約数とすると,例
えば p=6 のとき, aが
2の倍数であが3の倍数
のように, pがaまたば
bの約数でない場合もあ
る。
) かがaの約数であるとき
= pe (k は整数)とおくと, ① より
mーkは整数であるから, かはbの約数でもある。
(4)pがりの約数であるとき
(7)と同様に,pはaの約数となる。
(7, (イ)より,かはaとbの公約数となり, aともが互いに
素であることに矛盾する。
したがって, a+6と abは互いに素である。
(別解)
a+bと ab の最大公約数をgとおくと
a+b= mg …O,
と表される。ただし, m, nは互いに素な自然数である。
0より
2に代入すると
6= (m-k)p
自然
かは素数であるから1で
はない。
s 02 1)
4a+bと ab の公約数をg
とおいて, g=1 である
ことを示す。
ab = ng …2
6= mg-a
a(mg-a) = ng
よって
a° = (am-n)g
同様にして
6° = (bm-n)g
ゆえに,gはa', 6の公約数である。
ここで, aとbは互いに素より, α' とも互いに素である
から
Ia, bは共通な素因数を
たないから,' と6も
通な素因数をもたない
g=1
いに素である。
のプロセス
