【第6章】
(6)連立1次合同方程式
5で割ると2余り、7で割ると3余る数を求めよ。
求める数をxとし式にすると、
x≡2 (mod 5) …①
x≡3 (mod 7) …②
を同時に満たす数である。
①の各辺を7倍 7x≡14 (mod 35) …③
②の各辺を5倍 5x≡15 (mod 35) …④
5x+7y=1の特殊解(3,-2)だから、
④の両辺を3倍 15x≡45 (mod 35) …⑤
③の両辺を-2倍 -14x≡-28 (mod 35) …⑥
⑤+⑥
x≡17 (mod 35)
したがって、x=35t+17 (tは整数)
一般的な連立1次合同方程式の解法を考えてみよう。
x≡a (mod gm), x≡b (mod gn)
mとnは互いに素とする。
x≡a (mod g), x≡b (mod g)より、
b≡a (mod g)は必要条件である。
nx≡na (mod gmn), mx≡mb (mod gmn)
mとnは互いに素だから、
ms+nt=1の特殊解(s,t)が存在する。
ntx≡nta , msx≡msb (mod gmn)
(nta+msb)x≡nta+msb (mod gmn)
x≡nta+msb (mod gmn)
が解である。
【確かめ①】
b≡a (mod g)とし、b-a=gkとする。
nta+msb=(1-ms)a+ms(gk+a)=a+gmsk
x≡a+gmsk≡a (mod gm)
nta+msb=nt(gk-b)+(1-nt)b=b+gntk
x≡b+gntk≡b (mod gn)
【確かめ②】
x≡a (mod gm), x≡b (mod gn)
を満たす解
x≡p (mod gmn)
x≡q (mod gmn)とする。
p≡a (mod gm), q≡a (mod gm)より、
p≡q (mod gm)
p≡b (mod gn), q≡b (mod gn)より、
p≡q (mod gn)
したがって、
p≡q (mod gmn)
以上より、
x≡a (mod gm), x≡b (mod gn)
mとnは互いに素とする。
a≡b (mod g)のとき解を持つ。
ms+nt=1のとき、
x≡nta+msb (mod gmn)
(例)
x≡a (mod 5), x≡b (mod 7)
5x+7y=1の特殊解(3,-2)だから、
x≡-2×7a+3×5b (mod 35)
x≡-14a+15b (mod 35)
(a,b)=(2,3)→-28+45=17より、
x≡17 (mod 35)
【百五減算】
3で割るとa余り、5で割るとb余り、7で割るとc余る数を求めよ。
x≡a (mod 3) …①
x≡b (mod 5) …②
x≡c (mod 7) …③
②③より、x≡-14b+15c (mod 35)
3x+35y=1の特殊解(12,-1)
x≡-1×35a+12×3(-14b+15) (mod 105)
x≡-35a-504b+540c (mod 105)
x≡70a+21b+15c (mod 105)
(※ 江戸時代の和算書『塵劫記』に載っている。)
