Question

理工学部の大学1年生

注意②の「3は何倍しても9を法として1と合同にはならない」のは何故ですか？
aとmが互いに素でないこととどんな関係があるのですか？

合同式の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

合同式

Answer 1

✨ Best Answer ✨

Crystal Clear

3k≡1 mod9 と仮定
3k=9d+1
左辺は3の倍数、右辺は3の倍数でない、矛盾

(1)の別解のように、適当な数kを両辺にかけて
3kx≡6k
として、3k≡1となるようなうまいkを見つけて
x≡6k
とすることが不可能ということ。

合同式

Answer 2

とももん

『9を法として1と合同である』っていうのは『9で割ると1余る』という意味ですよ😀
3は何倍しても9で割って1余りませんよね！余りは0か3か6になるはずですから

理工学部の大学1年生

回答ありがとうございます！助かりました🙇‍♀️