余数——周期性和分组

余数，作除法运算时剩下的数。尽管从小学起我们就反复练习加、减、乘、除的计算，但有关余数的计算只在学习除法时略见其影，事实上，无论在数学还是编程中，余数都起着非常重要的作用。因为我们将意识到，“余数就是分组”，而且它的神奇性在于，将较大的数字除一次就能分组。

1. 星期数问题

以这样一个常见的问题为例：

今天是星期日，那么 1 亿天以后是星期几？

对于这个问题，我们显然知道，一周有 7 天，那么“7”是星期数的周期，从今天起每过 7 天，便循环到和今天相同的星期数。如果今天是星期日，则 7 天后、14 天后、21 天后......这种“7 的整数倍”天后都是星期日。由此我们便可引入除法运算，看 1 亿天里有几个 7 天，也就是周期的重复出现了多少次，以便将这个重复性影响剔除，方便我们解决问题。

显然，有

$$10^8 \div 7 =14285714 \cdots 2$$

这表示，1 亿（$10^8$）里面有 14285714 个星期数周期，将它们忽略，日子便相当于只前进了 2 天，因此从今天的星期日开始往后数 2 天，便是星期二，故而 1 亿天以后必然是星期 2。

2. 更进一步——隐藏的周期性分组

在星期数的问题上，如果数字更大呢？比如：

今天是星期日，那么$10^{100}$天以后是星期几？

我们固然可以套用之前的方法解决这个类似的问题，但是说实在的$10^{100}$这个数太大了，计算机计算起来都相当费力，我们需要更进一步的思考。

我们并不急于求出$10^{100}$，而可以像$1,10,100,1000,10000\cdots$这样，依次增加 0 的个数，观察其规律：

数字	0 的个数	除法计算	星期数
$1$	0	$1 \div 7 = 0 \cdots 1$	1
$10$	1	$10 \div 7 = 1 \cdots 3$	3
$10^2$	2	$10^2 \div 7 = 14 \cdots 2$	2
$10^3$	3	$10^3 \div 7 = 142 \cdots 6$	6
$10^4$	4	$10^4 \mod 7 = 4$	4
$10^5$	5	$10^5 \mod 7 = 5$	5
$10^6$	6	$10^6 \mod 7 = 1$	1
$10^7$	7	$10^7 \mod 7 = 3$	3
$10^8$	8	$10^8 \mod 7 = 2$	2
$10^9$	9	$10^9 \mod 7 = 6$	6
$10^{10}$	10	$10^{10} \mod 7 = 4$	4
$10^{11}$	11	$10^{11} \mod 7 = 5$	5
$10^{12}$	12	$10^{12} \mod 7 = 1$	1
$10^{13}$	13	$10^{13} \mod 7 = 3$	3

我们发现，余数以$1,3,2,6,4,5\cdots$的顺序循环，即星期数在这个层面上也处于循环之中，循环周期为 6，故而$10^{100}$与$10^{94},10^{88},10^{82}\cdots$的星期数相同，我们将指数位置处的 100 对 6 作除法：

$$100 \div 6 = 16 \cdots 4$$

因此$10^{100}$与$10^{4}$的星期数相同，而在上表中我们已经通过$10^4 \mod 7 = 4$知道了$10^{4}$为星期 4，因此我们已经找到了答案。

3. 乘方尾数的周期性（异曲同工）

上面我们用星期数的案例为例描述了余数的作用，其实还有一个典型的问题与之类似：

$1234567^{987654321}$的个位数是什么？

$1234567^{987654321}$的数值显然同样大到难以计算，我们可以采用同样的做法解决这个问题，此外，由于我们只关注个位数字，因此可将高位数字忽略掉。具体计算方法这里不再赘述，答案为 7。