整除

$a\vert b \equiv \text{“a divides b”} :\equiv (\exists c \in \mathbf{Z}: ac = b)$

定理一

$\forall a,b,c \in \mathbf{Z}$

1. $a\vert 0$
2. $(a\vert b \land \vert a\vert c) \rightarrow a\vert (b+c)$ 且 $a\vert (mb+nc), \forall m,n \in \mathbf{Z}$
3. $a\vert b \rightarrow a\vert bc$
4. $(a\vert b \land b\vert c) \rightarrow a\vert c$

   定理二

$\forall a,d \in \mathbf{Z}, d \neq 0: \exists q, r \in \mathbf{Z}: 0 \le r < \vert d\vert , a=dq+r$

$q$: 商数(quotient)，${\color{red} q = \lfloor a/d \rfloor} = a \ \text{div}\ d$

$r$: 余数(remainder)，${\color{red}r=a-qd}=a \mod d$

同余

本节中$a, b \in \mathbf{Z}, m \in \mathbf{Z}^+$

定理一

$a \equiv b\ (\mod m) \Leftrightarrow a(\mod m) \equiv b(\mod m) \Leftrightarrow \exists k \in \mathbf{Z},a=b+km$

定理二

若 $a \equiv b(\mod m)$且$c \equiv d(\mod m)$

则 $a+c \equiv b + d(\mod m)，ac\equiv bd(\mod m)$ (积同余且和同余)

定理三

$(a+b)\mod m=((a \mod m)+(b \mod m)) \mod m$

$(ab)\mod m=((a \mod m)(b \mod m)) \mod m$

模算术

$a +_{m} b=(a+b) \mod m$

$a \cdot_m b= (ab) \mod m$

模指数

快速幂

