素数运算

---

素数的定义

质数（Prime number），又称素数，指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数（也可定义为只有1与该数本身两个因数的数）

素数的性质和定理

• 欧拉证明：素数在数量上是无限的（不存在最大的素数）
• 存在任意长的一段连续数，其中的所有数都是合数（相邻素数之间的间隔任意大）
• 所有大于2的素数都可以唯一地表示成两个平方数之差。
• 当$n$为大于2的整数时，$2^n+1$和$2^n-1$两个数中，如果其中一个数是素数，那么另一个数一定是合数。
• 哥德巴赫猜想：每个大于4的偶数可以写成两个奇素数的和（陈景润证明：偶数为一个素数及一个不超过两个素数的乘积之和，简称“1+2”）
• 唯一分解定理：每个正整数都可以唯一地表示成素数的乘积，即有唯一的分解质因数的方案：$n=p_1^{e_1}p_2^{e_2}…p_k^{e_k}$
  根据上面的式子，可以推知$n$共有 $(e_{1}+1)(e_{2}+1)…(e_{k}+1)$个约数。

素数的判定

试除法

试用2…$\lfloor \sqrt{n} \rfloor$去除$n$（更好的做法是筛选出[2..$\sqrt{n}$]里的所有素数），$n$是素数当且仅当没有一个试用的除数能被$n$整除。时间复杂度：$O(\sqrt{n})$

Miller_Rabin方法

米勒-拉宾素性检验是一种素数判定法则，利用随机化算法判断一个数是合数还是可能是素数。
测试大素数的Miller_Rabin方法基于下述定理：

• 费马小定理：如果$n$是素数，$a$是整数，则 $a^n \equiv a\pmod{n}$
  如果 $a$ 不是 $n$ 的倍数，也可以写成 $a^{n-1} \equiv 1\pmod{n}$
• 二次探测定理：如果$n$是奇素数，则$a^2 ≡ 1\pmod n$的解为$a ≡ 1\pmod n$或$a ≡ n-1\pmod n$

重复$k$次计算，每次在$[1,n-1]$范围内随机选取一个$a$，若$a^{n-1} \neq 1\pmod{n}$，则$n$是合数。若随机选取的$k$个$a$都使得$a^{n-1} \equiv 1\pmod{n}$，则$n$是素数或伪素数。
若使用模指数运算的快速算法，这个算法的运行时间是：$O(klog_{2}^3n)$
经验结论：

• if n < 3,215,031,751, it is enough to test a = 2, 3, 5, and 7;
• if n < 4,759,123,141, it is enough to test a = 2, 7, and 61;
• if n < 18,446,744,073,709,551,616 = $2^{64}$, it is enough to test a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, and 37.
• if n < 318,665,857,834,031,151,167,461, it is enough to test a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, and 37.
• if n < 3,317,044,064,679,887,385,961,981, it is enough to test a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, and 41.

素数的筛法

筛选[2..$n$]中的所有素数

埃拉托斯特尼筛法

按递增顺序搜索筛中的最小数，将其倍数从筛中筛去，最终筛中留下的数即为素数。
时间复杂度：$O(nloglogn)$

欧拉筛法

在埃式筛法上改进：每个合数仅被它最小的质因数筛去。
时间复杂度：$O(n)$
此方法可以求积性函数$f(x)$，即在$O(n)$时间复杂度内预处理$f(1)$,$f(2)$ … $f(n)$的值，典型的用途是求欧拉函数。

公约数问题

---

最大公约数和最小公倍数

若
$x=p_1^{k_1}p_2^{k_2}…p_r^{k_r}$
$y=p_1^{n_1}p_2^{n_2}…p_r^{n_r}$
则
$GCD(x,y)=p_1^{min(k_1,n_1)}p_2^{min(k_2,n_2)}…p_r^{min(k_r,n_r)}$
$LCM(x,y)=p_1^{max(k_1,n_1)}p_2^{max(k_2,n_2)}…p_r^{max(k_r,n_r)}$
同时可以得到
$x×y=GCD(x,y)×LCM(x,y)$

若
$x=p×GCD(x,y)$
$y=q×GCD(x,y)$
则
$x+y=(p+q)×GCD(x,y)$
那么 $GCD(x,y)=GCD(x,x+y)$
同理可得 $GCD(x,y)=GCD(x+y,LCM(x,y))$

欧几里得算法

$$
GCD(a,b)=
\begin{cases}
b& \text{a = 0}\\
GCD(b,a\mod b)& \text{a $\neq$ 0}
\end{cases}
$$
简单证明：
设$g=GCD(a,b)$
将$a \mod b$化成$a$与$b$的线性组合，即$a \mod b=a-\lfloor{\frac{a}{b}}\rfloor *b$。由于$g$能整除$a$和$b$，那么$g$一定能整除$a$与$b$的线性组合，即$g$能整除$(a \% b)$，所以$GCD(a,b)=GCD(b,a\% b)$.
时间复杂度：$O(log \max(a,b))$

