連立合同式
p,q,rは、どの2つも互いに素とする。
N≡a (mod p)
N≡b (mod q)
N≡c (mod r)
次の1次合同式を解く。
qrx≡a (mod p)→x≡s (mod p)
pry≡b (mod q)→y≡t (mod q)
pqz≡c (mod r)→z≡u (mod r)
s,t,uを使って、
N≡qrs+prt+pqu (mod pqr)
【例①】
連立合同式を解け
N≡3 (mod 7)
N≡1 (mod 10)
N≡7 (mod 13)
【解】
130x≡3 (mod 7)→4x≡3≡24→x≡6
91y≡1 (mod 10)→y≡1
70z≡7 (mod 13)→5z≡7≡20→z≡4
N≡130×6+91×1+70×4
≡780+91+280≡1151≡241 (mod 910)
よって、N≡241 (mod 910)
※1次合同式の解法の際に、
aとpが互いに素のとき、
ax≡ab (mod p)⇒x≡b (mod p)
を利用している。
【百五減算】
N≡a (mod 3)
N≡b (mod 5)
N≡c (mod 7)
35x≡a (mod 3)→x≡-a (mod 3)
21y≡b (mod 5)→y≡b (mod 5)
15z≡c (mod 7)→z≡c (mod 7)
N≡-35a+21b+15c (mod 105)
N≡70a+21b+15c (mod 105)
文字が2つのときも同じように解くことができる。
p,qが互いに素とする。
n≡a (mod p)
n≡b (mod q)
qx≡a (mod p)→x≡s (mod p)
py≡b (mod q)→y≡t (mod q)
n≡qs+pt (mod pq)
【例②】
n≡1 (mod 7)
n≡2 (mod 5)
5x≡1 (mod 7)→5x≡15→x≡3
7y≡2 (mod 5)→2y≡2→y≡1
n≡5×3+7×1≡15+7≡22 (mod 35)
【例③】
n≡3 (mod 4)
n≡5 (mod 7)
7x≡3 (mod 4)→3x≡3→x≡1
4y≡5 (mod 7)→4y≡12→y≡3
n≡7×1+4×3≡7+12≡19 (mod 28)
【例④】
n≡20 (mod 27)
n≡4 (mod 11)
11x≡20 (mod 27)→-16x≡20
→4x≡-5≡-32→x≡-8
27y≡4 (mod 11)→5y≡4≡15→y≡3
n≡11×(-8)+27×3≡-88+81
≡-7≡290 (mod 297)
(2022/10/7)
【おまけ】
p[1],…,p[k]はどの2つも互いに素とする。
連立合同式
n≡a[1] (mod p[1])
n≡a[2] (mod p[2])
……
n≡a[k] (mod p[k])
を満たすnは、M=Πp[i]を法としてただ一つ存在する。
q[i]=M/p[i]とする。
q[i]x[i]≡a[i] (mod p[i])の解を、
x[i]≡b[i] (mod p[i])とすると、(※)
n≡Σq[i]b[i] (mod M)
【証明】
i≠jのとき、q[j]≡0 (mod p[i])
i=1,……,kのとき、
n≡q[i]b[i]≡a[i] (mod p[i])
よって、連立合同式を満たす。
x,yが共に解とする。
i=1,……,kで、
x≡a[i] ,y≡a[i] (mod p[i])
x-y≡0 (mod p[i])
x-yはp[i]の倍数
p[i]はどの2つも互いに素だから、
最小公倍数Mの倍数
x-y≡0 (mod M)
x≡y (mod M)
【証明終】
(※)
合同式q[i]x[i]≡a[i] (mod p[i])は、
q[i]とp[i]が互いに素だから、
解b[i]を持つ。
(2022/10/11)