00
はとも
ど、ま
いほど、
とき
例題234 互いに素な自然数の性質
2つの自然数aとbが互いに素であるとき, a+b と abも互いに素である
ことを証明せよ。
思考プロセス
条件の言い換え
「~ない」 の証明は
⇒ a+ b と ab が共通な素因数をもたない 「難しいので, 背理法
a + b と ab が互いに素
Action》互いに素であることの証明は,背理法を用いよ
開a + b と ab が互いに素ではないと仮定すると, a+b, ab
は素数の公約数を用いて
a+b=pm... ①, ab = pn ... 2
とける。 ただし, m, nは整数である。
このとき ② より paまたは6の約数である。
(ア) pαの数であるとき
a = pk(kは整数)とおくと, ① より b=(m-k)p
m-kは整数であるから, pは6の約数でもある。
(イ)が6の約数であるとき
(ア)と同様に
(ア),(イ)より,かはaとbの公約数となり, aとbが互いに
素であることに矛盾する。
したがって, a +6 と αb は互いに素である。
(別解)
a + b と ab の最大公約数をg とおくと
a+b=mg... ①,
ab = ng ... 2
と表される。ただし,m,nは互いに素な自然数である。
①より
b = mg-a
②に代入すると
互いに素ではない
はαの約数となる。
a(mg-a)=ng
よって
同様にして
b2=(bm-ng
ゆえに,g d','の公約数である。
ここで, a b は互いに素より とも互いに素である
から
g = 1
したがって, 最大公約数が1であるから, a + b と α は互
いに素である。
a² = (am-n)g
★★★
atbab互いにそである
ことを証明したい
背理法(例題 52,53) を
用いる。
を素数の公約数とせず,
単に公約数とすると 例
えば = 6 のとき, αが
2の倍数でbが3の倍数
のように, かが α または
6の約数でない場合もあ
る。
は素数であるから1で
はない。
a + b と abの公約数をg
とおいて,g=1 である
ことを示す。
a,b は共通な素因数をも
たないから
とも共
通な素因数をもたない。
7
章
17
1 約数と倍数