第3章 整数
問題は12ページ ,
|14| ユークリッドの互除法 Lv. ★★★
に素でない"は式で表しやすい。 そこで, 対偶法や背理法で示すのがポイント。
28n+5
を
21n+4
考え方
(1)条件や結論の “互いに素である" は式で表しづらいが, 否定した "互い
C
21n+4
(2) (1)がヒントになっていることには気づくだろう。つまり,
の形に表して,21n+4とcが互いに素であることを示せばよい。
Process
解答
対偶法で示す。 互いに
素でない2数a. bを式
a
(1)aともが互いに素でないと仮定すると
a= km, b=kn (kは2以上の自然数, m, nは自然数)
とおくことができる。与えられた関係式に代入して
kn _ _C_+d
km
で表す
: c=k(n- md)
km
よって,aとcは公約数 &(2 2) をもつので, aと cは互いに素
でない。ゆえに, 対偶命題が成り立つので, もとの命題も成り
(証終)
与式に代入して、 aとc
が互いに素でないこと
(公約数が2以上)を示
立つ。
28n+5
7n+1
す
+1であるから, 28n+5と21n+4
21n+4
21n+4
が互いに素であることを証明するためには, (1)より 21n+4
と7n+1が互いに素であることを示せばよい。
21n+4
1
ここで、
+3であり, 7n+1と1は互いに
7n+1
7n+1
素であるから,(1)より 21n+4と 7n+1も互いに素である。
ゆえに,28n+5と 21n+4も互いに素である。
(証終)
の解説 2つの自然数の最大公約数を求める方法をユークリッドの互除法といったが、
b
+dは, ユークリッドの互除法において a, bの最大公約数を求める操作に他な
a
a
らない。互いに素とは最大公約数が1ということであるから, 本間の背景にはユークリ
ッドの互除法がある。
核心は
ココ!
互いに素であることを証明するときには,
対偶法や背理法が有効
32