整数論2 合同一次方程式と中国式剰余定理

　 $ax \equiv b \pmod m$ の形の方程式を合同一次方程式という．またそれらの連立方程式の解を与える中国式剰余定理について紹介する．

一次合同方程式： $a,b,n \in \mathbb{Z},a\neq 0,n \gt 0$ とする． $k =\mathrm{gcd}(a,n)$ とするとき合同方程式$$ax \equiv b \pmod{n}$$の解は $k\mid b$ ならば $n$ を法として $k$ 個存在する．また $k \nmid b$ ならば解を持たない．

証明： $ax-ny=b$ となる整数 $x,y$ が存在するとする．左辺は $k$ を約数に持つので $k|b$ となる．従って $k \nmid b$ ならば解を持たない． $ax-ny=k$ は整数解を持つことは整数論1（定理２）で示している．解の１つを $x_0, y_0$ とする．２つの式を引き算すると$$a(x-x_0) + n(y -y_0)=0$$となる．両辺 $k$ で割ると$$a'(x - x_0) + n'(y - y_0)=0\ \ \ \ (a'=\frac{a}{k}, n'=\frac{n}{k})$$となる． $\mathrm{gcd}(a', n')=1$ より$$x \equiv x_0 \pmod{n'}$$となる．従って$$x \equiv x_0,x_0 + n', \dots , x_0 + (k - 1)n' \pmod{n}$$となる．（証明終了）

中国式剰余定理： $m_1,m_2, \dots ,m_n$ をどの２つとも互いに素な自然数とする．整数 $b_1,b_2 ,\dots ,b_n$ に対し連立合同方程式 \begin{eqnarray*} x &\equiv &b_1 \pmod{m_1} \\ x &\equiv &b_2 \pmod{m_2} \\ &\dots& \\ x &\equiv &b_n \pmod{m_n} \end{eqnarray*} の解は $M=m_1*m_2* \cdots *m_n$ を法として１個存在する．

証明： 解の存在：$$M=m_1M_1=m_2M_2= \cdots = m_n M_n$$として $M_1,M_2,\dots , M_n$ を定める．定義より$$\mathrm{gcd}(m_i,M_i)=1\ \ \ (i=1,2,\dots , n)$$である．整数論1（定理２）より任意の $i$ に対し \begin{equation}\label{iti} M_it_i \equiv 1 \pmod{m_i} \end{equation} を満たす $t_i$ が存在する．従って$$x \equiv \sum_{i=1}^n M_it_ib_i$$は連立合同方程式を満たす．実際 $m_i$ で $x$ を割ると $i \neq j$ において $m_i | M_j$ より$$x \equiv m_iM_it_i \pmod{m_i}$$が成り立ち， $(\ref{iti})$ より$$x \equiv b_1 \pmod{m_i}$$となる．
解の一意性： $x,y$ が解とする．このとき任意の $i$ に対し$$x_i \equiv y_i \pmod{m_i}$$が成り立つ． $\{m_i\}_{i=1}^n$ は互いに素より$$x\equiv y \pmod{M}$$となる．従って $M$ を法として一意性が成り立つ．（証明終了）

　以下は合同一次式と中国式剰余定理を用いた連立合同方程式を解くコード．整数論1で定義したmoduleをimportとしている．

# coding: utf-8

import euclidian_algorithm as ea

def solve_cong_eq(a, b, n):
    #ax = b mod(n)のmod(n)解をリストで返す関数
    if a == 0: raise ValueError("aに0が代入されてます")
    elif n <= 0: raise ValueError("n<=0となっています")
    else:
        k = ea.Euclid(a, n)                                            # 最大公約数を与える関数
        if b % k != 0: return None                                     # 解なし
        else:
            b = b // k
            x0, y0 = ea.Bezout_identity(a, n)                          # ax0 + ny0 = gcd(a,n)の特殊解x0, y0を与える関数
            x0 = b * x0
            return sorted([(x0 + (n // k) * i) % n for i in range(k)]) # 0 ~ m - 1 の間で小さい順 

def chinese_rem(l):
    """"
    l: [(b1,m1),(b2,m2),...,(bn,mn)]
    x = b1 mod m1
    x = b2 mod m2
      ...
    x = bn mod mn
    のM = m1 * m2 * ... * mnを法とした解x (0 <= x < M)を返す関数
    """

    for i in range(len(l) - 1):
        if l[i][1]  <= 0: raise ValueError("n<=0となっています")
        for j in range(i + 1, len(l)):
            if ea.Euclid(l[i][1], l[j][1]) != 1: raise ValueError("互いに素ではありません") 
    if l[len(l) - 1][1] <= 0: raise ValueError("n <= 0となっています")
    M = 1
    for i in range(len(l)):  
        M = M * l[i][1]
    M_list = [M // l[i][1] for i in range(len(l))]
    t_list = [ea.Bezout_identity(M_list[i], l[i][1])[0] for i in range(len(l))]
    x = 0
    for i in range(len(l)):
        x += l[i][0] * M_list[i] * t_list[i]
    return x % M

if __name__ == "__main__":
    for a, b, n in [(3, 12, 15), (-12, 6, 30), (3, 2, 15)]:
        print("{0}x={1}   mod({2})".format(a, b, n))
        print("解：{0} mod {1}".format(solve_cong_eq(a, b, n), n))
        print("############################################")

    l = [(1, 2), (3, 7), (-3, 13)]
    M = 1
    for b, m in l:
        print("x = {0} mod({1})".format(b, m))
        M *= m
    print("解：x={0} mod({1})".format(chinese_rem(l), M))

3x=12 mod(15)

解：[4, 9, 14] mod 15

############################################

-12x=6 mod(30)

解：[2, 7, 12, 17, 22, 27] mod 30

############################################

3x=2 mod(15)

解：None mod 15

############################################

x = 1 mod(2)

x = 3 mod(7)

x = -3 mod(13)

解：x=101 mod(182)