int qpow(int a, int b, int p) {
	int ans = 1;
	while (b) {
		if (b & 1) ans = ans * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return ans;
}

计算 $11^{644} \mod 645$： $(644)_{10}=(1010000100)_2$

	    x=1, 	a=11
n[0]=0,	x=1, 	a=121
n[1]=0,	x=1, 	a=451
n[2]=1,	x=451, 	a=226
n[3]=0,	x=451, 	a=121
n[4]=0,	x=451, 	a=451
n[5]=0,	x=451, 	a=226
n[6]=0,	x=451, 	a=121
n[7]=1,	x=391, 	a=451
n[8]=0,	x=391, 	a=226
n[9]=1,	x=1, 	a=121

$11^{644} \mod 645=1$

质数

质数有无穷个

令$q=p_1p_2p_3 \cdots p_n+1$，则$q$是一个质数。

梅森质数

如果$2^p-1$是质数，则被称为梅森素数。

质数分布

不超过$x$的素数的个数近似为$\dfrac{x}{\ln(x)}$。

最大公因数(GCD)

(Greatest Common Divisor, GCD)

$d=\gcd(a,b)=\max(d:d\vert a \land d\vert b) \Leftrightarrow d\vert a \land d\vert b \land \forall e \in \mathbf{Z}: (e\vert a \land e\vert b) \rightarrow d\ge e$

$\gcd(a,b)=\dfrac{ab}{\text{lcm}(a,b)}$

若

$a=p_1^{a_1}p_2^{a_2}p_3^{a_3}\cdots p_n^{a_n}, b=p_1^{b_1}p_2^{b_2}p_3^{b_3}\cdots p_n^{b_n}$

则

$\gcd(a,b)=p_1^{\min(a_1,b_1)}p_2^{\min(a_2,b_2)}p_3^{\min(a_3,b_3)}\cdots p_n^{\min(a_n,b_n)}$

互质

$a$和$b$互质当且仅当$\gcd(a,b)=1$

最小公倍数(LCM)

(Least Common Multiple, LCM)

$d=\text{lcm}(a,b)=\min(d:a\vert m \land b\vert m) \Leftrightarrow a\vert m \land b\vert m \land \forall n \in \mathbf{Z}: (a\vert n \land b\vert n) \rightarrow m\le n$

$\text{lcm}(a,b)=\dfrac{ab}{\gcd(a,b)}$

若

$a=p_1^{a_1}p_2^{a_2}p_3^{a_3}\cdots p_n^{a_n}, b=p_1^{b_1}p_2^{b_2}p_3^{b_3}\cdots p_n^{b_n}$

则

$\text{lcm}(a,b)=p_1^{\max(a_1,b_1)}p_2^{\max(a_2,b_2)}p_3^{\max(a_3,b_3)}\cdots p_n^{\max(a_n,b_n)}$

欧几里得算法

$\gcd(a,b)=\gcd((a \mod b), b)$

int gcd(int a, int b) {
	return b ? gcd(b, a % b) : a;
}

扩展欧几里得算法(exgcd)

eg. 35, 78

1. 首先用欧几里得算法求最大公因数 $78=2 \times 35+8$ $35=4\times8+3$ $8=2\times3+2$ $3=2\times3+2$ $2=2\times1+0$

2. 将余数写在前面 $1=3-1\times2$ $2=8-2\times3$ $3=35-4\times8$ $8=78-2\times35$

3. 去表达最后的最大公因数，使用第 2 步中的式子去代换，最终代换得到原数对最大公因数的表达式

其他相关定理

定理一

若 $\gcd(a, b)=1$ 且 $a \vert bc$，则 $a\vert c$ 。

定理二

若 $ac\equiv bc(\mod m)$ 且 $\gcd(c,m)=1$，则 $a \equiv b(\mod m)$

定理三

如果 $p$ 是质数并且 $p\vert a_1a_2 \cdots a_n$，则 $\exists i: p\vert a_i$

模逆元

$a a^{-1} \equiv 1(\mod m)$，$a^{-1}$ 称为模 $m$ 意义下 $a$ 的逆。

费马小定理

如果 $p$ 是质数并且 $a$ 不是 $p$ 的倍数，则 $a^{p-1} \equiv 1(\mod p)$。该定理可以用来求逆元，两边同时乘 $a^{-1}$。

$a^{p-2}\equiv a^{-1}(\mod p)$。即：$a$ 的逆元是 $a$ 的 $p-2$ 次方，其中 $p$ 是质数。

扩展欧几里得定理

当 $a$ 和 $m$ 互质，$\gcd(a, m) = 1$, 有 $sa+tm=1$ （贝祖系数法），因此 $sa \equiv 1(\mod m)$。此时 $s=a^{-1}$。

故先用 $a$ 和 $m$ 线性表示 1。

例1. 上文中 $35 \times 29 \equiv 1(\mod 78 \text{ 或} \mod 13)$。

例2. 求 144 在模 233 意义下的逆元。

使用扩展欧几里得用两个数字表示 1：

$1 = 89 \times 144 - 55 \times 233$

故 $144^{-1}\equiv89 (\mod 233)$

同余方程组

$x \equiv a_1 (\mod m_1)$ $x \equiv a_2 (\mod m_2)$ $\cdots$ $x \equiv a_n (\mod m_n)$

中国剩余定理(CRT)

令 $m=m_1m_2m_3\cdots m_n, M_k=\dfrac{m}{m_k}$，

令 $y_k$ 为 $M_k$ 在模 $m_k$ 意义下的逆元，即 $M_ky_k \equiv 1(\mod m_k)$。

$x=a_1M_1y_1+a_2M_2y_2 + \cdots + a_nM_ny_n$

伪素数(Pseudoprimes)

如果 $n$ 是合数并且 $b^{n-1} \equiv 1(\mod n)$，那么 $n$ 是基数 $b$ 的伪素数。

原根(Primitiva Roots)

$p$ 为素数，若 $\exists r \in N^{+}$，使得 $r, r^2, r^3, \cdots, r^{p-1}$ 模 $p$ 互不同余，则称 $r$ 是模 $p$ 的一个原根。

例如：

2 是 11 的原根，因为在模 11 的意义下 $2^1 \equiv 2, 2^2 \equiv 4, e^3 \equiv 8, 2^4 \equiv 5, 2^5 \equiv 10, 2^6 \equiv 9, 2^7 \equiv 7, 2^8 \equiv 3, 2^9 \equiv 6, 2^{10} \equiv 1$ 。

3 不是 11 的原根，因为在模 11 的意义下 $3^1 \equiv 3^6 \equiv 3$。

离散对数(Discrete Logarithms)

若 $p$ 是偶数，且 $r^e \equiv a (\mod p)$ ， $0 \le e \le p-1$，则称 $e$ 是在模 $p$ 意义下以 $r$ 为底 $a$ 的对数，$\log_ra=e$。