一般に ax=c (mod m)は(a,m)|cのとき、かつ、そのときに限り解をもつ。

(a,m)=1に対しては、解はｍを法として一意である。また、

ax=c (mod m)

の解はax=my+cの整数解と一致する。

15x=1 (mod 11)は(15,11)=1であるから、解をもつ。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

対応するディオファントス方程式は

15x=11y+1

yについて解くと、y=x+(4x-1)/11→4ｘ-1は4の倍数

4x-1=11wをｘについて解くと、x=2w+(3w+1)/4→3w+1は3の倍数

3w+1=3vをwについて解くと、w=v+(v-1)/3

ここで、整数解はV=1→W=1→x=3,y=4が得られる。15・=451 (mod11)

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

以上の手続きはユークリッドの互除法と同じものである。

15/11=1+4/11

11/4~2+3/4

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