Prove001

详细代码请到 「Thematic001. 数论专题」 中查看

目录

• 分解质因数
• 欧拉函数
• 约数
• 最大公约数 & 最小公倍数
• 乘法逆元
• 欧几里得（拓展）
• 中国剩余定理
• 中国剩余定理（拓展）

---

分解质因数

$$\large n=p_{1}^{c_{1}}p_{2}^{c_{2}}\cdots p_{m}^{c_{m}}$$

---

欧拉函数

定义

$\varphi$($x$) 表示求在 $1$ 到 $x$ 的整数中有多少个数与 $x$ 互质

求 $\varphi(n)$

$$\large \varphi(n)=n\times(1-\frac{1}{p_{1}})\times(1-\frac{1}{p_{2}})\times\cdots\times(1-\frac{1}{p_{m}})$$

性质

• $\varphi(1)=\varphi(2)=1$，其余的欧拉函数均为偶数
• 当 $n$ 为素数时，$\varphi(n)=n-1$
• 欧拉函数是积性函数，但不是完全积性。

  即当 $\gcd(n,m)=1$ 时，$\varphi(nm)=\varphi(n)\varphi(m)$

• 当 $n$ 为奇数时，$\varphi(2n)=\varphi(n)$
• 当 $n$ 为素数时，$\varphi(n^{k})=(n-1)\times n^{k-1}$
• 当 $n \geq 1$ 时，$1$ 到 $n$ 中所有与 $n$ 互质的数的和为 $\frac{\varphi(n)}{2}\times n$

  证明：
  若 $\gcd(n,i)=1$，那么 $\gcd(n,n-i)=1$
  即 与 $n$ 互质的数是成对出现的，而且每一对的和都为 $n$。

• 如果 $k \bmod p = 0$ 且 $p$ 为素数，那么 $\varphi(kp)=\varphi(k)\times p$
• 如果 $k \bmod p \neq 0$ 且 $p$ 为素数，那么 $\varphi(kp)=\varphi(k)\times (p-1)$
• 如果 $\gcd(a,p)=1$ ，那么 $a^{\varphi(p)}\equiv 1 \pmod p$

---

约数

求 $n$ 的正约数个数

$$\large (c_{1}+1)(c_{2}+2)\cdots(c_{m}+m)$$

求 $n$ 所有正约数的和

$$\large (1+p_{1}+p_{1}^{2}+\cdots+p_{1}^{c_{1}})\cdots(1+p_{m}+p_{m}^{2}+\cdots+p_{m}^{c_{m}})$$

---

最大公约数 & 最小公倍数

定理

$$\large \gcd(a,b)\times \operatorname{lcm}(a,b)=a\times b$$ $$\large \gcd(ka,kb)=k\times \gcd(a,b)$$ $$\large \operatorname{lcm}(ka,kb)=k\times \operatorname{lcm}(a,b)$$ $$\large \operatorname{lcm}(\frac{S}{a},\frac{S}{b})=\frac{S}{\gcd(a,b)}$$

求最大公倍数

• 更相减损术
• 欧几里得（$\text{ }$辗转相除法$\text{ }$）
• 二进制算法

---

乘法逆元

解决的问题

求下面关于 $x$ 的同余方程的整数解

$$\large ax \equiv 1\pmod b$$

定理

$$\large (\frac{a}{b}) \bmod p$$ $$\large =(a\times a\text{的逆元}) \bmod p$$

求乘法逆元

欧几里得（拓展）

可以将上面的同余方程化为

$$\large ax=1-by$$ $$\large ax+by=1$$

快速幂

这里需要用到费马小定理

若 $a$ 为正整数，$b$ 为素数，$a,b$ 互质，则有

$$\large a^{b-1} \equiv 1 \pmod b$$

把这个式子代入 $ax \equiv 1 \pmod b$ 中，得

$$\large ax \equiv a^{b-1} \pmod b$$ $$\large x \equiv a^{b-2} \pmod b$$

所以这时候方程的解就是 $a^{b-2} \bmod b$

---

欧几里得（拓展）

解决的问题

求下面关于 $x,y$ 的不定方程的整数解

$$\large{ax+by=c}$$

定理

若不定方程有整数解，则

$$\large{\gcd(a,b)|c}$$

若关于这个不定方程的一组解为 $x_{0},y_{0}$， 则这个不定方程的特殊解为

$$\large{x_{special}=\frac{x_{0}\times c}{\gcd(a,b)}}$$

最小解为

