abstract

讨论整数之间的整除关系后,我们要讨论整数之间一种更精细的关系：同余关系.

它的引入极大地丰富了数论的内容，简化了数论中的许多问题.

利用同余关系可以进一步讨论整除；对整数集合进行分类，将彼此同余的整数放在一起，得到一类整数，称为剩余类.每个剩余类可看作一个特殊的“数”.对于这些“数”，我们可以像普通的数一样引入加法、乘法运算.

在此基础上，我们讨论同余方程和同余方程组的解法.同余在初等数论中占有极为重要的地位.

模和同余概念

给定一个正整数 $m$，把它称为模。

如果整数 $a$ 和 $b$ 用 $m$ 去除$(a/m,b/m)$所得的余数相同，就称 $a$ 和 $b$ 对模 $m$ 同余，记作 $a\equiv b(\mathrm{mod}m)$。

• 这里的$a,b$可以是负数

如果余数不同，则称 $a,b$ 对模 $m$ 不同余，记作 $a\not\equiv b(\mathrm{mod}m)$。

简称

对模$m$同余有时称为模$m$同余,或关于模$m$同余

用符号描述:若$a=m{q}_1+r$,$b=m{q}_2+r$, ( r ∈ { 0 , 1 , ⋯ , r − 1 } ) (r\in\set{0,1,\cdots,r-1}) (r∈{0,1,⋯,r−1}),$(q_1,q_2\in \mathbb{Z})$,则$a\equiv b(\mathrm{mod}m)$

符号说明

• $\mathrm{mod}$这个符号是由高斯(Gauss)发明的

• $a\equiv b(\mathrm{mod}m)$是一个完整的符号,涉及3个操作数,称为:" $a$ 和 $b$ 对模 $m$ 同余"

• $a\not\equiv b(\mathrm{mod}m)$同理,称为:" $a$ 和 $b$ 对模 $m$ 不同余"

• 在latex公式的符号中$a\equiv b(\mathrm{mod}m)$可以用a\equiv b \pmod{m}来表示,尤其是其中的\pmod{}专门用于此情形,并强烈建议\pmod带上{ }(花括号),否则容易出现意外的结果,和a\mod{b}并不相通,这种情况$a\mathrm{mod}b$不会自动携带括号,而且mod前后自带空格间距

例

例如，8 和 15 除以 7 都余 1，称 8 和 15 对模 7 同余，记为

$$8\equiv 15(\mathrm{mod}7).$$

又如 34 和 58 除以 12 余数都是 10，称 34 和 58 对模 12 同余，记为

$$34\equiv 58(\mathrm{mod}12).$$

此外$-1=(-1)\times 5+4$,所以$-1$除以5的余数为4(负数除以正数求余数时,一定要把商往负数考虑,同时要控制余数为不超过除数的正数)

例

求证:对任何整数 $x$，总有$x^2\equiv 0$ 或 $1(\mathrm{mod}4)$.

分析:

这个结论描述的是$x^2$可以和谁对模$4$同余,并背出了答案:$x^2$只可能和$0$或$1$中的一个配合对模$4$同余

即$x^2\equiv 0(\mathrm{mod}4))$或$x^2\equiv 1(\mathrm{mod}4)$

1. $x^2$和$0$对模$4$同余
   • 0除以4余0
2. $x^2$和$1$对模$4$同余
   • $1$除以4余$1$

那么问题转换为求证$x^2$除以4余数为0或余数为1这两种可能

证明:

由带余除法定理改写$x$的表达式,可设 $x=4k+r$，$r=0,1,2,3$.

$x^2=(4k+r{)}^2=16k^2+8kr+r^2$ = $4(4k^2+2kr)+r^2$;

$4(4k^2+2kr)+r^2$除以4的余数取决于(等同于)$r^2$除以$4$的余数

$x^2\equiv r^2(\mathrm{mod}4)$

而$r^2=0,1,4,9$,所以$r^2/4$的余数对应分别可能为$0,1,0,1$,也就是只有两种取值可能:$0,1$

所以$x^2\equiv r^2\equiv 0$ 或 $1(\mathrm{mod}4)$.即$x^2\equiv 0$或$1(\mathrm{mod}4)$

同余性质

