余数与同余

考什么 · What it tests

需要先会 · Prerequisites

• 带余除法（被除数 = 除数 × 商 + 余数） / Division with remainder (dividend = divisor × quotient + remainder)
• 整除与因数 / Divisibility and factors
• 数列的周期性 / Periodicity of sequences

常见套路 · Common moves

1. 先取余再运算：算大数的和/积除以 $m$ 的余数，先把每个数换成余数再算，数立刻变小——同余题的通用第一招。

   Reduce first, then compute: to find a big sum or product's remainder mod $m$, replace each number by its remainder before computing — the numbers shrink at once, the universal first move.
2. 求个位数 = 模 10 找周期：如 $3^n$ 的个位按 $3,9,7,1$ 循环，周期 4，看指数除以 4 的余数定位。

   A units digit is a period mod 10: e.g. $3^n$ cycles $3,9,7,1$ with period 4, so the exponent's remainder mod 4 pins it down.
3. 「除以几余几」凑同一个数：多个「除 $a$ 余 $b$」的条件，若余数补齐后一致（如都差 1），加上那个差就整除，问题立刻简化。

   Align mismatched remainders: with several "divide by $a$, remainder $b$" conditions, if they line up after a shift (all short by 1), adding that shift makes everything divisible and the problem collapses.

易错点 · Common pitfalls

• 余数取成负数或超过除数：余数必须在 0 到「除数减 1」之间，$-1$ 除以 5 的余数是 4 不是 $-1$。

  Taking a remainder negative or too big: it must lie between 0 and one less than the divisor, so $-1$ mod 5 is 4, not $-1$.
• 模幂时直接把指数对 $m$ 取余：应是底数按周期循环，不是把指数对 $m$ 取余——先找个位周期再定位。

  Reducing the exponent mod $m$ for a power: it's the base that cycles by a period, not the exponent mod $m$ — find the cycle first, then locate.