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

例：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

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