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

２８２１＝７・１３・３１はカーマイケル数である.

例：x^2=1　　　(mod2821)

については

2^2820=1 (mod2821)

である。

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

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

2^1410＝１５２０≠-１　　（ｍｏｄ２８２１）

　２^2820＝（２^1410）^2＝１５２０^2=２３１０４００＝１　（ｍｏｄ２８２１）

これより、

　　x^2=1　　　(mod2821)

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

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

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

(1520+1,2821)=13

(1520-1,2821)=217＝7・31

(-1520+1,2821)=(1302,2821)=217＝7・31

(-1520-1,2821)=(1300,2821)=13

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