同余的性质：深入解析

定理11.5 （带余除法定理）设n为不等于0的整数，则任意整数a可唯一表示为如下形式：

a=nq+r，q和r为整数且0≤r＜|n|

q和r分别称为a除以n的商和余数。将r定义为a mod n，即a mod n=r。注意，0≤a mod n＜n。

【例11-8】 由于5=1×3+2

所以5 mod 3≡2

又由于-5=（-2）×3+1

所以-5 mod 3≡1

定义11.3 对于整数a、b和正整数n，如果

a mod n≡b mod n则称a和b模n同余，记为a≡b（mod n），n称为模数。

【例11-9】 由于 9 mod 5≡4，-1 mod 5≡4

故 9≡-1（mod 5）

定理11.6 a≡b（mod n）与以下条件等价：

1）a=nt+b，t∈Z；

2）n|（a-b）。

定理11.7 模n的同余关系是整数集合上的等价关系，即具有下列性质。

自反性：a≡a（mod n）。

对称性：如果a≡b（mod n），则b≡a（mod n）。

传递性：如果a≡b（mod n），b≡c（mod n），则a≡c（mod n）。

因此，利用模n的同余关系能将整数划分为n个等价类{[0]，[1]，…，[n-1]}，叫做模n的剩余类。每一个剩余类是余数相同的元素的集合，如剩余类[0]表示所有能够被n整除的整数的集合，而[1]表示所有被n整除后余数为1的整数的集合。

在每一个剩余类中取一个元素构成模n的一个完全剩余系。0，1，2，…，n-1是模n的一个完全剩余系，称为最小非负完全剩余系。模n的完全剩余系中的元素两两模n不同余。

同余具有以下性质：(www.xing528.com)

1）对于整数{a_i|i=1，2，…，t}和{b_i|i=1，2，…，t}，如果a_i≡b_i（mod n）（i=1，2，…，t），则

a₁+a₂+…+a_t≡b₁+b₂+…+b_t（mod n）

a₁a₂…a_t≡b₁b₂…b_t（mod n）

2）如果a+b≡c（mod n），则a≡c-b（mod n）；

3）如果a≡b（mod n），则a+nk≡b（mod n），k为整数；

4）如果a≡b（mod n），则a^m≡b^m（mod n）；

5）如果a≡b（mod n），s为正整数，则as≡bs（mod ns）；

6）如果a≡b（mod n），且a=a₁k，b=b₁k，n=n₁k，k为正整数，则a₁≡b₁（mod n₁）；

7）如果a≡b（mod n），k是n的正因子，则a≡b（mod k）；

8）如果a≡b（mod n），且d|a，d|n，则d|b。

下面通过两个例子来介绍同余性质的基本应用。

【例11-10】 判断5874192是否能被3整除。

【解析】 因为10ⁿ≡1（mod 3），其中n是正整数，

所以5874192=5×10⁶+8×10⁵+7×10⁴+4×10³+1×10²+9×10+2≡（5+8+7+4+1+9+2）（mod 3）≡36（mod 3）≡0（mod 3）

故3|5874192。

【例11-11】 2005年7月26日是星期二，问此天后第2¹⁰⁰⁰天是星期几。

【解析】 依题意，需要求2¹⁰⁰⁰mod 7。

因为 2³≡1（mod 7）

所以 2¹⁰⁰⁰=2⁹⁹⁹×2=（2³）333×2≡2（mod 7）

则第2¹⁰⁰⁰天是星期四。