User:Fungwan39/沙盒

孙子定理的补充

要用孙子定理，同余方程组的模数必须是两两互质，否则孙子定理就不能运用。本文就是说明如何解除这种限制。见中国剩余定理。

关于如何解非两两互质模的同余方程组，在中国剩余定理结尾部分亦有提及。

同余定义和运算[编辑]

如果整数a和b的差能被正整数M所整除，便可以记为　　　

   a ≡ b  (mod M).

念：a同余于b模M。 M称为模。“≡” 是同余符号，为德国数学家高斯首先使用。同余符号的两边除以M，则得出的余数相等。下面是简单的运算。^[1]

例如：　　　　　　　

  　92 ≡ 37  (mod 5).
  　30 ≡ 0   (mod 5).

    " => " 表示暗示或者导出。 
    a ≡ b (mod m)      
    =>  a ≡ b + n*m (mod m)   (n 是任何整数）

    a ≡ b (mod m)      
    =>  a ≡ b - n*m (mod m)   (n 是任何整数）

    a≡a', b≡b'  (mod m)  (a' 和 b' 是指比 m 小的非负值余数，下同）    
    =>  a + b ≡ a' + b'  (mod m)

    a≡a', b≡b'  (mod m)      
    =>  a - b ≡ a' - b'  (mod m)

   a≡a', b≡b'  (mod m)      
    =>  a * b ≡ a' * b'  (mod m)

   473 ≡ 3 , 936 ≡ 1 , 2054 ≡ 4 (mod 5)
   => 473 + 936 - 2054 ≡ 3 + 1 - 4 ≡  0  (mod 5)

   (231)*(724)*(329) ≡ 6*4*5  ≡ 24*5 ≡ 6*5 ≡ 30 ≡ 3  (mod 9)

   9*X + 12 ≡ 4*X - 3   (mod 11) ,
   5*X  ≡ -15 + 2*11    (mod 11) ,
   5*X  ≡  7        　  (mod 11) ,
   两边乘9，9是5的模反元素 (mod 11)
   45*X ≡ （-15）(9） 　 (mod 11) ,
   1*X  ≡ （-4）（9） 　 (mod 11) , 
   X  ≡ -36 + 4*11 ≡ 8  (mod 11)．

应用题例子：

   今天是星期三，15天前星期几？ 
       X ≡ 3 - 15 ≡ -12 ≡ -12 + 7 + 7 ≡ 2 (mod 7).   
   
   现在是上午九点，85小时后几点？
       X ≡ 9 + 85 ≡ 94 ≡ 94 - 3*24 ≡ 22 (mod 24).
   
   用模9证明 234156 * 912533 = 213,675,067,148 是错的。
   先求左边的模9的余数 234156 * 912533 ≡（2+3+4+1+5+6)(9+1+2+5+3+3）≡（21)(23) ≡ (3)(5) ≡ 15 ≡ 6 (mod 9).    
   再求右边的模9的余数 213,675,067,148 ≡ 2+1+3+6+7+5+0+6+7+1+4+8 ≡ 50 ≡ 5+0 ≡ 5 (mod 9). 
   左右的余数不同，所以原答案是错的。

   生肖排列是：1鼠 2牛 3虎 4兔 5龙 6蛇 7马 8羊 9猴 10鸡 11狗 12猪
   如果今年是狗年，老翁已79岁，问老翁属什么生肖？
       X ≡ 11 - 79 ≡ -68 ≡ -68  + 6*12 ≡ 4 （兔） (mod 12)。

   密码学和同余方程式有密切关系，下面是一个例子。
   假设秘密公式是： y ≡ x*a - b (mod 10).
   y是加密数字, x是原来数字，a和b是密钥。
   a=7，b=3。密钥是经常改换的。
   如果原文是0123456789，问密文是什么？
   y ≡ 0*7 - 3 ≡ -3 + 10 ≡ 7 (mod 10)   (0的加密数字是7）
   y ≡ 1*7 - 3 ≡ 4           (mod 10)   (1的加密数字是4）
   y ≡ 2*7 - 3 ≡ 11 ≡ 1      (mod 10)   (2的加密数字是1）
   等等。
   0123456789 的密文是7418529630。
   本题的解密公式是：x ≡ (y + 3)*3 (mod 10).
   中文电码用四个数字代表一个中国字。加密中文就需要多用一个程序。

非两两互质模的同余方程组[编辑]

非两两互质模的一元线性同余方程组至少有两个方程式的两个模有大于1的公约数：

     (S）：
           X ≡ a  (mod P*j) 
           X ≡ b  (mod P*k).
      其中P大于1，是两模的公约数，造成两模非互质。

例如

       （S）：                        
             X ≡ 3  (mod 2*3)                            
             X ≡ 5  (mod 2*2*2) .                    
       （S）：
             X ≡ 11  (mod  $3^{3}$ ) ,
             X ≡ 44  (mod  $3^{2}*7$ ) .    
             X ≡ 86  (mod  $7^{2}*2$ )) .

这些同余方程组不能直接用孙子定理解决，因为它们的模不是两两互质。需要经过“暗示方程式”和“分裂方程式”，然后舍弃重复的方程式，新方程组的模成为两两互质，这时才可以用孙子定理解决。

非两两互质模的同余方程组不一定有解。在遇到矛盾的情况，即宣告无解。两两互质模的同余方程组一定有解。

同余暗示定理[编辑]

   如果        a ≡ b  (mod M*N)            
   必存在j满足 （a - b）= （M*N）* j      （同余定义）
   因此       （a - b）=  M * (N*j)    
   也就是      a ≡ b  (mod M).          （同余定义）
   这就证明了同余暗示定理: 如果某同余方程式在模P下成立，那么这同余方程式在模Q （假设Q是P的一个约数）下也成立。
   a ≡ b (P) and Q|P => a ≡ b (Q).  
   Q|P 表示Q能整除P。 
   
   如果    X ≡ 18     (mod 21)  
   也就是  X ≡ 18     (mod 7*3)  
   导出    X ≡ 18 ≡ 4 (mod 7)。       （同余暗示定理）

   如果    X ≡ 10  (mod  $2^{5}*3^{7}$ )  
   导出    X ≡ 10 ≡ 2  (mod  $2^{3}$ )  
          X ≡ 10      (mod  $3^{4}$ )       （同余暗示定理）
   
   如果    X ≡ 103  (mod 2*3*5)  
   导出    X ≡ 103 ≡ 1  (mod 2)    
          X ≡ 103 ≡ 1  (mod 3)
          X ≡ 103 ≡ 3  (mod 5)
          X ≡ 103 ≡ 1  (mod 6)
          X ≡ 103 ≡ 13 (mod 15)
          X ≡ 103 ≡ 3  (mod 10).     （同余暗示定理）

虽然没有明写，这些导出都是原方程式的属性，故称暗示定理。 X ≡ 18 (mod 21) 可以暗示 X ≡ 18 ≡ 4 (mod 7) ，但是 X ≡ 4 (mod 7) 却不能暗示 X ≡ 18 (mod 21)。因此这导出过程是不可逆的。同余暗示定理是解同余方程式的有力工具。

同余分裂定理[编辑]

  如果 X ≡ R  (mod p*q*r)
  而且p，q， r 两两互质
  那么  这方程式可分裂成
  （S）：
         X ≡ R  (mod p)
         X ≡ R  (mod q)
         X ≡ R  (mod r).
  如果用孙子定理解这方程组，它的解正是原方程式：
         X ≡ R  (mod p*q*r).

说明了这分裂是可逆的。分裂前的方程式和分裂后的方程组有相同的答案的。分裂定理就是孙子定理的逆过程。

  例如  X ≡ 120  (mod 5*7*9)
  由于5，7，9 两两互质
  可以分裂成
      （S）：
         X ≡ 120 ≡ 0    (mod 5)
         X ≡ 120 ≡ 1    (mod 7)
         X ≡ 120 ≡ 3    (mod 9).   （同余分裂定理）
   如果用中国剩余定理解之，便可得出和原来方程式一样的答案：
       X ≡ 120  (mod 315) 。      （315 就是5，7，10的LCM）
       X = 120 + 315n, n 是任何整数。

证明：

   假设  $m_{1},m_{2},\cdots ,m_{n}$  两两互质。
   M =  $m_{1}*m_{2}*\cdots *m_{n}$ 
   X ≡ a  (mod M ) 分裂成
    $(S):\quad \left\{{\begin{matrix}x\equiv a{\pmod {m_{1}}}\\x\equiv a{\pmod {m_{2}}}\\\vdots \qquad \qquad \qquad \\x\equiv a{\pmod {m_{n}}}\end{matrix}}\right.$ 
   用孙子定理解这方程组，假设得出
   X ≡ b  (mod M ) （这模是方程组各模之积）
   另外，从方程组的建成，说明了a 是方程组的一个解。
   又因为孙子定理已经证明在模M的意义下，方程组（S）只有一个解。 
   所以证明了 a 就是 b 。

因此，当某个同余方程组的某个方程式分裂了，而且分裂后的模两两互质，那么分裂不会影响原方程组的解。

用暗示和分裂定理可以舍弃多余的方程式从而运用孙子定理解题[编辑]

从一般形式的非互质同余方程组来看

     (S）：
           X ≡ a  (mod  $P^{n}*k$   ) 
           X ≡ b  (mod  $P^{m}*j$   )   
       其中P 是一个质数，m和n 是正整数，而且 $m\geqslant n$  , k和j 都没有约数P。
       可见  $P^{n}$  是两模数的公约数，造成两模数非互质。
       首先可以分裂第一方程式，因为k没有约数P，分裂后的两模互质。
       然后原题目的第二方程式可以暗示 X ≡ b（mod  $P^{n}$ ) 。（  $m\geqslant n$ ）
     (S）：
           X ≡ a (mod  $P^{n}$ )，X ≡ a  (mod  $k$ ）    
           X ≡ b (mod  $P^{m}*j$ )。 （导出 X ≡ b (mod  $P^{n}$ )）
       比较 X ≡ a (mod  $P^{n}$ ) 和 导出的 X ≡ b (mod  $P^{n}$ ) ，
       如果有矛盾即宣告无解，
       如果相同即可舍弃 X ≡ a  (mod  $P^{n}$ )。
       如果方程组的模仍非互质，就找出共有的质数，重来一次。舍弃多余的方程式，或者宣告无解。
       直至两模数互质, 便可以用孙子定理解题.

如方程式较多，模共有的质数较多，一般的解决程序是：

       (一) 把模写成质数的乘积，相同质数的积用指数表示。 
       例子(S）：
          （P，Q，R，S是不同的质数） 
           X ≡ a (mod  $P^{3}*Q^{2}$ )，
           X ≡ b (mod  $P^{3}*R^{2}$ )， 
           X ≡ c (mod  $P^{2}*Q^{3}*R*S$ ). 
       (二) 把共有质数的模的方程式分裂
       例子(S）：
           X ≡ a (mod  $P^{3}$ )，
           X ≡ a (mod  $Q^{2}$ )，           
           X ≡ b (mod  $P^{3}$ )， 
           X ≡ b (mod  $R^{2}$ )， 
           X ≡ c (mod  $P^{2}$  ), 
           X ≡ c (mod  $Q^{3}$  ), 
           X ≡ c (mod  $R$  ), 
           X ≡ c (mod  $S$  ). 
       (三) 把相同模的方程式进行比较。如有矛盾，则无解。否则舍弃其中一个。
        从相同质数而指数较高的模的方程式，导出指数较低的模的方程式。
        如有矛盾，则无解。否则舍弃指数较低的一个。
       例子(S）：
           X ≡ a (mod  $P^{3}$ )， 舍弃
           X ≡ a (mod  $Q^{2}$ )， 舍弃           
           X ≡ b (mod  $P^{3}$ )， 导出X ≡ b (mod  $P^{2}$ )  
           X ≡ b (mod  $R^{2}$ )， 导出X ≡ b (mod  $R$ )
           X ≡ c (mod  $P^{2}$  ), 舍弃
           X ≡ c (mod  $Q^{3}$  ), 导出X ≡ c (mod  $Q^{2}$ )  
           X ≡ c (mod  $R$  ),   舍弃
           X ≡ c (mod  $S$  ).   保留
       (四) 这时模数两两互质，可以用孙子定理解答。
        新(S）：
           X ≡ b (mod  $P^{3}$ )， 
           X ≡ b (mod  $R^{2}$ )，  
           X ≡ c (mod  $Q^{3}$  ), 
           X ≡ c (mod  $S$  ).

例一[编辑]

      （S）：
             X ≡ 4  (mod 9），　                                
             X ≡ 31 (mod 108) .　
       把模写成质数的积和相同质数的幂。　　　　　　　　　
      （S）：
             X ≡ 4  (mod  $3^{2}$ )， 
             X ≡ 31  $3^{3}*4$ ). 
       从  X ≡ 31   $3^{3}*4$ )  导出
             X ≡ 31 ≡ 4 (mod  $3^{2}$ )，  
       舍弃重复   
             X ≡ 4 (mod  $5^{2}$ )。   （原第一方程式）    
       本题答案就是       
             X ≡ 31 (mod 108) 
              $X=31+108k,\;k\in \mathbb {Z} .$  
       答案也满足原方程组。

例二[编辑]

     （S）：
            X ≡ 16 (mod 49) ，
            X ≡ 9  (mod 77) ，
            X ≡ 9  (mod 121) . 
      把模写成质数的积和相同质数的幂。 
     （S）：
            X ≡ 16  (mod  $7^{2}$ )，    
            X ≡ 9  ( mod 7*11 ) ，
            X ≡ 9  (mod  $11^{2}$  )，     .
      分裂第二方程式。
      （S）：
            X ≡ 16  (mod  $7^{2}$ )，     
            X ≡ 2  (mod 7) ，X ≡ 9  (mod 11)，      
            X ≡ 9  (mod  $11^{2}$  ) .
       从  X ≡ 16  (mod  $7^{2}$ ) 导出
            X ≡ 16 ≡ 2 (mod 7 )  
       舍弃重复   
            X ≡ 2 (mod 7) .         (这是分裂出的方程式）    
       从  X ≡ 9  (mod  $11^{2}$  ) 导出
            X ≡ 9 (mod 7 )  
       舍弃重复  
            X ≡ 9 (mod 7) .         (这是分裂出的方程式）  
       新（S）：
            X ≡ 16 (mod 49) 
            X ≡ 9  (mod 121) . 
       用孙子定理解题 
            X  ≡ 3397  (mod 5929) .  （5929是49和121的LCM）
             $X=3397+5929k,\;k\in \mathbb {Z} .$  
       这答案也满足原来方程组。

例三[编辑]

       (S）：                      
           X ≡ 0   (mod 200 ) ,
           X ≡ 184 (mod 200 ) ,
           X ≡ 100 (mod 38500 ) .
       将模写成各质数的积。
       (S）：                      
           X ≡ 0   (mod  $2^{3}*5^{2}$ )，
           X ≡ 184 (mod  $2^{3}*7^{2}$ )， 
           X ≡ 100 (mod  $2^{2}*5^{3}*7*11$ ). 
       分裂有共同质数的模的方程式。         
        (S）：                      
           X ≡ 0   (mod  $2^{3}$ )，
           X ≡ 0   (mod  $5^{2}$ )，
           X ≡ 184 ≡ 0 (mod  $2^{3}$ )，
           X ≡ 184 ≡ 37 (mod  $7^{2}$ )，
           X ≡ 100 ≡ 0 (mod  $2^{2}$ )，
           X ≡ 100 (mod  $5^{3}$ ), 
           X ≡ 100 ≡ 2 (mod  $7$ )， 
           X ≡ 100 ≡ 1 (mod  $11$ ). 
                
        从 X ≡ 184 ≡ 0 (mod  $2^{3}$ )，导出
           X ≡ 0 (mod  $2^{2}$ )，  
        舍弃重复   
          X ≡ 0 (mod  $2^{3}$ )，
          X ≡ 100 ≡ 0 (mod  $2^{2}$ )。
             
        从 X ≡ 184 ≡ 37 (mod  $7^{2}$ )，导出
          X ≡  37 ≡ 2   (mod  $7$ )，  
        舍弃重复   
          X ≡ 100 ≡ 2 (mod  $7$ )。
      
        从 X ≡ 100 (mod  $5^{3}$ )，导出
          X ≡ 100 ≡ 0 (mod  $5^{2}$ )，  
        舍弃重复   
          X ≡ 0 (mod  $5^{2}$ )。
        
        舍弃前都没有发现矛盾现象。  
 
        新(S）：                      
           X ≡ 0 (mod  $2^{3}$ )，
           X ≡ 37 (mod  $7^{2}$ )，
           X ≡ 100 (mod  $5^{3}$ )， 
           X ≡ 1 (mod  $11$ ).
        用孙子定理解题，得
           X ≡ 38600 (mod 539000） 
           539000 = LCM（8，125，49，11）
            $X=38600+539000k,\;k\in \mathbb {Z} .$  
        答案也满足原方程组。

例四[编辑]

      （S）：
             X ≡ 1  (mod 7) ,                                         
             X ≡ 9  (mod 21) .
       从  X ≡ 9  (mod 7*3) 导出 
             X ≡ 9 ≡ 2 (mod 7) 。 （同余暗示定理）
       但是X ≡ 2 (mod 7)和原第一方程式X ≡ 1 (mod 7)互相矛盾。宣告无解。

例五[编辑]

有鸡蛋一箩。两个两个数，刚好。三个三个数，剩一个。四个四个数，剩两个。五个五个数，刚好。六个六个数，剩四个。七个七个数，剩六个。八个八个数，剩两个。九个九个数，剩四个。问有多少鸡蛋？

        （S）：
             X ≡ 0  (mod 2) ,
             X ≡ 1  (mod 3) ,
             X ≡ 2  (mod 4) ,
             X ≡ 0  (mod 5) ,
             X ≡ 4  (mod 6) ,
             X ≡ 6  (mod 7) ,
             X ≡ 2  (mod 8) ,
             X ≡ 4  (mod 9) .
         须分裂 X ≡ 4  (mod 2*3)
        （S）：
             X ≡ 0  (mod 2) ,    多余？
             X ≡ 1  (mod 3) ,    多余？
             X ≡ 2  (mod  $2^{2}$ )，    多余？
             X ≡ 0  (mod 5) ,
             X ≡ 4 ≡ 0 (mod 2)， X ≡ 4 ≡ 1 (mod 3),    先分裂，多余？
             X ≡ 6  (mod 7) ,
             X ≡ 2  (mod  $2^{3}$ )， 暗示 X ≡ 2 ≡ 0(mod 2)
                              也暗示 X ≡ 2 (mod  $2^{2}$ )   
             X ≡ 4  (mod  $3^{2}$ )， 暗示 X ≡ 4 ≡ 1(mod 3)
       比较各个 X ≡ 0(mod 2)，X ≡ 2 (mod 4) 和 X ≡ 1 (mod 3)。          
       没有发现矛盾，舍弃所有多余的。 
       新（S）：
             X ≡ 0  (mod 5)
             X ≡ 6  (mod 7)
             X ≡ 2  (mod 8)
             X ≡ 4  (mod 9).
        模数两两互质，可以用孙子定理解答。
        答案：X≡ 1210 只鸡蛋 (mod 2520). 也满足原来方程组。
        2520 是5，7，8，9的LCM。
        X = 1210 + 2520n （n是任何自然数）。

^ Wolfram Mathworld. Congruence.

[1] Wolfram Mathworld. Congruence.

[1]