■ユークリッドの互除法(その2)

1次合同式

 ax=c (mod m)

は最大公約数(a,m)がcを割り切るとき、かつ、そのときに限り解が存在する。

mを法として合同でない解が(a,m)個存在する。(a,m)=1に対しては、解は一意である。

===================================

3x=9 (mod 6)

(3,6)=3は9を割り切る。

F={1,2,3,4,5}を考えると、3つの合同でない解{1,3,5}が見つかる。6の倍数を加えると{7,9,11,13、・・・}が得られる。

解はax=my+cの整数解(x,y)と一致する。

===================================