合同式の1次方程式
次の合同式を満たすxを, それぞれの法mにおいて,
x=a (mod m) [aはmより小さい自然数] の形で表せ。
(1) 4x=3 (mod5)
用して、
例題 37
(2) 3x=6(mod9)
合同式の扱い ×3D0, 1, …, m-1 について, 表を用いて調べる。
(1) 下の表より, 4x=3 (mod5) となるのは, x=2 のときである。
3
x
0 1
2
4
4x|0 4 8=3 12=2 16=1
圏 x=2(mod5)
別解 [左辺のxの係数を1にすることを考える]
4x=3 (mod5)の両辺に4を掛けて
16x=1·x=x (mod5), 12=2 (mod5) であるから
(2) 下の表より,3x=6 (mod9) となるのは, x=2, 5, 8 のときである。
16x=12(mod5)
=2(mod5)啓
012
3
4
5
6
7 8
x
3x|0 3 6930 12=3 15=6 18=0 21=3 24=6
よって
=2, 5, 8(mod9) 寄
注意 0 x=a (modm) または x=b (modm)を,「x=a, b (modm)」
と表す。
2 3は何倍しても9を法として1と合同にはならないから, (2)は(1)
の別解の方法を使えない。また, 3x=6 (mod9) の両辺を3で割っ
て, x=2 (mod9) としてはいけない。
参考 一般に,aとmが互いに素であるときに限り,
ax=ay (modm) → x=y (modm)
が成り立つ。
(証明)ax=ay (modm) → a(x-y)=mk (kは整数)
aとmが互いに素であるから, x-yはmの倍数である。
よって
x=y(mod m)
S