直接从定义可以得到的基本性质

由定义容易得到以下的基本性质：其中$a,b\in \mathbb{Z}$

1. $a\equiv a(\mathrm{mod}m)$；（自反性）

2. 若 $a\equiv b(\mathrm{mod}m)$，则 $b\equiv a(\mathrm{mod}m)$；（对称性）

3. 若 $a\equiv b(\mathrm{mod}m)$，$b\equiv c(\mathrm{mod}m)$，则 $a\equiv c(\mathrm{mod}m)$。（传递性）

4. 若$a\equiv b(\mathrm{mod}m)$,则可令$c=(a\mathrm{mod}m)=(b\mathrm{mod}m)$,且有$a\equiv b\equiv c(\mathrm{mod}m)$

同余和整除之间的关系👺

整数 $a$, $b$ 对模 $m$ 同余,即$a\equiv b(\mathrm{mod}m)$的充分必要条件是 $m|(a-b)$.

说明:此定理揭示了$a,b,m$三个整数成立的同余关系和整除关系($a\equiv b(\mathrm{mod}m)\iff m|(a-b)$)要么同时成立,要么都不成立;并且我们可以将相对陌生的同余关系问题的研究转换为整除关系进行研究,学习同余关系前,我们对整除关系的性质和定理的认识有了积累

证明:

利用带余除法定理证明

• 必要性

  • 因为$a\equiv b(\mathrm{mod}m)$,可设 $a=m{q}_1+r,b=m{q}_2+r,0\le r<m$, 则$$a-b=m(q_1-q_2),$$即$$m|(a-b).$$

• 充分性

  • 同样利用带余除法,并且构造差式
  • 设 $a=m{q}_1+r_1$, $0⩽r_1<m$, $b=m{q}_2+r_2$, $0⩽r_2<m$, 则$$a-b=m(q_1-q_2)+(r_1-r_2).$$
  • 因为 $m|(a-b)$，所以 $m||r_1-r_2|$.(这里用绝对值$|r_1-r_2|$是一个细节)
  • 但 $|r_1-r_2|<m$，故必有$|r_1-r_2|=0$,即 $r_1=r_2$，即$$a\equiv b(\mathrm{mod}m).$$
  • 补充:这里解释$|r_1-r_2|$
    • $0⩽r_1<m$;$0⩽r_2<m$,将第二个不等式变形为$-m<-r_2⩽0$
    • 第一个和第三个等式合并:$-m<r_1-r_2<m$;从而$|r_1-r_2|<m$,注意不能取等号

相关性质|推论

性质1 同模性质

若 $a\equiv b(\mathrm{mod}m),a_1\equiv b_1(\mathrm{mod}m)$，则

1. $a+a_1\equiv b+b_1(\mathrm{mod}m)$;
   • 显然,由此可知$a+c\equiv b+c(\mathrm{mod}m)$
2. $a{a}_1\equiv b{b}_1(\mathrm{mod}m)$.
3. $ka\equiv kb(\mathrm{mod}m)$，$k$ 为任意整数;
4. $a^n\equiv b^n(\mathrm{mod}m)$，$n$ 为正整数.
   • 这表明,模$m$同余的两个数$a,b$它们各自的$n$次幂也是模$m$同余的
5. 若 $ab\equiv ac(\mathrm{mod}m)$，且 $(a,m)=1$，则 $b\equiv c(\mathrm{mod}m)$.

证明：

根据同余关系和整除关系的性质定理,求证$a+a_1\equiv b+b_1(\mathrm{mod}m)$相当于求证$m|((a+a_1)-(b+b_1))$

同理,求证$a{a}_1\equiv b{b}_1(\mathrm{mod}m)$相当于求证$m|(a{a}_1-b{b}_1)$

