一次合同式の解き方

３ｘ≡６（mod９）のｘを求めよという問題でgcd（3，9）= 3より6は3の倍数であるので解を持つことは分かるのですが，ｘを具体的に求めることができません．参考にしたサイトは
ttp://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/ExEuclid.html「ここの拡張ユークリッド互除法の応用例２」の部分です．
拡張ユークリッドの互除法を用いても
3*1+9*0=3より3*1=3 mod 9 と当然の結果しか得られず進むことができません．

ｘをどのようにすれば求めることができますか？手計算で表を書けば出来るという話ではなく参考サイトのように数学らしい（？）の解き方でお願いします．

No.1 回答者： mister_moonlight 回答日時： 2009/01/10 22:02

応用例の1を使えばいいんじゃないの。

不定方程式を解くだけ。

xとyを整数とすると、題意から　3x＝9y＋6　→　x＝3y＋2　‥‥(1)
(1)のxとyの特別解を各々、α、βとすると　α＝3β＋2　‥‥(2)
(1)-(2)より　（x-α）＝3*（y-β）であるから、1と3は互いに素からmを整数として、x-α＝3m、y-β＝m　‥‥(3)
(2)を満たす具体値の一つは　（α、β）＝（5、1）。
従って、(3)より　x＝3m＋5、y＝m＋1.
これを(1)に代入すると、x-3y-2＝0.

No.2 ベストアンサー 回答者： proto 回答日時： 2009/01/10 22:02

そこまで出来ているなら

　　3*1 ≡ 3 (mod 9)
の両辺に2を掛けて
　　3*2 ≡ 6 (mod 9)
より、x=2が解の一つ。
でもx=5もx=8も解だからこれでは不十分な事が分かる。

自分なら次のように解くかな。
　　3x ≡ 3*2 (mod 9)
より、両辺を3で割りたいところだが、その前にgcd(3,9)=3であることに注意して
　　x ≡ 2 (mod 3)
これが答え。


一般に
　　a*c ≡ b*c (mod m)
のとき
gcd(c,m)=1ならば
　　a ≡ b (mod m)
gcd(c,m)=d≠1ならば
　　a ≡ b (mod m')
(ただしm'はm=d*m'であるような整数)

この回答へのお礼

>gcd(c,m)=d≠1ならば
>　　a ≡ b (mod m')
>(ただしm'はm=d*m'であるような整数)

これは知らなかったです＞＜

助かりました

お礼日時：2009/01/10 23:14