## 7 数论算法

2019-04-06 15:31 CST
2019-06-06 23:55 CST
CC BY-NC 4.0

## 31.2 Greatest common divisor

Theorem 31.11 (Lame’s theorem) For any integer $k \geqslant 1$, if $a > b \geqslant 1$ and $b < F_{k+1}$, then the call $\texttt{Eculid}(a, b)$ makes fewer than $k$ recursive calls.

## 31.3 Modular arithmetic

The size of $\mathbb{Z}_n^*$ (multiplicative group modulo $n$) is denoted as $\phi(n)$, known as Euler’s phi function, satisfies the equation $$\phi(n) = n \prod_{p: p \text{ is prime and } p \mid n} \left( 1 - \dfrac{1}{p} \right)$$

If $p$ is prime, $\phi(p) = p-1$.

If $n$ is composite, then $\phi(n) < n-1$, and $$\phi(n) > \dfrac{n}{e^\gamma \ln\ln n + \frac{3}{\ln\ln n}}$$ for $n \geqslant 3$, where $\gamma = 0.5772156649 \dots$ is Euler’s constant.

Theorem 31.15 (Lagrange’s theorem) If $(S, \oplus)$ is a finite group and $(S', \oplus)$ is a subgroup of $(S, \oplus)$, then $|S'|$ is a divisor of $|S|$.

Corollary 31.16 If $S'$ is a proper subgroup of a finite group $S$, then $|S'| \leqslant \dfrac{|S|}{2}$.

Corollary 31.19 If $(S, \oplus)$ is a finite group with identity $e$, then for all $a \in S$, $a^{(|S|)} = e$. （结合31.15 拉格朗日定理，生成群的大小整除$|S|$，故成立。）

## 31.4 Solving modular linear equations

Theorem 31.20 For any positive integers $a$ and $n$, if $d = \gcd(a, n)$, then $$\langle a \rangle = \langle d \rangle = { 0, d, 2d, \dots, ((n/d)-1)d }$$ in $\mathbb{Z}_n$, and thus $\vert \langle a \rangle \vert = n / d$.

Corollary 31.21 The equation $ax \equiv b \mod n$ is solvable for the unknown $x$ if and only if $d \mid b$, where $d = \gcd(a, n)$.

Corollary 31.22 The equation $ax \equiv b \mod n$ either has $d$ distinct solutions modulo $n$, where $d = \gcd(a, n)$, or it has no solutions.

Theorem 31.23 Let $d = \gcd(a, n)$, and suppose that $d = ax' + ny'$ for some integers $x'$ and $y'$. If $d \mid b$, then the equation $ax \equiv b \mod n$ has as one of its solutions the value $x_0$, where $$x_0 = x'(b/d) \mod n$$

Theorem 31.24 Suppose that the equation $ax \equiv b \mod n$ is solvable (that is, $d \mid b$, where $d = \gcd(a, n)$) and that $x_0$ is any solution to this solution. Then, this equation has exactly $d$ distinct solutions, modulo $n$, given by $x_i = x_0 + i(n/d)$ for $i = 0, 1, \dots, d - 1$. The above algorithm performs $O(\lg n + \gcd(a, n))$ arithmetic operations, since Extended-Euclid performs $O(\lg n)$ arithmetic operations, and each iteration of the for loop of lines 4-5 performs a constant number of arithmetic operations.

Corollary 31.25 For any $n > 1$, if $\gcd(a, n) = 1$, then the equation $ax \equiv b \mod n$ has a unique solution, modulo $n$.

Corollary 31.26 For any $n > 1$, if $\gcd(a, n) = 1$, then the equation $ax \equiv 1 \mod n$ has a unique solution, modulo $n$. (multiplicative inverse of $a$) Otherwise, it has no solution.

## 31.5 The Chinese remainder theorem

Theorem 31.27 (Chinese remainder theorem) Let $n = n_1n_2 \cdots n_k$, where $n_i$ are pairwise relatively prime. Consider the correspondence $$a \leftrightarrow (a_1, a_2, \dots, a_k)$$ where $a \in \mathbb{Z}_n$, $a_i \in \mathbb{Z}_{n_i}$, and $$a_i = a \mod n_i$$ for $i = 1, 2, \dots, k$. Then, the above mapping is a one-to-one correspondence (bijection) between $\mathbb{Z}_n$ and the Cartesian product $\mathbb{Z}_{n_1} \times \mathbb{Z}_{n_2} \times \cdots \times \mathbb{Z}_{n_k}$. Operations performed on the elements of $\mathbb{Z}_n$ can be equivalently performed on the corresponding $k$-tuples by performing the operations independently in each coordinate position in the appropriate system. That is, if \begin{aligned} a &\leftrightarrow (a_1, \dots, a_k) \ b &\leftrightarrow (b_1, \dots, b_k) \end{aligned} then \begin{aligned} (a+b) \mod n &\leftrightarrow ((a_1 + b_1) \mod n_1, \dots, (a_k + b_k) \mod n_k) \ (a-b) \mod n &\leftrightarrow ((a_1 - b_1) \mod n_1, \dots, (a_k - b_k) \mod n_k) \ (ab) \mod n &\leftrightarrow ((a_1 b_1) \mod n_1, \dots, (a_k b_k) \mod n_k) \end{aligned}

Corollary 31.28 If $n_1, n_2, \dots, n_k$ are pairwise relatively prime and $n = n_1 n_2 \cdots n_k$, then for any integers $a_1, a_2, \dots, a_k$, the set of simultaneous equations $$x \equiv a_i \mod n_i$$ for $i = 1, 2, \dots, k$, has a unique solution modulo $n$ for the unknown $x$.

Corollary 31.29 If $n_1, n_2, \dots, n_k$ are pairwise relatively prime and $n = n_1 n_2 \cdots n_k$, then for all integers $x$ and $a$, $$x \equiv a \mod n_i$$ for $i = 1, 2, \dots, k$ if and only if $$x \equiv a \mod n .$$

## 31.6 Powers of an element

Theorem 31.30 (Euler’s theorem) For any integer $n > 1$, $$a^{\phi(n)} \equiv 1 \mod n$$ for all $a \in \mathbb{Z}_n^*$.

Theorem 31.31 (Fermat’s theorem) If $p$ is prime, then $$a^{p-1} \equiv 1 \mod p$$ for all $a \in \mathbb{Z}_n^*$.

If $\text{ord}_n(g) = \vert \mathbb{Z}_n^* \vert$, then every element in $\mathbb{Z}_n^*$ is a power of $g$, modulo $n$, and $g$ is a **primitive root** or a **generator** of $\mathbb{Z}_n^*$. If $\mathbb{Z}_n^*$ possesses a primitive root, the group $\mathbb{Z}_n^*$ is cyclic.

Theorem 31.32 The values of $n > 1$ for which $\mathbb{Z}_n^*$ is cyclic are $2, 4, p^e$ and $2p^e$, for all primes $p > 2$ and all positive integers $e$.

If $g$ is a primitive root of $\mathbb{Z}_n^$ and $a$ is any element of $\mathbb{Z}_n^$, then there exists a $\mathbb{z}$ such that $g^{\mathbb{z}} \equiv a \mod n$. This $\mathbb{z}$ is a discrete logarithm or an index of $a$, modulo $n$, to the base $g$; we denote this value as $\text{ind}_{n, g}(a)$.

Theorem 31.33 (Discrete logarithm theorem) If $g$ is a primitive root of $\mathbb{Z}_n^*$, then the equation $g^x \equiv g^y \mod n$ holds if and only if the equation $x \equiv y \mod \phi(n)$ holds.

Theorem 31.34 If $p$ is an odd prime and $e \geqslant 1$, the the equation $$x^2 \equiv 1 \mod p^e$$ has only two solutions, namely $x = 1$ and $x = -1$.

A number $x$ is a nontrival square root of 1, modulo n, if it satisfies the equation $x^2 \equiv 1 \mod n$ but $x$ is equivalent to neither of the two “trival” square roots: $1$ or $-1$, modulo $n$.

Corollary 31.35 If there exists a nontrivial square root of $1$, modulo $n$, then $n$ is composite.

### Raising to powers with repeated squaring

（快速幂算法，贴图跑路） 