1. 由 $m|(a-b)$，$m|(a_1-b_1)$，由整除的性质可得 $m|[(a-b)+(a_1-b_1)]$，即 $m|[a+(a_1)-(b+b_1)]$．
2. 由 $m|(a-b)$，$m|(a_1-b_1)$，可得 $m|[a_1(a-b)+b(a_1-b_1)]$，即 $m|(a{a}_1-b{b}_1)$．
3. 由$m|a-b$可得$m|k(a-b)$,所以$ka\equiv kb(\mathrm{mod}m)$;或者利用性质$a{a}_1\equiv b{b}_1(\mathrm{mod}m)$,其中$a_1=b_1=k$
4. 反复利用性质$a{a}_1\equiv b{b}_1(\mathrm{mod}m)$,其中$a_1=a,b_1=b$,即可得到$a^n=b^n(\mathrm{mod}m)$
5. 由$n|a(b-c)$,$(n,a)=1$,以及整除和公约数的性质可得$n|(b-c)$,所以$b\equiv c(\mathrm{mod}n)$

还可以得到不与相等类似的性质．

性质 2

若 $ac\equiv bc(\mathrm{mod}m)$，且 $(c,m)=d$，则 $a\equiv b\left(\mathrm{mod}\frac{m}{d}\right)$．

说明:定理指出了我们可以通过提出模$m$同余的两个操作数的公约数,并将模缩小为$\frac{m}{d}$,其中$d=(c,m)$

证明：由条件$ac\equiv bc(\mathrm{mod}m)$得 $m|c(a-b)$，知 $\frac{m}{d}|\frac{c}{d}(a-b)$．又由$(c,m)=d$和最大公约数的性质,得 $\left(\frac{m}{d},\frac{c}{d}\right)=1$，根据整除和公约数(互素)的性质,可得 $\frac{m}{d}|(a-b)$．所以$a\equiv b(\mathrm{mod}\frac{m}{d})$

例如，由 $17\times 6\equiv 25\times 6(\mathrm{mod}8)$及$(6,8)=2$，可知 $17\equiv 25(\mathrm{mod}4)$．

性质 3 不同模的同余式性质

如果 $a\equiv b(\mathrm{mod}{m}_i)$，其中 $1\le i\le n$，则$$a\equiv b(\mathrm{mod}[m_1,m_2,\dots ,m_n]).$$

说明:定理揭示了同一对数$a,b$同时关于不同模同余时,$a,b$将对这些模的最小公倍数同余;证明思路仍然是转换为模整除差式,方便我们利用最小公倍数的性质进行推导,最后将整除式和对模同余联系起来

证明：由于 $m_i\mid (a-b)$，其中 $1\le i\le n$，可见 $(a-b)$ 是 $m_1,m_2,\dots ,m_n$ 的公倍数，因此有 $[m_1,m_2,\dots ,m_n]\mid (a-b)$。

利用同余解决大数相关经典问题

整除问题可转换为同余问题,特别是判断一个能否整除另一个数的问题或者除以另一个数后余数时多少的问题以及类似或相关的问题

这类问题依赖于对同余和整除性质的了解,比如同余性质:若$a\equiv b(\mathrm{mod}m)$,则可令$c=(a\mathrm{mod}m)=(b\mathrm{mod}m)$,且有$a\equiv b\equiv c(\mathrm{mod}m)$

大数整除问题

求证$641 \mid F_5 $。其中$F_{5}=2^{32} + 1$表示$n=5$时的费马数

分析

$2^{32}$是一个很大的数,对于二进制了解的同学可以知道这是个过40亿的数,($2^{32}=2^2\cdot 2^{30}=4\cdot 1024^3>4\cdot 1000^3=4\cdot 10^9$),利用同余的性质来减少计算量,也就是找到一个比较小的数$x$,满足$2^{32}+1\equiv x(\mathrm{mod}641)$,通过判断$641|x$是否成立来判断$641|F_5$是否成立

我们先从$2^8$次方(或直接从$2^{16}$)开始试探;

事实上,我们可以先判断$2^{32}|641$,根据同余性质,$(2^{32}+1)|641$就是容易的事情

最后的效果是一个10位数除以$641$的整除问题转换为几次5位数能否整除$641$的整除或求余问题

在$a\equiv b(\mathrm{mod}m)$求取缩小$x$的过程是通过计算余数($x_i=\min (a,b)\mathrm{mod}m$),我们有$a\equiv b\equiv x_i(\mathrm{mod}m)$

如果$x_i$仍然很大,那么继续操作得到$x_2$和$a,b$都对模$m$同余

证明：

下面这个过程有一定的计算量,但是比起直接计算$(2^{32}+1)/641$的余数仍然要轻松的多

