基本 例題I13 互いに素に関する証明問題(2)
|自然数 a, bに対して,aとbが互いに素ならば, a+bとabは互いに素であるこ
481
とを証明せよ。
あ
p.476 基本事項 2
重要114
指針>a+bとab の最大公約数が1となることを直接示すのは糸口を見つけにくい。
そこで,背理法(間接証明法)を利用する。→a+bと abが互いに素でない,すなわち
atbと abはある素数かを公約数にもつ,と仮定して矛盾を導く。
なお、次の素数の性質も利用する。ただし, m, nは整数である。
4章
17
をmn が素数pの倍数であるとき, mまたはnはpの倍数である。
Opd
1 最大公約数が1を導く
2 背理法(間接証明法)の利用
CHART 互いに素であることの証明
よケ 音
解答
| る
a+bと ab が互いに素でない,すなわちa+6と abはある素
数かを公約数にもつと仮定すると
合量a+6=pk …
mとnが互いに素でない
→mとnが素数を公約
数にもつ
の, ab=pl …② (k, 1は自然数)
と表される。
き お
のから,aまたはbはかの倍数である。
aがpの倍数であるとき, a=pm となる自然数mがある。
このとき,① から b=pk-a=pk-pm=p(k-m) となり,
bもかの倍数である。
これはaとbが互いに素であることに矛盾している。
bがかの倍数であるときも,同様にしてaはpの倍数であり,
aとbが互いに素であることに矛盾する。
したがって,a+bと abは互いに素である。
R-m は整数。
音数
Aa=pk-b
| =が(R-m')
でO 自 (m' は整数)
まないる ()-
ら、
約数と倍数、最大公約数と最小公倍数