数论 | XY's blog

整数

第一/第二数学归纳法
良序公理: 每个自然数集的子集都是良定义的, 即有最小元素
数学归纳法可推出良序公理
对于整数a和b, b > 0, 存在唯一的整数q和r, 满足$a=bq+r$, 其中$0\le e<b$.
对于非0整数a和b, 存在整数r和s, 满足 $\gcd(a, b) = ar+bs$ 进一步, $gcd(a, b)$是唯一的.
欧几里得算法: 求最大公因数gcd. (辗转相除)
素数有无限个.
算数基本定理: n是大于1的整数, 存在n的唯一素数分解 $n = p_1^{e_1}p_2^{e_2}...p_r^{e_r}$ 其中$p_i$是素数, $p_1 < p_2 < … < p_r$, 且$e_i$为正整数.

逆元和最大公约数

乘法逆元: $a’\cdot_n a = 1$, 则$a’$是$a$的乘法逆元.
如果$a$在$Z_n$中有乘法逆元$a’$, 那么对于任意$b\in Z_n$, 方程$a\cdot_n x = b$有唯一解$x=a’ \cdot _n b $.
对于$a$, $b\in Z_n$, 如果方程$a\cdot_n x = b$无解, 那么$a$没有乘法逆元.
逆元唯一.
方程$a\cdot_n x = 1$有解(即有$a$在$Z_n$中逆元)当且仅当存在整数$x$和$y$满足$ax+ny=1$, 而$a$的逆元就是$x \mod n$.
如果存在整数$x$和$y$满足$ax+ny=1$, 那么a和n互素.
如果$j, k, q, r$是满足$k=jq+r$的正整数, 那么$\gcd(j, k) = \gcd(r, j)$.
Euclid’s extended GCD algorithm: 返回$gcd(j, k)$和整数$x$和$y$满足$\gcd(j, k) = jx+ky$.
正整数$j$和$k$互素当且仅当存在整数$x$和$y$满足$jx+ky=1$.
对于正整数$n$, $Z_n$中元素$a$有乘法逆元当且仅当$\gcd(a, n) = 1$.
对于素数p, $Z_p$中每个非0元素$a$都有逆元.
求逆元: 用Euclid’s extended GCD algorithm求得$\gcd(a, n), x, y$. 如果$\gcd(a, n)==1$, 逆元是 $x\mod n$. 否则没有逆元.
Euclid / Extended Euclid 算法递归调用次数: $O(\lg b)$ (a > b > 0).
对于任意非0整数a, g, gcd(a, b)是a和b的线性组合集$\{ax+by: x, y \in Z\}$中的最小元素.
对于所有整数a, b以及非负整数n, 有 $\gcd(an, bn) = n\gcd(a, b)$
对于正整数n, a, b, 如果$n | ab$且$\gcd(a, n) = 1$, 则$n|b$.

模运算

$Z_n ^ $的规模表示为$ \phi(n)$ , 称为*欧拉phi函数
欧拉函数下界: $\phi(n) > \frac{n}{e^\gamma\ln\ln n + \frac{3}{\ln \ln n}}$ 其中$n \ge 3$, $\gamma = 0.5772156649…$ 为欧拉常数.
一个有限群的非空封闭子集是一个子群
拉格朗日定理: 如果$(S, \oplus)$ 是一个有限群, $(S, \oplus)$ 是$(S, \oplus)$ 的一个子群, 则$|S’| $ 是$|S|$ 的一个约数.
对于任意有限群$(S, \oplus)$ 和任意$a \in S$ , $ord(a) = |\langle a\rangle|$.

求解线性方程

考虑求解下列方程的问题: $ax \equiv b \mod n$ 其中$a > 0, n > 0$.
令$\langle a \rangle$表示由a生成的$\mathbb{Z}_n$的子群. 所以当且仅当$[b] \in \langle a \rangle$时, 方程上述有一个解.
对于任意正整数a和n, 如果$d=\gcd(a, n)$, 则在$\mathbb{Z}_n$中, $\langle a \rangle = \langle d \rangle$ 因此 $|\langle a \rangle | = n / d$
当且仅当$d|b$时, 方程$ax\equiv b \mod n$对于未知量x有解, 这里$d = \gcd(a, n)$.
方程$ax\equiv b \mod n$ 要么对模n有d个解, 要么无解, 这里$d = \gcd(a, n)$.
令$d=\gcd(a, n)$, 假设对某些整数$x’$和$y’$, 有$d = ax’+ny’$. 如果 $d | b$ , 则方程 $ax\equiv b \mod n$有一个解的值为 $x_0 = x' (b / d) \mod n$
假设方程$ ax \equiv b \mod n$ 有解(即$d = \gcd(a, n) , d | b$ ), 且$x_0$是该方程的任意一个解. 则改方程对模n有d个不同的解, 分别为$x_i = x_0 + i(n/d)$, 这里$ i = 0, 1, …, d - 1$.

