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}$

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

A Friendly Introduction to Number Theory Chapter 8~9

同余(Congruences)，快速幂取模和费马小定理(Fermat's little theorem)

Content

Congruence

Properties

Successive squaring

Linear congruence

Code snippets

Modular multiplicative inverse

Polynomial roots mod $p$ theorem

Reduced residue system

Lemma

Fermat’s little theorem

Wilson’s theorem

Carmichael numbers

Exercises

8.4

(c) & (d)

(e)

9.3

(a) && (b)

FEATURED TAGS

FRIENDS

Content

Congruence

Properties

Successive squaring

Linear congruence

Code snippets

Modular multiplicative inverse

Polynomial roots mod pp theorem

Reduced residue system

Lemma

Fermat’s little theorem

Wilson’s theorem

Carmichael numbers

Exercises

8.4

(c) & (d)

(e)

9.3

(a) && (b)

FEATURED TAGS

FRIENDS

Polynomial roots mod $p$ theorem