$2^8=256$,$2^{16}=65536$，$2^{16}\mathrm{mod}641=154$,因此$2^{16}\equiv 154(\mathrm{mod}641)$(1)

由同余的性质,式(1)变形为$2^{32}\equiv 154^2(\mathrm{mod}641)$;(2)

而$154^2=23716$,$154^2\mathrm{mod}641$=$640$,所以$2^{32}\equiv 154^2\equiv 640$

$2^{32}\equiv (154{)}^2=23716\equiv 640\equiv -1(\mathrm{mod}641)$。

所以$2^{32}+1\equiv 0(\mathrm{mod}641)$,这说明$2^{32}+1$除以$641$的余数和$0$除以641的余数相同都是0,从而$(2^{32}+1)|641$

这个结果否定了费马的一个猜想：$2^{2^n}+1$ 都是素数（其中 $n$ 为自然数）。

末尾数字问题

求 $23^{23}$ 的末位数字。

分析:根据进位计数法的定义可知,一个$r$进制数$S_r$的个位数可通过$S_r\mathrm{mod}r$来求得

那么一个十进制数整数的末位(个位)可以通过除以10求余数获得

解：
$$23^{23}\equiv 3^{23}\equiv (3^2{)}^{11}\cdot 3\equiv (9{)}^{11}\cdot 3\equiv (10-1{)}^{11}\cdot 3\equiv -1\cdot 3\equiv 7(\mathrm{mod}10)$$
由二项式定理展开式$(10-1{)}^{11}$=${\sum }_{i=0}^{11}\left(\genfrac{}{}{0ex}{}{11}{i}\right)10^i(-1{)}^{11-i}$

$(10-1{)}^{11}$=$(-1+10k)$,$k\in {\mathbb{Z}}_{+}$,其个位数为$10-1=9$所以$(10-1{)}^{11}\mathrm{mod}10=9$,所以$(10-1{)}^{11}\equiv 9(\mathrm{mod}10)$,根据同模性质,$(10-1{)}^{11}\cdot 3\equiv 27(\mathrm{mod}10)$,从而$(10-1{)}^{11}\cdot 3\equiv 27\equiv 7(\mathrm{mod}10)$

因此 $23^{23}$ 的末位数字是 7。

日期问题

例 1 今天为星期日，过 $2004^{2004}$ 天后的今天是星期几？

分析：$2004^{2004}$ 这个数很大，我们很难直接判断 $7$ 除 $2004^{2004}$ 的余数是多少。现在，我们想办法把 $2004^{2004}$ 变小。一个自然的考虑是 $7$ 除底数 $2004$ 的余数是多少，利用这个余数替换底数 $2004$，然后降次，反复进行这个过程，直至去掉指数。

解：因为 $2004=7\times 286+2$，所以 $2004\equiv 2(\mathrm{mod}7)$。

由同余的性质，有

$$2004^{2004}\equiv 2^{2004}(\mathrm{mod}7),$$

而 $2^{2004}=8^{668}$，所以 $2^{2004}\equiv 8^{668}(\mathrm{mod}7)$。

又因为 $8\equiv 1(\mathrm{mod}7)$，所以 $8^{668}\equiv 1^{668}=1(\mathrm{mod}7)$。

因此 $2004^{2004}\equiv 1(\mathrm{mod}7)$，即 $7$ 除 $2004^{2004}$ 的余数为 $1$，所以过 $2004^{2004}$ 天后的今天是星期一。

例 2 证：$17|19^{1000}-1$。

分析：类似例 1，我们想办法把 $19^{1000}$ 变小，用 $17$ 除底数 $19$ 的余数替换底数 $19$，然后降次，反复进行这个过程，直至去掉指数。

证明：要证 $17|19^{1000}-1$，只需证 $19^{1000}\equiv 1(\mathrm{mod}17)$，

因为 $19\equiv 2(\mathrm{mod}17)$，所以

$$19^{1000}\equiv 2^{1000}\equiv 16^{250}(\mathrm{mod}17).$$

又由于 $16\equiv -1(\mathrm{mod}17)$，故 $16^{250}\equiv (-1{)}^{250}=1(\mathrm{mod}17)$。

因此 $17|19^{1000}-1$。