模运算

计算机通常以从1970年1月1日（即“Unix era” 的开始）至今所经过的秒数来存储时间，并在所有和时间有关的计算中使用这些时间戳。

而人类则以历史的某一时刻为参照，记录时间，这个时刻通常具有政治或宗教意义。例如，写这段话的时候大约从公元1年（这是六世纪东罗马僧侣对耶稣基督出生日期的最佳估计）至今已经过了大约63882260594秒。

相比计算机要处理数位可能达到11位的整个时间戳，人类情境中需要的时间信息通常更为简单和局限。例如，人们可能只需要知道现在是下午2点，该去吃饭了；或者今天是周四，所以赛百味的每日特价三明治是意大利BMT。人们通常只从整个时间戳中提取出自己所需要的信息，而不需要了解全部内容。这种处理方式（只处理1-2位数字）比处理整个时间戳（11位数字）来得更简便。

问题是：今天是周四，一年后的今天是周几？

首先，我们将一周的每一天赋以一个数值，星期一是0，星期二是1，以此类推，直到星期日是6。在这个系统下，星期四是3。然后，我们添加365（也就是一年的天数）到这个数字上，然后再对7取余数。更方便的算法是，因为365除以7的余数是1，所以一年后的这一天是星期五（3+1=4，对应到我们的系统就是星期五）。然而，如果下一年是闰年，那么会多出一天（366天），所以我们需要在上述计算后再加一天，那么结果就变成了星期六。

余数

定义：如果两个整数 $a$ 和 $b$ 的差可以被 $m$ 整除，则称 $a$ 和 $b$ 模 $m$ 同余：

$m | (a-b) \Longleftrightarrow a \equiv b(\mod m)$

例如，一年中的第42天和第161天是一周中的同一天，因为 $(161 - 42) = 119 = 17 \times 7$ 。

模 $m$ 同余是一种等价关系，它将所有整数划分为等价类，称为余数类（residue class）。每一个模 $m$ 的余数类可以由其中任何一个成员表示——尽管我们通常使用该类中最小的非负整数（等于所有非负 $x \mod m$ 的余数）。

模数算术研究这些余数集，它们对数论至关重要。

**问题：**现在我们一周有 $m$ 天，一年有 $a$ 天（不考虑闰年）。那么一年、两年、三年等以后的那天是星期几？有多少种可能性？

为了简单起见，假设今天是星期一，所以初始日 $d_0$ 编号为0，然后没过一年，更新如下：

$d_{k+1} = (d_k+a) \mod m$

过了 $k$ 年后，将变为：

$d_k = k \cdot a \mod m$

由于我们一周有 $m$ 天，在某个时刻，日期将回到星期一，日期的顺序将开始循环。不同的星期几的数量就是循环的长度，所以我们需要找到使得下式满足的最小的 $k$ ：

$k \cdot a \equiv 0 (\mod m)$

首先，如果 $a \equiv 0$ ，则永远都是星期一。现在我们假设是 $a \not ≡ 0$ 这种有意义的情况：

一周7天， $m = 7$ 是质数。我们无法找到一个小于 $m$ 的数 $k$ 使得 $k \cdot a$ 能被 $m$ 整除。这是因为质数的定义是只能被1和它本身整除的数，不能被分解成两个非零自然数的乘积。因此，如果 $m$ 是一个质数，我们将会遍历所有的 $m$ 个星期几。
如果 $m$ 不为质数，但是 $a$ 与它互质（即 $a$ 与 $m$ 没有公约数），那么答案仍然是 $m$ ，原因类似： $a$ 的除数对帮助乘积对 $m$ 整除没有任何帮助。
如果 $a$ 和 $m$ 有共同的除数（公约数），那么我们对 $k \cdot a$ 进行模 $m$ 计算时，只能得到公约数的倍数。举个例子，如果一周有 $m=10$ 天，一年有 $a = 42$ 天或者其他偶数天数，则结果将在10以内偶数中循环。如果一年的天数是5的倍数，则结果只会在0和5之间来回切换。

