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

「(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 回答日時： 2007/01/21 16:55

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)
」

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

この回答へのお礼

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

お礼日時：2007/01/22 08:58

No.1 回答者： koko_u 回答日時： 2007/01/21 14:04

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