数学课堂
挑战≈ 16 分钟未开始

同余初步

核心概念

同余:设 mm 是正整数。若 m∣(a−b)m \mid (a - b),就说 aa 与 bb 模 mm 同余,记作

a≡b(modm).a \equiv b \pmod{m}.

等价地说,aa 和 bb 除以 mm 的余数相同。

同余的运算性质:若 a≡b(modm)a \equiv b \pmod m 且 c≡d(modm)c \equiv d \pmod m,则

  • a+c≡b+d(modm)a + c \equiv b + d \pmod m;
  • a−c≡b−d(modm)a - c \equiv b - d \pmod m;
  • ac≡bd(modm)ac \equiv bd \pmod m;
  • an≡bn(modm)a^n \equiv b^n \pmod m(对正整数 nn)。

注意:除法不能随便约掉。只有当约去的数与模 mm 互质时,才允许两边同除。

直观理解 · 动手试试

同余把"无穷多的整数"压缩成"几个余数类"。模 mm 之下,世界里只剩 0,1,…,m−10,1,\dots,m-1 这 mm 个"代表"。求 71007^{100} 的个位、判断某个巨大的数能否被 99 整除——都不必真算出那个庞然大物,只要在余数世界里做加减乘方,既快又准。

关键直觉:同余像等号一样可以加、减、乘、乘方,唯独除法要小心。这让"取余"成为可以放心运算的对象,而不是算到最后才做的一步。

同余 · 幂的循环

2n mod 5 的循环节

n=1
2
n=2
4
n=3
3
n=4
1
n=5
2
n=6
4
n=7
3
n=8
1
n=9
2
n=10
4
n=11
3
n=12
1
余数序列以 周期 4 循环。 要算 2n mod 5，只需看 n 落在循环里的第几位。
2
5

幂在模 m 下必然循环。绿色是一个完整周期；找到周期，再大的指数也能秒算余数。

例题 1求大幂的余数

求 71007^{100} 除以 55 的余数。

▸查看解答步骤

答: 余 1

例题 2被 9 整除的判别法

说明:一个整数能被 99 整除,当且仅当它的各位数字之和能被 99 整除。

▸查看解答步骤

答: 各位数字和被 9 整除则原数被 9 整除

即时练习

320243^{2024} 除以 44 的余数是多少?

3≡−1(mod4)3 \equiv -1 \pmod 4,故 32024≡(−1)2024=1(mod4)3^{2024} \equiv (-1)^{2024} = 1 \pmod 4。

2302^{30} 的个位数字是多少?

22 的个位以 2,4,8,62,4,8,6 为周期( mod  4\bmod\,4):指数 ≡1→2, ≡2→4, ≡3→8, ≡0→6\equiv 1\to2,\ \equiv2\to4,\ \equiv3\to8,\ \equiv0\to6。30≡2(mod4)30\equiv 2\pmod4,故个位是 44。

下列哪一条不一定成立(模 mm)?

由 ac≡bcac \equiv bc 一定能推出 a≡ba \equiv b由 a≡ba\equiv b 推出 a2≡b2a^2 \equiv b^2由 a≡b, c≡da\equiv b,\ c\equiv d 推出 a+c≡b+da+c\equiv b+d由 a≡ba\equiv b 推出 a+c≡b+ca+c\equiv b+c

同余的消去律要求被约去的数与模互质,否则 ac≡bcac\equiv bc 不能推出 a≡ba\equiv b。

    123456789123456789 能被 99 整除。

    数字和 1+2+⋯+9=451+2+\cdots+9 = 45,9∣459 \mid 45,所以原数被 99 整除。

    9509^{50} 除以 1010 的余数是多少?

    9≡−1(mod10)9\equiv-1\pmod{10},950≡(−1)50=19^{50}\equiv(-1)^{50}=1。

    3183^{18} 除以 55 的余数是多少?

    33 的幂模 55 以 3,4,2,13,4,2,1 为周期(44)。18≡2(mod4)18\equiv2\pmod4,对应 32=9≡4(mod5)3^2=9\equiv4\pmod5。

    易错点

    • 在同余式里随意约分。 6≡0(mod6)6\equiv 0\pmod 6 但不能两边除 22 得 3≡03\equiv0。只有与模互质才能约。
    • 乘方循环的周期数错。 个位循环常从指数 11 开始,定位时要数清"第几个"。
    • 混淆同余与相等。 a≡b(modm)a\equiv b\pmod m 不代表 a=ba=b,只代表二者差是 mm 的倍数。

    下一步

    接下来学习