Content

Congruence

两个整数之间的模 $m$ 同余关系通过整除来定义：

$m\mid{a-b}\iff a\equiv b\pmod m$

即如果 $m$ 整除 $a$ 和 $b$，称 $a$ 和 $b$ 模 $m$ 同余。

Properties

整数之间的同余关系”$\equiv$”和实数上的相等关系”$=$”存在众多相似之处。除了作为一个等价关系所具备的自反性(reflexive)、对称性(symmetric)和传递性(transitive)之外，假如已知

$a\equiv b\pmod m\text{ and }c\equiv d\pmod m$

容易证明

$a\pm c\equiv b\pm d\pmod m\tag{1}$ $ac\equiv bd\pmod m\tag{2}$ $a^n\equiv b^n\pmod m\tag{3}$

Successive squaring

虽然没有找到这个名词的中文翻译，但我猜测这就是中文里的“快速幂取模”，有的文章把这个称作重复乘方法(repeated squaring)。重复乘方法是一种便于快速计算高次幂取模的算法，即计算以下模 $m$ 同余

$a^n\pmod m$

考虑整数 $n$ 的二进制形式 $n={b_0b_1b_2\ldots b_k}_{(2)}$，$b_i=0\text{ or }1$

$n=b_0+b_1\cdot 2+b_2\cdot 2^2+\ldots+b_k\cdot2^k$ $\begin{aligned} a^n&=a^{b_0+b_1\cdot 2+b_2\cdot 2^2+\ldots+b_k\cdot2^k}\\ &=a^{b_0}\cdot a^{b_1\cdot 2}\cdot a^{b_2\cdot 2^2}\cdot\ldots\cdot a^{b_k\cdot2^k} \end{aligned}$

二进制表示整数的好处在这里体现出来了：一方面 $2^i$ 次幂可以从上一次的结果计算得到，因为 $(a^{2^{i-1}})^2=a^{2\cdot2^{i-1}}=a^{2^i}$。另一方面整数二进制表示的数位只有 $0$ 和 $1$，和其它进制相比做乘法的次数更少。比起简单地做 $n$ 次乘法，这种方法将时间复杂度降低到 $O(\log{n})$。

Linear congruence

对于线性同余方程

$ax=c\pmod m$ 因为

$m\mid{(ax-c)}\implies my=ax-c$ 我们可以将它转化为 $ax+my=c$ 的形式然后应用扩展欧几里德算法和线性方程解法来解决。关于 $ax\equiv c\pmod m$ 的解的个数，设 $x_0, x_1$ 是 $ax\equiv c\pmod m$ 的两个解，令 $g=\gcd{(a,m)}$ ，

$ax_0\equiv ax_1\pmod m\implies \dfrac{m}{g}\mid\dfrac{a}{g}(x_1-x_0)$

因为 $\gcd{(\dfrac{m}{g},\dfrac{a}{g})}=1$，由欧几里德引理得到$\dfrac{m}{g}\mid{x_1-x_0}$，应用解线性方程的方法

$\begin{array}{} x_i=x_0+k\cdot\dfrac{m}{g} &k\in\mathbb{Z}^* \text{ and } 0\le k\lt g \end{array}$

因为 $x_i \lt x_0+k\frac{m}{g}$，这意味着 $ax\equiv c\pmod m$ 有 $g=\gcd{(a,m)}$ 个 模 $m$ 两两不同余 的解。

Code snippets

