代数の合同式の問題で質問です。

質問

「(a,n)=1である自然数aと整数x,yについて
　　　　a*x≡a*y (nod n) ⇒　x≡y (nod n)
が成立することを証明するときにa*t+n*u=1となる整数t,uが存在することを使って解くことは可能でしょうか？？

回答No.2

yoikagari · ベストアンサー

nod nは mod nの誤りですよね。

一応、両方の方針で証明します。

a*t+n*u=1となる整数t,uが存在することを使わない解答
「
a*x≡a*y (mod n)
a(x-y)≡0 (mod n)　
a(x-y)はnで割り切れる
(a,n)=1よりaとnは互いに素だから、x-yがnで割り切れる。
よって
x-y≡0 (mod n)
x≡y (mod n)
」

a*t+n*u=1となる整数t,uが存在することを使う解答
「
a*x≡a*y (mod n)
両辺にtをかけて
(a*t)*x≡(a*t)*y (mod n)
a*t≡1-n*u≡1　 (mod n)
だから
x≡y　 (mod n)
」

どちらがよろしいでしょうか。

お礼

ありがとうございました。とてもわかりやすく丁寧で感謝してます＾＾

回答No.1

koko_u

使っても解けるし、使わなくても解ける。