494
演習 例題 121 合同式の性質の証明と利用
00000
(1) か.492 基本事項の合同式の性質 2、および次の性質を証明せよ。 ただし
は整数, m は自然数とする。
5aとが互いに素のとき ax=ay (modm)⇒x=y (modm)
(2)次の合同式を満たすxを,それぞれの法mにおいて, x=a(mod m) [a は
mより小さい自然数] の形で表せ(これを合同方程式を解くということがある)。
(ア)x+4=2 (mod 6 )
(イ) 3x≡4 (mod 5 )
指針
pp.492 基本事項 ③3
(mod m) のとき,
-■はmの倍数である。
合同式 加法・減法・乗法だけなら普通の数と同じように扱える
(イ) 「4 (mod 5) かつ
指針▷ (1) 方針はp.493の証明と同様。
(2)
解答
(1) 2 条件から, a-b=mk,c-d=ml (k, lは整数)
と表され
性質を適用する。
が3の倍数」となるような数を見つけ,
a=b+mk, c=d+ml
よって a-c=(6+mk)-(d+ml)=b-d+m(k-l
ゆえに a-c-(b-d)=m(k-1)
(2) (ア) 与式から
5ax=ay (modm) ならば, ax-ay=mk(kは整数)と表
され
a(x-y)=mk aとは互いに素であるから
x-y=ml (lは整数)
よってx=y (mod m)
x=2-4 (mod 6 )
24 (mod6) であるから
(イ) 49 (mod5) であるから、与式は
法5と3は互いに素であるから
......
よって a-c=b-d (modm)
x=4 (mod 6 )
3x=9 (mod 5)
x=3 (mod 5)
の倍数
→ = ▲k(kは整数)
<pg が互いに素でpk
が g の倍数ならば k
はgの倍数である。
検討 合同方程式の問題は表を利用すると確実
(2)(イ)については, 次のような表を利用する解答も考えられる。
別解 (イ)x=0, 1,2,3,4について, 3xの値は右の表
のようになる。 3x=4 (mod5) となるのは, x=3のと
きであるからx=3 (mod5)
注意 合同式の性質5が利用できるのは, 「aとが互いに素」であるときに限られる。
例えば, 4x=4 (mod6) ① については, 4と法6は互いに素ではないから,
①よりx=1 (mod6) としたら誤り!
性質2。 移項の要領。
-2-4-6 ( 6の倍数)
また, 推移律を利用。
性質を利用。
XC 01 2
3 4
3x 0 3 6=1 9=4 12=2
2
表を利用の方針で考えると,右の表からわか
るように x=1, 4(mod 6 ) である。
x = (mod m) またはx=6 (modm) を x=a,b (modm)」と表す。]
x 0 1
3
4 5
4x 0 4 8=2_12=0_16=4 20=2
漢
練習
(1) p.492 基本事項の合同式の性質
を証明せよ。
③ 121 (2) 次の合同式を満たすxを, それぞれの法mにおいて, x=a (mod m) の形で
表せ。 ただし, a はより小さい自然数とする。
(ア) x-7=6 (mod 7 )
(イ) 4x5 (mod11)
(ウ) 6x=3 (mod 9 )
(1
IC
(1)
F
