例題241 と同じ考え方で証明できるが,ここでは背理法を用いてみよう。背理法
より,その命題が正しいことを証明する方法」である.(p.271「命題と証明」を
「ある命題に対して, その命題が成り立たないと仮定し, 矛盾が生じることを示すこ。
(2) a+bとab が互いに素であるとき, aとbも互いに素である。
例題 242
互いに素な自然数の性質2
a, bを自然数とするとき,次の命題を示せ、
(2) a+bと abが互いに素であるとき,aとbも互いに素である
考え方
「ある命題に対して, その命題が成り立たないと反定し,矛盾が生じるこ。背理は
(1) a+bとabが互いに素でないと仮定すると, a+b,
ab はある素数かを約数にもつから,
a+b= pk · ①
解答
Taムで a ab= pl ②
→ トト とおける.
G孝た このとき, ②より, かはaまたはbの約数となる。
(k, lは整数)
かは素数
pはaの約数としー
も一般性は失われ。
したがって、かはaの約数とすると,
a= pm (mは整数)
とおける。
これを①に代入すると,
したがって, b=p(k-m) となり,かはbの約数と
なる。
→ら
い、
pm+b=pk
すなわち,かはaとbの公約数となり, かキ1 より,
aとbが互いに素であることに矛盾する。
かはbの約数としても,同様に矛盾する。
よって, a+bと abは互いに素である。