def linear_congruence(a,c,m):
    g, x, y = gcd(a,m)
    m = abs(m)
    if c % g == 0:
        x *= c // g
        return [(x + k * (m // g)) % m for k in range(g)]

Modular multiplicative inverse

已知整数 $a,m$，满足 $ax\equiv1\pmod m$ 的整数 $x$ 称为 $a$ 的模 $m$ 乘法逆元(modular multiplicative inverse)，写作 $x\equiv a^{-1}\pmod m$。应用前面解线性同余方程的方法可以立即得到以下结论：

假如 $\gcd{(a,m)}=1$，而且 $a$ 的模 $m$ 乘法逆元只有一个，即由 $a$ 和 $a^{-1}\pmod p$ 各自组成的集合之间存在一一对应关系
换言之若 $\gcd{(a,m)}\gt1$，那么 $a$ 的模 $m$ 乘法逆元不存在，即不存在整数 $x$ 满足 $ax\equiv1\pmod p$；

在同余的语境下，模 $m$ 乘法逆元运算可以类比实数上的倒数运算，它们都有着类似的性质：元素 $a$ 和它的逆元作乘法运算的结果是 $1$ 以及对应逆元只有 $1$ 个。

以分数形式出现的模算数也是有意义，比如

$x\equiv\frac{2}{3}\pmod 5\implies3x\equiv2\pmod 5\implies x\equiv4\pmod 5$

又如 $x\equiv\frac{1}{a}\equiv a^{-1}\pmod m$，它的意义是 $a$ 的模 $m$ 乘法逆元而不是倒数；而且 $(a^{-1})^n\equiv(a^n)^{-1}\pmod m$，这是因为

$ax\equiv 1\pmod m\implies \begin{cases} x\equiv a^{-1}\pmod m\implies x^n\equiv(a^{-1})^n\pmod m\\ a^nx^n\equiv 1\pmod m\implies x^n\equiv(a^n)^{-1}\pmod m\\ \end{cases}\implies(a^{-1})^n\equiv(a^n)^{-1}\pmod m$

Polynomial roots mod $p$ theorem

给定素数 $p$，整数 $d\ge1$ 和系数为整数的多项式

$f(x)=a_0x^d+a_1x^{d-1}+\ldots+a_d$

其中 $p\nmid a_0$。然后同余式

$f(x)\equiv0\pmod p$

最多只有 $d$ 个模 $p$ 互不同余的解。

wikipedia 的拉格朗日定理条目上边有更准确的表达，书中的表述可以视为拉格朗日定理在 $p\nmid a_0$ 下的特例：

if $p$ is a prime number and $f(x)\in\mathbb{Z}[x]$ is a polynomial with integer coefficients, then either:

every coefficient of $f(x)$ is divided by $p$, or

$f(x)\equiv_p 0$ has at most deg $f(x)$ incongruent solutions.

Reduced residue system

已知集合 $A$ 有 $n$ 个元素而且两两模 $n$ 不同余，称 $A$ 为模 $n$ 完全剩余系(complete residue system modulo $n$)；而集合 $B={r\mid r\in A\text{ and }\gcd{(r,n)}=1}$ 称为模 $n$ 简化剩余系(缩系，reduced residue system modulo $n$)。

Lemma

给定素数 $p$ 和任意整数 $a$ 而且 $p\nmid a$，那么由 $a,2a,3a,\ldots,(p-1)a \pmod p$

构成的集合和 $1,2,3,\ldots,(p-1) \pmod p$

所构成的集合相等。

假设存在整数 $i$ 和 $j$，$1\lt i\lt j\lt p$，满足 $ia\equiv ja\pmod p$，那么 $p\mid(i-j)a$。因为 $p$ 是素数而且 $p\nmid a$，由欧几里德引理可以知道 $p\mid (i-j)$。又因为 $i,j\in{1,2,\ldots,p-1}$，因此 $i=j$，这表明 $a,2a,3a,\ldots,(p-1)a$ 当中任意两个数模 $p$ 不同余。

这表示给定模 $p$ 缩系 $B$，对于满足 $p\nmid a$ 的整数 $a$，$C={ ab \mid b\in B}$ 也是一个模 $p$ 缩系。更一般地，这个性质体现在所有自然数 $n$ 上，详见下一章[欧拉定理](/2018/10/04/AFINT-Chap-10~11/。

Fermat’s little theorem

假如 $p$ 是素数，那么对于任意整数 $a$ 而且 $p\nmid a$，都有

$a^{p-1}\equiv1\pmod p$

由已知集合

$\{a,2a,3a,\ldots,(p-1)a\}$

构成一个模 $p$ 缩系，所以

$a\cdot2a\cdot3a\cdot\ldots\cdot(p-1)a\equiv 1\cdot2\cdot3\cdot\ldots\cdot(p-1) \pmod p$

由于 $\gcd{((p-1)!,p)}=1$，两边同时去掉 $(p-1)!$ 得到

$a^{p-1}\equiv 1\pmod p$

值得注意的是，应用费马小定理可以 判别一个数是合数 ，但不能判别这个数是素数。这听上去有点矛盾：除了$1$之外，其他自然数要么是素数要么是合数，假如一个数不是合数，那么难道不是素数吗？

要回答这个问题就要仔细地重温一下离散数学的命题逻辑内容：原命题的真假性和逆命题(converse)的真假性没有必然关系，但是原命题和逆否命题(contrapositive)具有同样的真假性，由蕴涵等值式(material implication)

$A\to B \iff \lnot A \lor B \iff \lnot(\lnot B)\lor \lnot A\iff\lnot B\to \lnot A$

费马小定理的逆否命题：对于整数$m$，假如 $\exists\text{ }a\in N\text{ s.t.}$

$a^{m-1}\not\equiv 1\pmod m$

那么 $m$ 是合数。

Wilson’s theorem

威尔逊定理(Wilson’s theorem):

证明假如 $p$ 是素数，那么 $(p-1)!\equiv-1\pmod p$。

由线性同余方程的解可以知道当 $p$ 是素数而且 $p\nmid a$ 时，$ax\equiv 1\pmod p$ 模 $p$ 互不同余 的解只有一个。

除此之外，

$x^2\equiv1\pmod p \iff (x-1)(x+1)\equiv0\pmod p$ $\begin{array}{} x\equiv 1\pmod p & \text{or}&x\equiv p-1\pmod p \end{array}$

换言之，当 $a=1\text{ or }p-1$，满足 $ax\equiv 1\pmod p$ 的只有 $x\equiv a\pmod m$；在集合 $A’={2,\ldots,p-2}$ 中的元素 $a’$，有且只有一个数 $x\in A’ \text{ and }x\not= a’$满足 $a’x\equiv 1\pmod p$。

假如素数 $p\gt2$，$p-1$ 是偶数，对每一个数 $a$ 都能找到唯一一个数 $x$ 满足 $ax\equiv 1\pmod p$。所以

$(p-1)!\equiv1\cdot 2x_1\cdot 3x_2\cdot\ldots\cdot(p-2)x_{p-3}\cdot(p-1)\equiv p-1\equiv-1\pmod p$

所以当 $p$ 为素数，

$(p-1)!\equiv-1\pmod p$

Carmichael numbers

满足 $a^{m-1}\equiv 1\pmod m,\gcd{(a,m)}=1$ 的合数 $m$ 被称作卡迈克尔数(Carmichael numbers)。最小的卡迈克尔数是 $561=3\times11\times17$。

Exercises

8.4

(c) & (d)

整数 $a$ 能被 $3$ 整除当且仅当其数字的和能够被 $3$ 整除。

因为 $10\equiv1\pmod3\implies10^n\equiv1\pmod3$

$a_n10^n+a_{n-1}10^{n-1}+\ldots+a_0\equiv a_n+a_{n-1}+\ldots+a_0\pmod 3$

(e)

整数 $a$ 能被 $11$ 整除当且仅当其数字的交错和(Alternating Sum)能够被 $3$ 整除。

因为

$\begin{array}{} 10\equiv{-1}\pmod{11} & 10^2\equiv1\pmod {11} \end{array}$

所以

$\sum_{i=0}^{n}a_{2i+1}10^{2i+1}\equiv10\sum_{i=0}^{n}a_{2i+1}\equiv-\sum_{i=0}^{n}a_{2i+1}\pmod {11}$ $\sum_{i=0}^{n}a_{2i}10^{2i}\equiv\sum_{i=0}^{n}a_{2i}\pmod {11}$ $\sum_{i=0}^{n}a_i10^i\equiv\sum_{i=0}^{n}a_{2i}-\sum_{i=0}^{n}a_{2i+1}\pmod {11}$

9.3

(a) && (b)

证明假如 $m$ 是合数，那么 $(m-1)!\equiv0\pmod m$。

由算术基本定理可知，

当 $m=p^k$，由于 $k$ 可以写成$2$的幂的和，$k=k_1+k_2+\ldots+k_n\text{, }k_a=2^i\text{, }k_a\not=k_b$。因此

$m=p^k=p^{k_1+k_2+\ldots+k_n}=p^{k_1}p^{k_2}\ldots p^{k_n}$ $\begin{array}{} 1\lt p^{k_1}\lt p^{k_2}\lt\ldots\lt p^{k_n} \lt m\text{ ,}& p^{k_a}\in\{1,2,\ldots m-1\} \end{array}$ $(m-1)!=C\cdot p^{k_1}p^{k_2}\ldots p^{k_n}=Mm$

所以 $m\mid(m-1)!$，即 $(m-1)!\equiv0\pmod m$。

当 $m=p_1^{k_1}p_2^{k_2}\ldots p_n^{k_n}$，一定有 $\begin{array}{} 1\lt p_1^{k_1}\lt p_2^{k_2}\lt\ldots\lt p_n^{k_n} \lt m &\text{,}& p_n^{k_n}\in\{1,2,\ldots m-1\} \end{array}$