$$\large{\text{令 } t=\frac{b}{\gcd(a,b)}}$$ $$\large{\text{则 }x_{min}=(x_{special} \bmod t+t) \bmod t}$$

---

中国剩余定理

解决的问题

已知关于 $x$ 的同余方程组

$$\large\begin{cases} x \equiv b_{1} \pmod{m_{1}}\\ x \equiv b_{2} \pmod{m_{2}}\\ \cdots\\ x \equiv b_{n} \pmod{m_{n}}\\ \end{cases}$$

并且

$$\large \gcd(m_{1},m_{}2,\cdots,m_{n})=1$$

求整数解 $x$

过程

---

中国剩余定理（拓展）

解决的问题

已知关于 $x$ 的同余方程组

$$\large\begin{cases} x \equiv b_{1} \pmod{m_{1}}\\ x \equiv b_{2} \pmod{m_{2}}\\ \cdots\\ x \equiv b_{n} \pmod{m_{n}}\\ \end{cases}$$

并且

$$\large \gcd(m_{1},m_{}2,\cdots,m_{n})>1$$

求整数解 $x$

过程

先看两个方程

$$\large\begin{cases} x \equiv b_{1} \pmod{m_{1}}\\ x \equiv b_{2} \pmod{m_{2}}\\ \end{cases}$$

尝试合并两个式子

转换成

$$\large\begin{cases} x=m_{1}\times x_{1}+b_{1}\\ x=m_{2}\times x_{2}+b_{2}\\ \end{cases}$$

则有

$$\large m_{1}\times x_{1}+b_{1}=m_{2}\times x_{2}+b_{2}$$

由于 $x_{1},x_{2}$ 与符号无关，变形得到

$$\large m_{1}\times x_{1}+m_{2}\times x_{2}=b_{2}-b_{1} (1)$$

此处放上欧几里得（拓展）的式子

$$\large ax+by=c$$

由裴蜀定理得

$$\large\begin{cases} \text{此式有整数解，}\gcd(a,b)\mid c\\ \text{此式无整数解，}\gcd(a,b)\nmid c\\ \end{cases}$$

带入此式，得

$$\large\begin{cases} \text{此式有整数解，}\gcd(x_{1},x_{2})\mid (b_{2}-b_{1})\\ \text{此式无整数解，}\gcd(x_{1},x_{2})\nmid (b_{2}-b_{1})\\ \end{cases}$$

令

$$\large g=\gcd(x_{1},x_{2})$$ $$\large c=b_{2}-b_{1}$$

则有

$$\large m_{1}\times x_{1}+m_{2}\times x_{2}=g (2)$$

用欧几里得（拓展）解 $(2)$ 得

$$\large x_{1}=k_{1}'$$ $$\large x_{2}=k_{2}'$$

设 $(1)$ 的解为

$$\large x_{1}=k_{1}$$ $$\large x_{2}=k_{2}$$

则有

$$\large k_{1}=\frac{k_{1}'\times c}{g}$$ $$\large k_{2}=\frac{k_{2}'\times c}{g}$$ $$\large x_{1}=k_{1}+ \frac{m_{2}}{g}\times l(3) \text{ }\text{ }\text{ }(\text{ }l\text{为参数 })$$ $$\large x_{2}=k_{2}- \frac{m_{1}}{g}\times l$$

由前面的「欧几里得（拓展）」的最小值公式得

$$\large{\text{令 } t=\frac{m_{2}}{\gcd(m_{1},m_{2})}}$$ $$\large k_{1_{min}}=(k_{1}\bmod t+t)\bmod t$$

将 $(3)$ 代入前面的 $x=m_{1}\times x_{1}+b_{1}$ 得

$$\large x=m_{1}\times(k_{1}+ \frac{m_{2}}{g}\times l)+b_{1}$$ $$\large x=m_{1}\times k_{1}+ m_{1}\times \frac{m_{2}}{g}\times l+b_{1}$$ $$\large\text{令 } B=m_{1}\times k_{1}+b_{1}$$ $$\large x=B+m_{1}\times \frac{m_{2}}{g}\times l$$ $$\large\text{即 } B=x=B+\operatorname{lcm}(m_{1},m_{2})\times l$$ $$\large\text{等价于 }x\equiv B \pmod {\operatorname{lcm}(m_{1},m_{2})}$$

合并完成！

继续合并……

合并到最后，方程组就变成了

$$\large x\equiv x_{0} \pmod {\operatorname{lcm}(m_{1},m_{2},\cdots,m_{n})}$$

$x_{0}$ 即为方程组的一个整数解