扩展欧几里得算法

已知整数$a$、$b$，扩展欧几里得算法可以在求得$a$、$b$的最大公约数的同时，能找到整数$x$、$y$（其中一个很可能是负数）满足$ax+by=GCD(a,b)$.
若$b=0$，则$GCD(a,b)=a$，$x=1$，$y=0$；
若$b\neq 0$，首先递归求解满足$bx’+(a\mod b)y’=GCD(b,a\mod b)$的$x’$、$y’$，因为$GCD(a,b)=GCD(b,a\% b)$，所以有以下等式成立：
$$bx’+(a- \lfloor{\frac{a}{b}}\rfloor b)y’=ay’+b(x’- \lfloor{\frac{a}{b}}\rfloor y’)=ax+by$$
选择$x=y’$，$y=x’- \lfloor{\frac{a}{b}}\rfloor y’$就可以满足等式。

应用扩展欧几里得算法，可以求解如下形式的二元一次不定方程：
$$ax+by=c$$
首先先求解$ax+by=GCD(a,b)$的$x$和$y$，记$g=GCD(a,b)$.
若$c$不能被$g$整除，则无整数解；
否则初始解：$x_{0}=x\frac{c}{g}$，$y_{0}=y\frac{c}{g}$.
不定方程的通解形式为：
$$
\begin{cases}
x_{k}=x_{0}+k\frac{b}{g} & \\
y_{k}=y_{0}-k\frac{a}{g} & \text{k $\in $ Z}
\end{cases}
$$

同余问题

同余关系式

• 威尔逊定理：$(p-1)! \equiv -1 ({\mbox{mod}} p)$
• 费马小定理：${\displaystyle a^{p}\equiv a{\pmod {p}}}$
• 欧拉定理：$a^{\varphi (n)}\equiv 1{\pmod {n}}$
• 卡迈克尔函数：$a^{\lambda (n)}\equiv 1{\pmod {n}}$
• 阶乘幂：$(x)_{k}\equiv x(x-1)(x-2)\cdots (x-k+1)\equiv 0{\pmod {k!}}$

其它定理

• 若 $ac\equiv bc\pmod n$ 且 $GCD(c,n)=d$，则$a \equiv b \pmod{ \frac {n}{d}}$
• 若 $d \neq 0$ 且 $ad \equiv bd \pmod {nd}$，则 $a \equiv b \pmod n$
• 若 $n$ 和 $a$ 互质，则一次同余方程 $ax+b\equiv 0 \pmod n$ 有解
  模运算满足交换律（除了除法）

同余方程

• 求解一次同余方程 $ax\equiv b\pmod n$
  也就是要求解二元一次方程 $ax-my=b$，使用扩展欧几里得算法求解。
  令 $g=GCD(a,m)$，如果$b$不能被$g$整除，那么同余方程无解；否则有$g$个解，即
  $x_k=x_0+k \frac{m}{g}(0\leq k < g)$
• 求解同余方程 $a^x\equiv b\pmod n$
• 求解一元线性同余方程组
  $$ \begin{cases} x≡a_1 \pmod {m_1} & \\x≡a_2 \pmod {m_2} & \... \ x≡a_n \pmod {m_n} &\\\end{cases} $$

• 中国剩余定理

  若$m_1$、$m_2$ …. $m_n$ 两两互质，则对任意整数 $a_1$、$a_2$ …. $a_n$ 方程组有解。
  令
  $M=m_1m_2m_3…m_n$
  $w_i=\frac{M}{m_i}$
  $w_i’$ 为 $w_i$ 模 $m_i$ 下的逆元，即 $w_iw_i’≡1 \pmod {m_i}$
  则
  $x=(a_1w_1w_1’+a_2w_2w_2’+…+a_nw_nw_n’) \pmod M$

模逆元

在求解除法取模问题 $(a / b) \% n$ 时，我们可以转化为 $(a \% (b \cdot n))/b$。
但是 $b$ 范围很大时，$bn$ 可能存不下，所以我们使用乘法逆元将除法转换为乘法。
在模 $n$ 的意义下，把 $a$ 的模逆元写作 $a^{-1}$，满足$aa^{-1}\equiv 1{\pmod {n}}$，那么 $\frac {a}{b}=ab^{-1} \pmod n$
*$a$ 对模数 $n$ 之模逆元存在的充分必要条件是 $a$ 和 $n$ 互质。
求解模逆元的几种方法：

• 使用扩展欧几里得算法
  求解 $ax \equiv 1 \pmod n$，即 $ax-ny=1$。若 $g=GCD(a,n)=1$，该模逆元存在，且有无穷个解，选取最小正整数解即可。
• 使用欧拉定理
  当 $a$ 和 $n$ 互质时，有 $a^{\varphi (n)}\equiv 1{\pmod n}$。那么分解为 $a^{\varphi (n)}=a\cdot a^{\varphi (n)-1}\equiv 1{\pmod {n}}$，其中的 $a^{\varphi (n)-1}$ 即为 $a$ 关于模 $n$ 之模逆元。特别地，若 $n$ 为素数时，$a$ 的模逆元为 $a^{n-2}$（费马小定理）
