整数的除法与余数

为什么是这样

把数轴从 $0$ 起每 $b$ 格切一段，$a$ 落在第几段决定商 $q$，离那段左端几格就是余数 $r$，所以 $0\le r<b$。负数也一样：$-17$ 落在 $-20$ 到 $-15$ 那一段，$-17=5\times(-4)+3$，余数是 $3$，不是 $-2$。开头那题，$100=7\times14+2$，100 天后和 2 天后同为星期五。

按余数分类，每个整数恰好属于一类：除以 $3$ 时是 $3k$、$3k+1$、$3k+2$（$k$ 为整数）之一。$3k+2$ 也可以写成 $3k-1$，平方时更好算。图里每一列就是一类。

为什么余数能代替原数计算？设 $a=7k+3$，$b=7l+5$，则 $ab=49kl+35k+21l+15=7(7kl+5k+3l)+15$。展开后只有 $3\times5$ 这一项不带因数 $7$，所以 $ab$ 除以 $7$ 的余数等于 $15$ 除以 $7$ 的余数 $1$。和、差、乘方同理。

连续 $k$ 个整数在图里横着走过每一列各一次，所以其中恰有一个是 $k$ 的倍数。于是 $n(n+1)$ 是 $2$ 的倍数；$n(n+1)(n+2)$ 里既有 $2$ 的倍数又有 $3$ 的倍数，$2$ 与 $3$ 互素，所以是 $6$ 的倍数。一般地，连续 $k$ 个整数之积是 $k!$ 的倍数。

定量表达

设 $a$、$b$ 除以 $m$ 的余数是 $r$、$s$。$a+b$、$a-b$、$ab$ 除以 $m$ 的余数，分别等于 $r+s$、$r-s$、$rs$ 除以 $m$ 的余数，结果是负数时加上 $m$；$a^n$ 的余数等于 $r^n$ 的余数。「$a-b$ 是 $m$ 的倍数」在日本教材里常写成 $a\equiv b \pmod m$（合同式），打草稿很省事。

两个常用结果：$n^2$ 除以 $3$ 的余数只能是 $0$ 或 $1$，因为 $(3k\pm1)^2=3(3k^2\pm2k)+1$；除以 $4$ 也只能余 $0$ 或 $1$。乘方的余数会循环：$3^n$ 除以 $7$ 的余数依次是 $3,2,6,4,5,1$，到 $3^6$ 余 $1$ 后重复，周期是 $6$。求 $3^{100}$ 的余数，把指数 $100$ 除以周期 $6$，余 $4$，答案同 $3^4=81$，余 $4$。