【３】２次合同式への応用

例：x^2=1　　　(mod341)

については、2^10=1 (mod341)より

2^340=1 (mod341)

2^170=1 (mod341)

である。

それでは、2^85は+1か-1になるだろうか？

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

2^85＝32(2^10)^8=32 (mod341)

これより、

　　x^2=1　　　(mod341)

の4つの解は±1、±32であることがわかる。

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

もし各対から、それらの和と法の最大公約数を計算することによって法の因数を見つけることができる。

(32+1,341)=11

(32-1,341)=31

341＝11・31

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

例：x^2=1　　　(mod341)

は

x^2=1　　　(mod11)

x^2=1　　　(mod31)

したがって

x=1　　　(mod11)

x=1　　　(mod31)

x=-1＝10　　　(mod11)

x=-1＝30　　　(mod31)

の組み合わせを用いて、341を法とする4つの合同でない解を構成することができる。

M1＝31，M2＝11を用いると

31N1=1 mod11→N1=5

11N2=1 mod31→N2=17

これより,

x=155a1+187 (mod341)で

x=155・1+187・1＝1 (mod341)

x=155・1+187・-1＝-32 (mod341)

x=155・-1+187・1＝32 (mod341)

x=155・-1+187・-1＝-1 (mod341)

のように対で現れる

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