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

５６１＝３・１１・１７は最小のカーマイケル数である.

例：x^2=1　　　(mod561)

については

2^560=1 (mod561)

2^280=1 (mod561)

である。

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

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

2^140＝67 (mod561)

　２^280＝（２^140）^2＝６７^2=4481＝１　（ｍｏｄ５６１）

これより、

　　x^2=1　　　(mod561)

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

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

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

(67+1,561)=17

(67-1,561)=3

(-67+1,561)=(495,561)=3・11

(-67-1,561)=(493,561)=17

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