第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

14 Lv.★★★ 解答は32ページ · b (1)自然数a, b, c, dに- C+dの関係があるとき,aとcが互いに a a 素であれば,aとbも互いに素であることを証明せよ。 (2) 任意の自然数nに対し, 28n+5 と 21n+4は互いに素であることを 証明せよ。 (十阪士士山

25h+5 と212t4は、豆いに家でないと仮定すると 26n+5=p 5と Ap 21n+4=24. (lr2以上の自然数、Pg.4自然数) とおく2とができる 25n:dp-5 (lは2以上の自然数.p.9.8自発数) れ-e S P- 28 28 112 105 4 れ=l 21 れを消去し、両辺に、21.28をかけると 214p -21-5 - 26l- e12lp-26,): 105-1f2 AE2一2p7+7 1:2-7:3 a14-3p)·. 29g-9)- 1 されはL2以上の自然数だということに予輪する ま、2対傷盤が版り立つのでもとの原像gが立する 4-28