一道+ / edao.plus

同余

两个数除以 m 余数相同，记作 a ≡ b (mod m)。余数守加、守减、守乘——整除问题的万能语言。

直观场景

“钟表上的 14 点和 2 点指针指向同一位置”，这就是 14 ≡ 2 (mod 12)。同余让我们忽略具体数值，只关心“余数”这一特征。

推导思路

  1. 定义：a ≡ b (mod m) ⇔ m | (a − b)。
  2. 运算性质：若 a ≡ b, c ≡ d (mod m)，则 a + c ≡ b + d，a − c ≡ b − d，a · c ≡ b · d (mod m)。
  3. 幂：a^k ≡ b^k (mod m)。
  4. 常用技巧：把大数对 m 取余后再运算，保持结果正确。

公式 / 要点

  • 同加减乘：余数守恒（但除法不一定）。
  • 求余 = 先对每一部分求余，再合并。

典型例题

1大数求余
求 7^100 除以 5 的余数。
  1. 7 ≡ 2 (mod 5)，所以 7^100 ≡ 2^100 (mod 5)。
  2. 2^4 = 16 ≡ 1 (mod 5)，所以 2^100 = (2^4)^25 ≡ 1 (mod 5)。
  3. 余数 = 1。
2星期几
今天是星期三，100 天后是星期几？
  1. 100 ≡ 2 (mod 7)。
  2. 星期三 + 2 天 = 星期五。

常见误区

  • 除法不满足同余，不能直接“两边除”。
  • 取余时保持 0 ≤ 余数 < m。

用到“同余”的题目

#10025 韩信点兵·余同问题
数论六年级
#10044 同余问题·韩信点兵
数论五年级
#10178 同余问题·物不知数
数论六年级
#10184 同余问题·中国剩余定理
数论六年级

相关知识点

位值原理