第8章連立一次合同式

第 8 章連立一次合同式
8.1
解の存在と一意性
複数の１次合同式を同時に満たす整数解について考える。
定理 8.1 自然数 n1 、n2 、· · · 、nk がどの二つも互いに素であるとする。このとき、任意の a1 、· · · 、ak に対して、連
立一次合同式

x ≡ a1




 x ≡ a2





x ≡ ak
(mod n1 )
(mod n2 )
..
.
(mod nk )
(8.1)
を満たす解は、積 N = n1 · · · nk を法としてただ一つ存在する。
注 : この定理は、古代中国の「孫子算経」という本にあるそうで、中国では「孫子剰余定理」、一般には、「中国式剰余
定理（ “Chinese Reminder Theorem”）と呼ばれる。（終）
（証明）解の存在 : Ni := N/ni とおく。ni は、n1 、· · · 、ni−1 、ni+1 、· · · 、nk と互いに素なので、gcd (Ni , ni ) = 1。
よって、命題 6.7 より、
Ni ui ≡ 1 (mod ni )
を満たす整数 ui が ni を法としてただ一つ存在する。このとき、
x0 = N1 u1 a1 + · · · + Nk uk ak
とすると、u1 と Ni のとり方から、
N1 u1 ≡ 1,
N2 ≡ N3 ≡ · · · ≡ Nk ≡ 0 (modn1 )
となるので、
x 0 ≡ 1 · a1 + 0 + · · · + 0
= a1
(mod n1 )
となる。同様に、
x0 ≡ ai
(mod ni )
がなりたつ。ゆえに、x = x0 は解のひとつであり、その存在がいえた。
一意性 : (8.1) の任意の解を x1 とするとき、x1 ≡ x0 (mod N ) がいえればよい。各 i につき
x1 ≡ ai ≡ x0
(mod ni )
である。すなわち、x1 − x0 は n1 、· · · 、nk のいずれでも割り切れる。したがって、系 3.6 により、x1 − x0 は仮定から
それらの積 N で割り切れる。つまり x1 ≡ x0 (modN ) となるので、解はただひとつ。（証明終）
39
8.2
解法
連立一次合同式の解法 : 連立一次合同式 (8.1) は次のように解くことができる。
(1) N = n1 · · · nk とおき、各 i について Ni = N/ni とおく。
(2) 各 i について、一次合同式
Ni ui ≡ 1
(mod ni )
を満たす ui をひとつ求める。
(3) (8.1) の解は
x0 =
k
∑
N i u i ai
i=1
で与えられ、N を法として x = x0 ただひとつである。
例 : 連立一次合同式


 x≡2
x≡3


x≡2
(mod 3)
(mod 5)
(mod 7)
を解く。上の解法における N にあたる数は 3 · 5 · 7 = 105、N1 にあたる数は 105/3 = 35、N2 にあたる数は 105/5 = 21、
N3 にあたる数は 105/7 = 15 であるから、３つの合同式
35u1 ≡ 1 (mod 3)
21u2 ≡ 1 (mod 5)
15u3 ≡ 1 (mod 7)
を考えればよい。各々の合同式の解のひとつとして、
u1 = 2,
u2 = 1
u3 = 1
が取れるから、考えている連立一次合同式の解は
35 · 2 · 2 + 21 · 1 · 3 + 15 · 1 · 2 = 140 + 63 + 30 = 233 ≡ 23 (mod 105)
となるので、解は x ≡ 23 (mod 105) のただひとつになる。（例終）
問題 : 次の連立一次合同式を解け。
{
(1)
x ≡ 3 (mod 7)
x ≡ 4 (mod 11)
(2)


 x≡1
x≡2


x≡4
40
(mod 2)
(mod 3)
(mod 5)
(3)


 x ≡ 1 (mod 2)
x ≡ 1 (mod 3)


x ≡ 6 (mod 7)

Download Report