模运算与同余公式的性质

2019-04-13 12:21发布

       所谓的同余,顾名思义,就是许多的数被一个数d去除,有相同的余数。d数学上的称谓为模。如a=6,b=1,d=5,则我们说a和b是模d同余的。因为他们都有相同的余数1。
       数学上的记法为:
       a≡ b(mod d)
       可以看出当n 对于同余有三种说法都是等价的,分别为:
       (1) a和b是模d同余的.
       (2) 存在某个整数n,使得a=b+nd .
       (3) d整除a-b.
       可以通过换算得出上面三个说法都是正确而且是等价的.
       基本定律:
       同余公式也有许多我们常见的定律,比如相等律,结合律,交换律,传递律….如下面的表示:
       1)a≡a(mod d)
       2)对称性 a≡b(mod d)→b≡a(mod d)
       3)传递性 (a≡b(mod d),b≡c(mod d))→a≡c(mod d)
       如果a≡x(mod d),b≡m(mod d),则
           4)a+b≡x+m (mod d)
           5)a-b≡x-m (mod d)
           6)a*b≡x*m (mod d )
           7)a/b≡x/m (mod d)
       8)a≡b(mod d)则a-b整除d
       9)a≡b(mod d)则a^n≡b^n(mod d)
      10)如果ac≡bc(mod m),且c和m互质,则a≡b(mod m)
      模运算的运算规则:
      (a + b)  mod  p = (a  mod  p + b  mod  p)  mod  p            (1)
      (a - b)  mod  p = (a  mod  p - b  mod  p)  mod  p              (2) 
      (a * b)  mod  p = (a  mod  p * b  mod  p)  mod  p              (3)
      a^b  mod  p = ((a  mod  p)^b)  mod  p                              (4)
      结合率: ((a+b)  mod  p + c)  mod  p = (a + (b+c)  mod  p)  mod  p (5)
                     ((a*b)  mod  p * c) mod  p = (a * (b*c)  mod  p)  mod  p     (6)
      交换率: (a + b)  mod  p = (b+a)  mod  p                 (7)
                     (a * b)  mod  p = (b * a)  mod  p                 (8)
      分配率: ((a +b) mod  p * c)  mod  p = ((a * c)  mod  p + (b * c)  mod  p)  mod  p (9)
      重要定理:若a≡b ( mod  p),则对于任意的c,都有(a + c) ≡ (b + c) ( mod p);(10)
                        若a≡b ( mod  p),则对于任意的c,都有(a * c) ≡ (b * c) ( mod p);(11)
                        若a≡b ( mod  p),则对于任意的c,都有ac≡ bc ( mod p);     (13)

本文地址:http://blog.csdn.net/a359680405/article/details/41675143