同余定理

一、定义

同余定理是数论中的重要概念。

设m是非零整数，如果两个整数a和b满足a-b能够被m整除，即m|(a-b)，则称整数a与b对模m同余，记作a≡b(mod m)。

用另外一种更直观的方法解释就是：

两个整数a、b，若它们除以整数m所得的余数相等，则称a与b对于模m同余或a同余于b模m。

对模m同余是整数的一个等价关系。

若a-b不能够被m整除，则称a和b模m不同余,记作a≠b( mod m）。

二、性质

1.反身性：a≡a (mod m)；

2.对称性：若a≡b(mod m)，则b≡a (mod m)；

3.传递性：若a≡b(mod m)，b≡c(mod m)，则a≡c(mod m)；

4.同余式

(1)同余式相加：若a≡b(mod m)，c≡d(mod m)，则a± c≡b±d(mod m)。

(2)同余式相乘：若a≡b(mod m)，c≡d(mod m)，则ac≡bd(mod m)。

以上两个也就是线性运算。

(3)若 ac≡bc( mod m),则a≡b(mod(m/(c,m))。

特别地,当(c,m) =1时有a≡b( mod m)。

(4)若a≡b ( mod m),d|m,则a≡b( mod d)。

(5)若a≡b ( mod m),d≠0,则 da≡db ( mod dm);反之亦然。

(6)若a≡b( mod m),(1≤i≤n),则a≡b(mod{m₁,⋯,m_n});反之亦然。

5.线性运算：如果a ≡ b (mod m)，c ≡ d (mod m)，那么

(1)a ± c ≡ b ± d (mod m)；

(2)a * c ≡ b * d (mod m)。

6.除法：

若ac≡bc(mod m),则a≡b(mod(m/(c,m))。

特别地,当(c,m) =1时有a≡b(mod m)。

7.幂运算：

如果a≡b(mod m)，那么aⁿ≡bⁿ(mod m) ；

8.若a≡b(mod m)，n=m，则a≡b(mod n)。

三、相关定理

1.费马小定理: 

若p为质数，则a^p≡a(mod p) 即a^p-1≡1(mod p) （但是当p|a时不等价）。

2.中国剩余定理（孙子定理）：

孙子定理是中国古代求解一次同余式组（见同余）的方法。是数论中一个重要定理。又称中国余数定理。一元线性同余方程组问题最早可见于中国南北朝时期（公元5世纪）的数学著作《孙子算经》卷下第二十六题，叫做“物不知数”问题，原文如下：

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。《孙子算经》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理。