Question

什么是同余式？

Answer 1

同余式的意义：

表示同余关系的数学表达式，与等式相似。将等式中的等号“=”换成同余符号“≡”，必要时在式尾缀以(mod m) 注明模m（即除数），就是同余式。

含有未知数的同余式叫做同余方程，通常要求整数解。

定义：

如果两个正整数 a和 b之差能被 n整除，那么我们就说 a和 b对模n同余，记作：

a ≡b  (mod n)

运算：

同余式运算类似于等式的运算，在等号两边可进行加减乘除的算术运算。如 a≡b (mod n) ，则有：

a + c ≡b + c  (mod n)

a -  c ≡b - c  (mod n)

a ·c ≡b ·c  (mod n)

但在应用除法运算时应特别注意:

若c与n互质,则有 a / c ≡ b / c ( mod n )

简单解释: 如果ac≡bc(mod m)，且c和m互质，则a≡b(mod m) （就是说同余式两边可以同时除以一个和模数互质的数）。
证明：条件告诉我们，ac-mp = bc-mq，移项可得ac-bc = mp-mq，也就是说(a-b)c = m(p-q)。这表明，(a-b)c里需要含有因子m，但c和m互质，因此只有可能是a-b被m整除，也即a≡b(mod m)。

若a / c ≡ b / c ( mod n ) , 则不一定有c与n互质.

反例: 4 ≡ 64 (mod 10)   两边同除以c = 2 (n = 10)

2 ≡ 32 (mod 10)