MODULAR-LINEAR-RQUATION-SOLVE(a, b, n)
(d, x', y') = EXTENDED-EUCLID(A, n)
if d|b
	x_0 = x' (b / d) mod n
	for i = 0 to d - 1
		print (x_0 + i(n / d) mod n)
else print "no solutions"

对任意n > 1, 如果$\gcd(a, n) = 1$, 则方程$ax \equiv b \mod n$对模n有唯一解.
对任意n > 1, 如果$\gcd(a, n) = 1$, 则方程$ax \equiv 1 \mod n$对模n有唯一解; 否则无解.

中国剩余定理

(中国剩余定理) 令$n=n_1n_2 \cdots n_k$, 其中因子$n_i$两两互质. 考虑一下对应关系: $a \leftrightarrow (a_1, a_2, \cdots a_k)$ 这里$a\in Z_n$, $a_i \in Z_{n_i}$,
而且对$i = 1, 2, \cdots, k$, $a_i \equiv a \mod n_i$ 因此, 上述映射是一个在$Z_n$和笛卡尔积$Z_{n_1} \times Z_{n_2} \times \cdots Z_{n_k}$之间的一一映射. 通过在合适的系统中对每个坐标位置独立执行操作, 对$Z_{n}$中元素所执行的运算可以等价地作用与对应的k元组. 也就是说, 如果 $a \leftrightarrow (a_1, a_2, \cdots a_k)$ $b \leftrightarrow (b_1, b_2, \cdots b_k)$ 那么 $(a + b) \mod n \leftrightarrow ((a_1 + b_1)\mod n_1, \cdots, (a_k + b_k) \mod n_k)$ $(a - b) \mod n \leftrightarrow ((a_1 - b_1)\mod n_1, \cdots, (a_k - b_k) \mod n_k)$ $ab \mod n \leftrightarrow (a_1b_1\mod n_1, \cdots, a_kb_k \mod n_k)$
如果$n_1, n_2, \cdots, n_k$两两互质, 且$n = n_1, n_2, \cdots, n_k$, 则对任意整数$a_1, a_2, \cdots, a_k$, 关于未知量x的联立方程组 $x \equiv a_i \mod n_i, i = 1, 2, \cdots, k$ 对模n有唯一解.
如果$n_1, n_2, \cdots, n_k$两两互质, 且$n = n_1, n_2, \cdots, n_k$, 则对任意整数x和a,
$x \equiv a \mod n_i, i = 1, 2, \cdots, k$
当且仅当
$x \equiv a \mod n$
根据$(a_1, a_2, \cdots, a_k)$求a: 定义$m_i = n / n_i $, $c_i = m_i (m_i^{-1} \mod n_i)$, 则
$a \equiv (a_1c_1 + a_2c_2 + \cdots + a_kc_k)\mod n$

元素的幂

欧拉定理: 对于任意整数n > 1, $a^{\phi(n)} \equiv 1 \mod n$ 对所有$a \in \mathbb{Z}_n^*$ 都成立.
费马定理: 如果p是素数, 那么$a^{p-1} \equiv 1 \mod p $ 对所有$a \in \mathbb{Z}_p^*$ 都成立.
对于所有素数p > 2和所有正整数e, 使得$\mathbb{Z}_n^*$ 是循环群的n > 1的值为2, 4, $p^e$和$2p^e$.
离散对数定理: 如果g是$\mathbb{Z}_n^*$的一个原根(生成元), 则当且仅当灯饰$x\equiv y\mod \phi(n)$成立时, 有等式$g^{x}\equiv g^y \mod n$成立.
如果p是一个奇素数且$e \ge 1$, 则方程 $x^2 \equiv 1 \mod p^e$ 仅有两个解, 即$x = 1$和$x = -1$.
如果对模n存在1的非平凡平方根, 则n是合数.

用反复平方法求数的幂:

MODULAR-EXPONENTIATION(a, b, n)
c = 0
d = 1
let <b_k, b_{k-1}, ..., b_0> be the binary representation of b
for i = k downto 0
	c = 2c
	d = (d * d)mod n
    if b_i == 1
    	c = c + 1
    	d = (d * a) mod n
return d