• 使用线性递推法
  $n$为奇素数时，记 $i$ 的逆元为 $inv[i]$，有递推式：
  $$ inv[i]=\begin{cases}1& \text{i = 1}\(n-\frac{n}{i}) \cdot inv[n \% i]\% n & \text{i $>$ 1}\end{cases} $$
  证明（略，公式移项）
  此方法以在 $O(n)$ 时间复杂度求解小于 $n$ 的所有模逆元。

Lucas定理

---

在数论中，Lucas定理用于计算二项式系数 $\tbinom {m}{n}$ 被质数 $p$ 除的所得的余数。

公式

对于非负整数m和n和素数p，同余式：
$$ \binom {m}{n}\equiv \prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}{\pmod {p}} $$
成立。其中：
$$ m=m_{k}p^{k}+m_{k-1}p^{k-1}+\cdots +m_{1}p+m_{0}$$,
并且
$$ n=n_{k}p^{k}+n_{k-1}p^{k-1}+\cdots +n_{1}p+n_{0} $$
是 $m$ 和 $n$ 的 $p$ 进制展开。当 $m$ < $n$ 时，二项式系数 $\tbinom {m}{n}=0$。

证明

略，详见参考资料。

扩展

如果 $p$ 不是质数，对其进行质因子分解，然后对于每个质因子 $p_{i}^{e_{i}}$ 都得到一个同余方程 $x≡a_{i}(\mod p_{i}^{e_{i}})$，然后用中国剩余定理。

链接

link1
link2
link3
link4

积性函数

在数论中，积性函数是指一个定义域为正整数 $n$ 的算术函数 $f(n)$，有如下性质：$f(1) = 1$，且当 $a$ 和 $b$ 互质时，$f(ab) = f(a) f(b)$
若对于任意两个正整数 $a$ 和 $b$ ，都有 $f(ab)=f(a)f(b)$，则称此函数 $f$ 为完全积性函数。
显然，对于任意积性函数，$f(1)=1$
$GCD(a,b)$ 也是积性函数（当一个数字固定的情况下）

欧拉函数

定义欧拉函数$φ(n)$，表示小于等于 $n$ 且与 $n$ 互质的正整数的个数。
例如：$φ(1)=φ(2)=1$，$φ(3)=φ(4)=2$
欧拉函数是积性函数，即当 $n$、$m$ 互质时，$φ(nm)=φ(n)φ(m)$。但不是完全积性函数。

欧拉函数的值

• 当 $n$ 是素数时，$φ(n)=n-1$
• 当 $n$ 是合数时，$φ(n)<n-1$，且 $φ(n) \leq n- \sqrt n$

若 $n$ 是素数 $p$ 的 $k$ 次幂，$φ(n)=φ(p^{k})=p^{k}-p^{k-1}=(p-1)p^{k-1}$，因为除了 $p$ 的倍数外，其他数都跟 $n$ 互质。

一般地，设 $n=p_1^{k_1}p_2^{k_2}…p_r^{k_r}$
则
$$φ(n)=\prod_{i=1}^{r}p_{i}^{k_{i}-1}(p_{i}-1)=n \prod_{p|n} \left(1-{\frac {1}{p}} \right)$$

欧拉定理

若两个正整数 $n$ 和 $a$ 互质，则 $a^{φ(n)} \equiv 1 \pmod n$
推论：$a^{φ(n)+1} \equiv a \pmod n$
欧拉定理的一个特例是费马小定理（若 $n$ 是素数，则 $φ(n)=n-1$）。

欧拉函数的性质

• $n$ 的欧拉函数 $\varphi (n)$ 也是循环群 $C_n$ 的生成元的个数，即
  $$ \sum_{d \mid n} \varphi (d)=n $$
  其中的 $d$ 为 $n$ 的正约数。
  运用莫比乌斯反演来“翻转”这个和，就可以得到另一个关于 $\varphi (n)$ 的公式：
  $$ \varphi (n)=\sum _{d \mid n} {d\cdot \mu (n/d)}$$
  其中 $μ$ 是所谓的莫比乌斯函数，定义在正整数上。
• 当 $n>1$ 时，$1…n$ 中与 $n$ 互质的整数和为 $\frac{n\varphi (n)}{2}$
• 当 $n$ 为奇数时，有 $\varphi (2n)= \varphi (n)$

莫比乌斯函数

定义莫比乌斯函数$μ(n)$，表示非平方数 $n$ 的质因子个数，$μ(n)$ 是 $φ(n)$ 的反演函数。

参考资料

---

Matrix67 Blog
维基百科 质数
维基百科 辗转相除法
维基百科 扩展欧几里得算法
模逆元
维基魔杖 卢卡斯定理
维基百科 同余
维基百科 积性函数