同余（一）

欢迎大家来到IT世界,在知识的湖畔探索吧!

在二年级我们第一次正式接触了带余除法，

根据实际意义，我们知道余数一定比除数小，若余数比除数大，对应图片中搭正方形的情景，余下的超过4根，便可再继续搭正方形。如果固定除数，以图片中的4为例，有

13÷4=3……1

17÷4=4……1

21÷4=5……1

25÷4=6……1

虽然被除数在变化，但余数都是1。有了同余定义后，我们就说13和17是模4同余的。

在日常生活中，同余的概念是经常出现的。例如钟表的指针，它表示的小时数是除以12同余的；若12月1号是周日，很容易就知道12月8号、15号、22号、29号也是周日。下面给出同余的定义。

有了同余的定义，我们再来看

13÷4=3……1 ①

17÷4=4……1 ②

此时13≡17（mod 4），继续思考②-①，得到17-13=4×1，即4|(17-13).抽象的看对于a≡b（mod m），可知

a÷m=q……r ③

b÷m=p……r ④

用③-④有 a-b=(q-p)×m，故m|(a-b). 反之，若m|(a-b)，可知

(a-b)≡0（mod m）, 由此易知

a≡b（mod m）. 所以a和b是模m同余的。

综上分析可知

a≡b（mod m） iff m|(a-b).

特别的

a≡0（mod m） iff m|a.

换句话说，整除也可以由同余来定义。注:iff 意思是 当且仅当。

通过以上分析, 可知以下命题是等价的：

1. a和b是模m同余的,即a≡b（mod m）.

2. 存在整数k, 使得a=b+km.

3. m整除a-b，即m|(a-b).

同余符号记法的优点:在形式上同余式具有普通等式的性质。对于等式来说，有

1. 恒有a=a.

2. 若a=b, 则b=a.

3. 若a=b, b=c, 则a=c.

性质

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）.

证明 只证明第3条性质，只需证明 m|(a-c).

由于

a≡b（mod m）,

b≡c（mod m）,

可知

m|(a-b),

m|(b-c),

因此存在整数q, p使得

a=b+qm,

b=c+pm,

所以

a=b+qm，

c=b-pm,

两式相减

a-c=(q+p)m,

知

m|(a-c). □

注:对于普通等式有 a-b=0 iff a=b,

同余式也有

(a-b)≡0（mod m） iff a≡b（mod m）