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

　　ｘ^2＝ｂ　　（ｍｏｄｍ＝ｐ^aｑ^bｒ^c・・・）

は連立合同式

　　ｘ^2＝ｂ　　（ｍｏｄｐ^a）

　　ｘ^2＝ｂ　　（ｍｏｄｑ^b）

　　ｘ^2＝ｂ　　（ｍｏｄｒ^c）

・・・・・・・・・・・・・・・

に帰着される。

例：x^2=9　　　(mod28)

は

x^2=9　　　(mod4)

x^2=9　　　(mod7)

したがって

x=3　　　(mod4)

x=3　　　(mod7)

x=-3＝1　　　(mod4)

x=-3＝4　　　(mod7)

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

M1＝7，M2＝4を用いると

7N1=1 mod4→N1=3

4N2=1 mod7→N2=2

これより,

x=21a1+8a2 (mod28)で

x=21・3+8・3＝3 (mod28)

x=21・3+8・4＝11 (mod28)

x=21・1+8・3＝17＝-11 (mod28)

x=21・1+8・4＝25＝-3 (mod28)

のように対で現れる

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

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

(3+11,28)=14

(3+17,28)=4

(3+25,28)=28

(11+17,28)=28

(11+25,28)=4

(17+25,28)=14

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