因此，总的来说，答案是 $\frac{m}{gcd(a,m)}$ ，其中 $gcd(a,m)$ 是 $a$ 和 $m$ 的最大公约数。

费马定理

现在，我们考虑如果我们用累乘 $a$ 代替累加 $a$ ，得到这样一串数字

$d_n = a^n \mod m$

同样的，由于余数的数量是有限的，所以仍会存在一个循环。但循环的长度是多少呢？事实证明，如果 $m$ 是质数，它将包括所有 $(m−1)$ 个非零余数。

定理：对任意数 $a$ 和一个质数 $p$ ，有：

$a^p \equiv a (\mod p)$

证明：略

需要注意的是，这只对质数 $p$ 成立。我们可以利用这点，来检查给定的数字是否为质数，这比用对数字进行分解的方式速度更快：我们可以随机挑选一个数字 $a$ （一般小于 $p$ ），计算 $a^p \mod p$ ，检查是否等于 $a$ 。

这被称为费马素数性检验（Fermat primality test），它是一种概率性检验——只返回“否”或者“可能是”，因为尽管 $p$ 为合数，也可能出现 $a^p \mod p$ 等于a。在这种情况下，你需要用不同的随机 $a$ 来重复测试，直到你对错误正例的概率（false positive probability）感到满意。

质数性检验通常用于生成大质数（大质数在密码学中有重要应用）。前 $n$ 个数中有大约 $\frac{n}{\ln n}$ 个质数，而这些质数的分布比较均匀。我们可以随机选择一个需要的范围内的数，进行素性检查，如果不是质数就重复操作，直到找到一个质数。这个操作需要进行的次数平均约是 $O(\ln n)$ 次。

对费马素性检验来说，一个极其糟糕的输入是卡迈克尔数（Carmichael numbers）。卡迈克尔数是一个合数 $n$ ，但它对所有与其互质的 $a$ 都有 $a^{n-1} ≡ 1(\mod n)$ 。然而，卡迈克尔数非常罕见，我们在随机选择数字进行素性检验时，碰到卡迈克尔数的概率非常低。

模数除法

在实现常见的算术运算（如加法、减法、乘法等）时，使用余数（取模）是直接且有效的。只需要注意防止整数溢出，并记住在每次运算后都要取模：

c = (a + b) % m;
c = (a - b + m) % m;
c = a * b % m;

对于加法，减法和乘法，我们可以先进行运算然后对结果取模，或者先对每个操作数取模然后进行运算，这两种做法的结果是一样的。但是对于除法来说，这两种做法的结果可能是不同的。例如， $\frac{8}{2} = 4$ ，但是

$\frac{8 \mod 5}{2 \mod 5} = \frac{3}{2} ≠ 4$

在模运算中，我们不能直接进行除法，而是需要找到一个元素，当我们乘以它时，效果等同于除以另一个数字。这个元素称为模乘法逆元（modular multiplicative inverse）。假设我们要在模 $p$ 运算中除以 $a$ ，我们需要找到一个数 $b$ ，使得 $(a * b) \mod p = 1$ 。也就是说， $b$ 就是 $a$ 在模 $p$ 下的乘法逆元，因为 $a$ 乘以 $b$ 后模 $p$ 的结果等于1，所以 $b$ 就像是 $\frac{1}{a}$ 。

当模 $p$ 是一个质数时，我们可以使用费马定理来找到这个模乘法逆元。我们将等式两端除以 $a$ 两次可以得到：

$a^p \equiv a \Longrightarrow a^{p-1} \equiv 1 \Longrightarrow a^{p-2} \equiv a^{-1}$

这就意味着，我们只需要计算 $a^{p-2} \mod p$ ，就可以得到我们需要的模乘法逆元。所以，当我们需要在模 $p$ 下除以 $a$ 时，我们实际上是将其乘以 $a$ 的模 $p$ 逆元，也就是计算 $(b * a^{p-2}) \mod p$ 。这样，我们可以在模 $p$ 下进行除法操作。