整除性

整除

定义

设 $a,b\in\mathbf{Z}$，$a\ne 0$。如果 $\exists q\in\mathbf{Z}$，使得 $b=aq$，那么就说 $b$ 可被 $a$ 整除，记作 $a\mid b$；$b$ 不被 $a$ 整除记作 $a\nmid b$。

整除的性质
  • $a\mid b\iff-a\mid b\iff a\mid-b\iff|a|\mid|b|$
  • $a\mid b\land b\mid c\implies a\mid c$
  • $a\mid b\land a\mid c\iff\forall x,y\in\mathbf{Z}, a\mid(xb+yc)$

证明：因为$ b \mid a $且 $ b \mid c $

必然存在 $ q_1, q_2 \in \mathbb{Z} $，使得 $ a = q_1 b $ 且 $ c = q_2 b $

对于任意 $ s, t \in \mathbb{Z} $，有 $sa = s q_1 b$ 且 $tc = t q_2 b$

必有 $sa \pm tc = s q_1 b \pm t q_2 b$

​ $ = b (s q_1 \pm t q_2) $
所以 $ b \mid (sa \pm tc) $

  • $a\mid b\land b\mid a\implies b=\pm a$
  • 设 $m\ne0$，那么 $a\mid b\iff ma\mid mb$。
  • 设 $b\ne0$，那么 $a\mid b\implies|a|\le|b|$。
  • 设 $a\ne0,b=qa+c$，那么 $a\mid b\iff a\mid c$。

素数与合数

定义

设整数 $p\ne0,\pm1$。如果 $p$ 除了平凡约数外没有其他约数，那么称 $p$ 为 素数（不可约数）。

若整数 $a\ne0,\pm 1$ 且 $a$ 不是素数，则称 $a$ 为 合数。

$p$ 和 $-p$ 总是同为素数或者同为合数。如果没有特别说明，素数总是指正的素数。

整数的因数是素数，则该素数称为该整数的素因数（素约数）。

素数与合数的简单性质
  • 大于 $1$ 的整数 $a$ 是合数，等价于 $a$ 可以表示为整数 $d$ 和 $e$（$1<d,e<a$）的乘积。
  • 如果素数 $p$ 有大于 $1$ 的约数 $d$，那么 $d=p$。
  • 大于 $1$ 的整数 $a$ 一定可以表示为素数的乘积。
  • 对于合数 $a$，一定存在素数 $p\le\sqrt{a}$ 使得 $p\mid a$。

证明： 既然 n > 1 是合数，则 n = ab ，其中 1 < a < n 且 1 < b < n 。

首先，不可能 $ a > \sqrt{n} $ 且 $ b > \sqrt{n} $，因为这样 $ ab > \sqrt{n} \cdot \sqrt{n} = n $，与 $ n = ab $ 矛盾。

假设 $ a \leq \sqrt{n} $。根据引理2-1，既然 $ a > 1 $，$ a $ 必有素因子 $ p $（即 $ p \mid a $）。

因为 $ p \mid a $，$ a \mid n $，所以 $ p \mid n $。

又因为 $ p \leq a $，$ a \leq \sqrt{n} $，所以 $ p \leq \sqrt{n} $。得证！

  • 素数有无穷多个。
  • 所有大于 $3$ 的素数都可以表示为 $6n\pm 1$ 的形式。
  • 任何大于1的整数必有素因子。

证明：设集合S包含所有大于1且没有素因子的整数。只需证明S为空集。假设S不为空集，m∈S是S中最小整数（m>1且没有素因子）。

  1. m不可能为素数，因为任何素数都有素因子（它本身）。
  2. m为合数，则有m=ab，其中1<a<m，1<b<m。

既然a<m，必有a∉S。a必有素因子，设为p。

因为 p|a 且 a|m，则 p|m，

故而m有素因子p，与m∈S矛盾，得证。

算术基本定理
算术基本引理

​ 设 $p$ 是素数，$p\mid a_1a_2$，那么 $p\mid a_1$ 和 $p\mid a_2$ 至少有一个成立。

算术基本引理是素数的本质属性，也是素数的真正定义。

算术基本定理（唯一分解定理）

​ 设正整数 $a$，那么必有表示：
​
$$
a=p_1p_2\cdots p_s
$$

其中 $p_j(1\le j\le s)$ 是素数。并且在不计次序的意义下，该表示唯一。

标准素因数分解式

​ 将上述表示中，相同的素数合并，可得：
​
$$
a={p_1}^{\alpha_1}{p_2}^{\alpha_2}\cdots{p_s}^{\alpha_s},p_1<p_2<\cdots<p_s
$$

称为正整数 $a$ 的标准素因数分解式。

算术基本定理和算术基本引理，两个定理是等价的。

模运算

定义

设 $ a, b \in \mathbb{Z} $ 且 $ b > 0 $，如果 $ q, r \in \mathbb{Z} $ 满足$ a = qb + r, $且$ 0 \leq r < b, $则定义 $a \mod b := r$

运算规则

模运算与基本四则运算有些相似，但是除法例外。其规则如下：

$b \mid a \iff a \mod b = 0$

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

$(a - b) \mod p = (a \mod p - b \mod p) \mod p$

$(a * b) \mod p = (a \mod p * b \mod p) \mod p $

最大公约数

定义

最大公约数即为 Greatest Common Divisor，常缩写为 gcd。

一组整数的公约数，是指同时是这组数中每一个数的约数的数。$\pm 1$ 是任意一组整数的公约数。

一组整数的最大公约数，是指所有公约数里面最大的一个。

对不全为 $0$ 的整数 $a,b$，将其最大公约数记为 $\gcd(a,b)$，不引起歧义时可简写为 $(a,b)$。

对不全为 $0$ 的整数 $a_1,\dots,a_n$，将其最大公约数记为 $\gcd(a_1,\dots,a_n)$，不引起歧义时可简写为 $(a_1,\dots,a_n)$。

最大公约数与最小公倍数的性质

最大公约数有如下性质：

  • $(a_1,\dots,a_n)=(|a_1|,\dots,|a_n|)$；
  • $(a,b)=(b,a)$；
  • 若 $a\ne 0$，则 $(a,0)=(a,a)=|a|$；
  • $(bq+r,b)=(r,b)$；
  • $(a_1,\dots,a_n)=((a_1,a_2),a_3,\dots,a_n)$。进而 $\forall 1<k<n-1,~(a_1,\dots,a_n)=((a_1,\dots,a_k),(a_{k+1},\dots,a_n))$；
  • 对不全为 $0$ 的整数 $a_1,\dots,a_n$ 和非零整数 $m$，$(ma_1,\dots,ma_n)=|m|(a_1,\dots,a_n)$；
  • 对不全为 $0$ 的整数 $a_1,\dots,a_n$，若 $(a_1,\dots,a_n)=d$，则 $(a_1/d,\dots,a_n/d)=1$；
  • $(a^n,b^n)=(a,b)^n$。

最大公约数还有如下与互素相关的性质：

  • 若 $b|ac$ 且 $(a,b)=1$，则 $b\mid c$；
  • 若 $b|c$、$a|c$ 且 $(a,b)=1$，则 $ab\mid c$；
  • 若 $(a,b)=1$，则 $(a,bc)=(a,c)$；
  • 若 $(a_i,b_j)=1,~\forall 1\leq i\leq n,1\leq j\leq m$，则 $\left(\prod_i a_i,\prod_j b_j\right)=1$。特别地，若 $(a,b)=1$，则 $(a^n,b^m)=1$；
  • 对整数 $a_1,\dots,a_n$，若 $\exists v\in \mathbf{Z},\prod_i a_i=v^m$，且 $(a_i,a_j)=1,\forall i\ne j$，则 $\forall 1\leq i\leq n,~\sqrt[m]{a_i}\in\mathbf{Z}$。

最小公倍数有如下性质：

  • $[a_1,\dots,a_n]=[|a_1|,\dots,|a_n|]$；
  • $[a,b]=[b,a]$；
  • 若 $a\ne 0$，则 $[a,1]=[a,a]=|a|$；
  • 若 $a\mid b$，则 $[a,b]=|b|$；
  • $[a_1,\dots,a_n]=[[a_1,a_2],a_3,\dots,a_n]$。进而 $\forall 1<k<n-1,~[a_1,\dots,a_n]=[[a_1,\dots,a_k],[a_{k+1},\dots,a_n]]$；
  • 若 $a_i\mid m,~\forall 1\leq i\leq n$，则 $[a_1,\dots,a_n]\mid m$；
  • $[ma_1,\dots,ma_n]=|m|[a_1,\dots,a_n]$；
  • $[a,b,c][ab,bc,ca]=[a,b][b,c][c,a]$；
  • $[a^n,b^n]=[a,b]^n$。

最大公约数和最小公倍数可以组合出很多奇妙的等式，如：

  • $(a,b)[a,b]=|ab|$；
  • $(ab,bc,ca)[a,b,c]=|abc|$；
  • $\dfrac{(a,b,c)^2}{(a,b)(b,c)(a,c)}=\dfrac{[a,b,c]^2}{[a,b][b,c][a,c]}$。

这些性质均可通过定义或 唯一分解定理 证明，其中使用唯一分解定理的证明更容易理解。

欧几里得算法
过程

如果我们已知两个数 $a$ 和 $b$，如何求出二者的最大公约数呢？不妨设 $a > b$。我们发现如果 $b$ 是 $a$ 的约数，那么 $b$ 就是二者的最大公约数。

下面讨论不能整除的情况，即 $a = b \times q + r$，其中 $r < b$。

我们通过证明可以得到 $\gcd(a,b)=\gcd(b,a \bmod b)$，过程如下：

证明

​ 设 $a=bk+c$，显然有 $c=a \bmod b$。设 $d \mid a,~d \mid b$，则 $c=a-bk,
​ \frac{c}{d}=\frac{a}{d}-\frac{b}{d}k$。
​

由右边的式子可知 $\frac{c}{d}$ 为整数，即 $d \mid c$，所以对于 $a,b$ 的公约数，它也会是 $b,a \bmod b$ 的公约数。

反过来也需要证明：

设 $d \mid b,d\mid (a \bmod b)$，我们还是可以像之前一样得到以下式子
$$
\frac{a\bmod b}{d}=\frac{a}{d}-\frac{b}{d}k,\frac{a\bmod b}
{d}+\frac{b}{d}k=\frac{a}{d}
$$
因为左边式子显然为整数，所以 $\frac{a}{d}$ 也为整数，即 $d \mid a$，所以 $b,a\bmod b$ 的公约数也是 $a,b$ 的公约数。

既然两式公约数都是相同的，那么最大公约数也会相同。

所以得到式子 $\gcd(a,b)=\gcd(b,a\bmod b)$

既然得到了 $\gcd(a, b) = \gcd(b, r)$，这里两个数的大小是不会增大的，那么我们也就得到了关于两个数的最大公约数的一个递归求法。

扩展的欧几里得算法

最大公约数表示公理

设$a, b \in \mathbb{Z}$，$d = \gcd(a,b)$，则$\exists s,t \in \mathbb{z}$，使得 $as+bt=d$

特别的：$\gcd(a,b)=1 \iff as+bt=1$

推论：$d \mid v \iff as+bt=v$

扩展的欧几里得算法

扩展欧几里得算法（Extended Euclidean algorithm, EXGCD），常用于求 $ax+by=\gcd(a,b)$ 的一组可行解。

过程

设

$ax_1+by_1=\gcd(a,b)$

$bx_2+(a\bmod b)y_2=\gcd(b,a\bmod b)$

由欧几里得定理可知：$\gcd(a,b)=\gcd(b,a\bmod b)$

所以 $ax_1+by_1=bx_2+(a\bmod b)y_2$

又因为 $a\bmod b=a-(\lfloor\frac{a}{b}\rfloor\times b)$

所以 $ax_1+by_1=bx_2+(a-(\lfloor\frac{a}{b}\rfloor\times b))y_2$

$ax_1+by_1=ay_2+bx_2-\lfloor\frac{a}{b}\rfloor\times by_2=ay_2+b(x_2-\lfloor\frac{a}{b}\rfloor y_2)$

因为 $a=a,b=b$，所以 $x_1=y_2,y_1=x_2-\lfloor\frac{a}{b}\rfloor y_2$

将 $x_2,y_2$ 不断代入递归求解直至 $\gcd$（最大公约数，下同）为 $0$ 递归 $x=1,y=0$ 回去求解。

最小公倍数

定义

一组整数的公倍数，是指同时是这组数中每一个数的倍数的数。0 是任意一组整数的公倍数。

一组整数的最小公倍数，是指所有正的公倍数里面，最小的一个数。

对整数 $a,b$，将其最小公倍数记为 $\operatorname{lcm}(a,b)$，不引起歧义时可简写为 $[a,b]$。

对整数 $a_1,\dots,a_n$，将其最小公倍数记为 $\operatorname{lcm}(a_1,\dots,a_n)$，不引起歧义时可简写为 $[a_1,\dots,a_n]$。

两个数

设 $a = p_1^{k_{a_1}}p_2^{k_{a_2}} \cdots p_s^{k_{a_s}}$，$b = p_1^{k_{b_1}}p_2^{k_{b_2}} \cdots p_s^{k_{b_s}}$

我们发现，对于 $a$ 和 $b$ 的情况，二者的最大公约数等于

$p_1^{\min(k_{a_1}, k_{b_1})}p_2^{\min(k_{a_2}, k_{b_2})} \cdots p_s^{\min(k_{a_s}, k_{b_s})}$

最小公倍数等于

$p_1^{\max(k_{a_1}, k_{b_1})}p_2^{\max(k_{a_2}, k_{b_2})} \cdots p_s^{\max(k_{a_s}, k_{b_s})}$

由于 $k_a + k_b = \max(k_a, k_b) + \min(k_a, k_b)$

所以得到结论是 $\gcd(a, b) \times \operatorname{lcm}(a, b) = a \times b$

要求两个数的最小公倍数，先求出最大公约数即可。

多个数

可以发现，当我们求出两个数的 $\gcd$ 时，求最小公倍数是 $O(1)$ 的复杂度。那么对于多个数，我们其实没有必要求一个共同的最大公约数再去处理，最直接的方法就是，当我们算出两个数的 $\gcd$，或许在求多个数的 $\gcd$ 时候，我们将它放入序列对后面的数继续求解，那么，我们转换一下，直接将最小公倍数放入序列即可。

同余关系

同余

定义

​ 设整数 $m\ne0$。若 $m\mid(a-b)$，称 $m$ 为 模数（模），$a$ 同余于 $b$ 模 $m$，$b$ 是 $a$ 对模 $m$ 的 剩余。记作 $a\equiv b\pmod m$。
​

否则，$a$ 不同余于 $b$ 模 $m$，$b$ 不是 $a$ 对模 $m$ 的剩余。记作 $a\not\equiv b\pmod m$。

这样的等式，称为模 $m$ 的同余式，简称 同余式。

根据整除的性质，上述同余式也等价于 $a\equiv b\pmod{(-m)}$。

如果没有特别说明，模数总是正整数。

式中的 $b$ 是 $a$ 对模 $m$ 的剩余，这个概念与余数完全一致。通过限定 $b$ 的范围，相应的有 $a$ 对模 $m$ 的最小非负剩余、绝对最小剩余、最小正剩余。

同余的性质
  • 同余是 等价关系，即同余具有
    • 自反性：$a\equiv a\pmod m$。
    • 对称性：若 $a\equiv b\pmod m$，则 $b\equiv a\pmod m$。
    • 传递性：若 $a\equiv b\pmod m,b\equiv c\pmod m$，则 $a\equiv c\pmod m$。
  • 线性运算：若 $a,b,c,d\in\mathbf{Z},m\in\mathbf{N}^*,a\equiv b\pmod m,c\equiv d\pmod m$ 则有：
    • $a\pm c\equiv b\pm d\pmod m$。
    • $a\times c\equiv b\times d\pmod m$。
  • 设 $f(x)=\sum_{i=0}^n a_ix^i$ 和 $g(x)=\sum_{i=0}^n b_ix^i$ 是两个整系数多项式，$m\in\mathbf{N}^*$，且 $a_i\equiv b_i\pmod m,~0\leq i\leq n$，则对任意整数 $x$ 均有 $f(x)\equiv g(x)\pmod m$。进而若 $s\equiv t\pmod m$，则 $f(s)\equiv g(t)\pmod m$。
  • 若 $a,b\in\mathbf{Z},k,m\in\mathbf{N}^*,a\equiv b\pmod m$, 则 $ak\equiv bk\pmod{mk}$。
  • 若 $a,b\in\mathbf{Z},d,m\in\mathbf{N}^*,d\mid a,d\mid b,d\mid m$，则当 $a\equiv b\pmod m$ 成立时，有 $\dfrac{a}{d}\equiv\dfrac{b}{d}\left(\bmod;{\dfrac{m}{d}}\right)$。
  • 若 $a,b\in\mathbf{Z},d,m\in\mathbf{N}^*,d\mid m$，则当 $a\equiv b\pmod m$ 成立时，有 $a\equiv b\pmod d$。
  • 若 $a,b\in\mathbf{Z},d,m\in\mathbf{N}^*$，则当 $a\equiv b\pmod m$ 成立时，有 $(a,m)=(b,m)$。若 $d$ 能整除 $m$ 及 $a,b$ 中的一个，则 $d$ 必定能整除 $a,b$ 中的另一个。

乘法逆元

介绍模意义下乘法运算的逆元（Modular Multiplicative Inverse），并介绍如何使用扩展欧几里德算法（Extended Euclidean algorithm）求解乘法逆元。

定义

如果一个线性同余方程 $ax \equiv 1 \pmod b$，则 $x$ 称为 $a \bmod b$ 的逆元，记作 $a^{-1}$。

如何求逆元
扩展欧几里得法

设 $\gcd(a, n) = 1$ 根据最大公约数表示定理，有$as + tn = 1$等式两边同时模 $n$，得$as \equiv 1 \pmod{n}$

易知，模 $n$ 下 $a$ 的逆元是 $s$

一次同余方程

同余方程

​ 对正整数 $m$ 和一元整系数多项式 $f(x)=\sum_{i=0}^n a_ix^i$，其中未知数 $x\in\mathbf{Z}_m$，称形如
​
$$
f(x)\equiv 0\pmod m\tag{1}
$$

的方程为关于未知数 $x$ 的模 $m$ 的一元 同余方程（Congruence Equation）。

若 $a_n\not\equiv 0\pmod m$，则称上式为 $n$ 次同余方程。

类似可定义同余方程组。

关于一次同余方程与方程组的相关内容请参见 线性同余方程 与 中国剩余定理。

同余下的消去律

设$a,n \in {Z},n > 0$，如果$\gcd(a,n)=d$，有
$$
az \equiv az’ \pmod n \implies z \equiv z’ \pmod {n/d}
$$

一次同余方程有解的条件

若$\gcd(a,n)=d$，则$ax \equiv b \pmod n 有解 \iff d \mid b$

中国剩余定理

引入

「物不知数」问题：有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

即求满足以下条件的整数：除以 $3$ 余 $2$，除以 $5$ 余 $3$，除以 $7$ 余 $2$。

该问题最早见于《孙子算经》中，并有该问题的具体解法。宋朝数学家秦九韶于 1247 年《数书九章》卷一、二《大衍类》对「物不知数」问题做出了完整系统的解答。上面具体问题的解答口诀由明朝数学家程大位在《算法统宗》中给出：

三人同行七十希，五树梅花廿一支，七子团圆正半月，除百零五便得知。

$2\times 70+3\times 21+2\times 15=233=2\times 105+23$，故答案为 $23$。

定义

中国剩余定理 (Chinese Remainder Theorem, CRT) 可求解如下形式的一元线性同余方程组（其中 $n_1, n_2, \cdots, n_k$ 两两互质）：

$$
\begin{cases}
x &\equiv a_1 \pmod {n_1} \
x &\equiv a_2 \pmod {n_2} \
&\vdots \
x &\equiv a_k \pmod {n_k} \
\end{cases}
$$

上面的「物不知数」问题就是一元线性同余方程组的一个实例。

过程
  1. 计算所有模数的积 $n$；
  2. 对于第 $i$ 个方程：
    1. 计算 $m_i=\frac{n}{n_i}$；
    2. 计算 $m_i$ 在模 $n_i$ 意义下的 逆元 $m_i^{-1}$；
    3. 计算 $c_i=m_im_i^{-1}$（不要对 $n_i$ 取模）。
  3. 方程组在模 $n$ 意义下的唯一解为：$x=\sum_{i=1}^k a_ic_i \pmod n$。
证明

我们需要证明上面算法计算所得的 $x$ 对于任意 $i=1,2,\cdots,k$ 满足 $x\equiv a_i \pmod {n_i}$。

当 $i\neq j$ 时，有 $m_j \equiv 0 \pmod {n_i}$，故 $c_j \equiv m_j \equiv 0 \pmod {n_i}$。又有 $c_i \equiv m_i \cdot (m_i^{-1} \bmod {n_i}) \equiv 1 \pmod {n_i}$，所以我们有：

$$
\begin{aligned}
x&\equiv \sum_{j=1}^k a_jc_j &\pmod {n_i} \
&\equiv a_ic_i &\pmod {n_i} \
&\equiv a_i \cdot m_i \cdot (m^{-1}_i \bmod n_i) &\pmod {n_i} \
&\equiv a_i &\pmod {n_i}
\end{aligned}
$$

即对于任意 $i=1,2,\cdots,k$，上面算法得到的 $x$ 总是满足 $x\equiv a_i \pmod{n_i}$，即证明了解同余方程组的算法的正确性。

因为我们没有对输入的 $a_i$ 作特殊限制，所以任何一组输入 ${a_i}$ 都对应一个解 $x$。

另外，若 $x\neq y$，则总存在 $i$ 使得 $x$ 和 $y$ 在模 $n_i$ 下不同余。

故系数列表 ${a_i}$ 与解 $x$ 之间是一一映射关系，方程组总是有唯一解。

解释

下面演示 CRT 如何解「物不知数」问题。

  1. $n=3\times 5\times 7=105$；
  2. 三人同行 七十 希：$n_1=3, m_1=n/n_1=35, m_1^{-1}\equiv 2\pmod 3$，故 $c_1=35\times 2=70$；
  3. 五树梅花 廿一 支：$n_2=5, m_2=n/n_2=21, m_2^{-1}\equiv 1\pmod 5$，故 $c_2=21\times 1=21$；
  4. 七子团圆正 半月：$n_3=7, m_3=n/n_3=15, m_3^{-1}\equiv 1\pmod 7$，故 $c_3=15\times 1=15$；
  5. 所以方程组的唯一解为 $x\equiv 2\times 70+3\times 21+2\times 15\equiv 233\equiv 23 \pmod {105}$。（除 百零五 便得知）

欧拉函数

定义

欧拉函数（Euler’s totient function），即 $\varphi(n)$，表示的是小于等于 $n$ 和 $n$ 互质的数的个数。

比如说 $\varphi(1) = 1$。

当 $n$ 是质数的时候，显然有 $\varphi(n) = n - 1$。

性质

  • 欧拉函数是 积性函数。

    即对任意满足 $\gcd(a, b) = 1$ 的整数 $a,b$，有 $\varphi(ab) = \varphi(a)\varphi(b)$。

    特别地，当 $n$ 是奇数时 $\varphi(2n) = \varphi(n)$。

    证明参见 剩余系的复合。

  • $n = \sum_{d \mid n}{\varphi(d)}$。

  • 设两两互素的正整数$n_1,\cdots,n_m \in {N}$，并设$n = \prod_{i=1}^m \varphi(n_i)$，$\varphi(n) = \prod_{i=1}^m \varphi(n_i)$

  • $\varphi(p^k)=p^{k-1} \varphi(p)$

证明

利用 莫比乌斯反演 相关知识可以得出。

也可以这样考虑：如果 $\gcd(k, n) = d$，那么 $\gcd(\dfrac{k}{d},\dfrac{n}{d}) = 1, ( k < n )$。

如果我们设 $f(x)$ 表示 $\gcd(k, n) = x$ 的数的个数，那么 $n = \sum_{i = 1}^n{f(i)}$。

根据上面的证明，我们发现，$f(x) = \varphi(\dfrac{n}{x})$，从而 $n = \sum_{d \mid n}\varphi(\dfrac{n}{d})$。注意到约数 $d$ 和 $\dfrac{n}{d}$ 具有对称性，所以上式化为 $n = \sum_{d \mid n}\varphi(d)$。

  • 若 $n = p^k$，其中 $p$ 是质数，那么 $\varphi(n) = p^k - p^{k - 1}$。
    （根据定义可知）

  • 由唯一分解定理，设 $n = \prod_{i=1}^{s}p_i^{k_i}$，其中 $p_i$ 是质数，有 $\varphi(n) = n \times \prod_{i = 1}^s{\dfrac{p_i - 1}{p_i}}$。

    证明
    - 引理：设 $p$ 为任意质数，那么 $\varphi(p^k)=p^{k-1}\times(p-1)$。
    ​ 证明：显然对于从 1 到 $p^k$ 的所有数中，除了 $p^{k-1}$ 个 $p$ 的倍数以外其它数都与 $p^k$ 互素，故 $\varphi(p^k)=p^k-p^{k-1}=p^{k-1}\times(p-1)$，证毕。

    ​ 接下来我们证明 $\varphi(n) = n \times \prod_{i = 1}^s{\dfrac{p_i - 1}{p_i}}$。由唯一分解定理与 $\varphi(x)$ 函数的积性

    $$
    \begin{aligned}
    \varphi(n) &= \prod_{i=1}^{s} \varphi(p_i^{k_i}) \
    &= \prod_{i=1}^{s} (p_i-1)\times {p_i}^{k_i-1}\
    &=\prod_{i=1}^{s} {p_i}^{k_i} \times(1 - \frac{1}{p_i})\
    &=n \prod_{i=1}^{s} (1- \frac{1}{p_i})
    \end{aligned}
    $$

  • 对任意不全为 $0$ 的整数 $m,n$，$\varphi(mn)\varphi(\gcd(m,n))=\varphi(m)\varphi(n)\gcd(m,n)$。

    可由上一条直接计算得出。

举例

法一：
$$
\begin{aligned}
\varphi(30000) &= \varphi(3 \times 2^4 \times 5^4)\
&= \varphi(3) \times \varphi(2^4) \times \varphi(5^4) \
&= \varphi(3) \times 2^3\varphi(2) \times 5^3\varphi(5) \
&= 2 \times 2^3 \times 1 \times 5^3 \times 4 \
&= 8000
\end{aligned}
$$
法二：

30000 = 30 × 1000
30 = 2 × 3 × 5
1000 = 10 × 100 = 2 × 5 × 100 = 2 × 5 × 10 × 10 = 2 × 5 × 2 × 5 × 2 × 5 = 2³ × 5³
所以，30000 = 2³ × 3 × 5³ × 5 = 2³ × 3 × 5⁴

接下来用欧拉函数的公式来计算 φ(30000)。
$$
\varphi(n) = n \prod_{i=1}^{s} (1- \frac{1}{p_i})
$$
其中 p 是 n 的不同质因数。对于 30000，质因数是 2、3 和 5。代入公式：
$$
\begin{aligned}
\varphi(30000) &= 30000 \times (1-\frac{1}{2}) \times (1-\frac{1}{3}) \times (1-\frac{1}{5}) \
&= 30000 \times \frac{1}{2} \times \frac{2}{3} \times \frac{4}{5} \
&= 30000 \times \frac{4}{15} \
&= 8000
\end{aligned}
$$

欧拉定理 费马小定理

欧拉定理
定义

若 $\gcd(a, m) = 1$，则 $a^{\varphi(m)} \equiv 1 \pmod{m}$。

证明

实际上这个证明过程跟下文费马小定理的证明过程是非常相似的：构造一个与 $m$ 互质的数列，再进行操作。

设 $r_1, r_2, \cdots, r_{\varphi(m)}$ 为模 $m$ 意义下的一个简化剩余系，则 $ar_1, ar_2, \cdots, ar_{\varphi(m)}$ 也为模 $m$ 意义下的一个简化剩余系。所以 $r_1r_2 \cdots r_{\varphi(m)} \equiv ar_1 \cdot ar_2 \cdots ar_{\varphi(m)} \equiv a^{\varphi(m)}r_1r_2 \cdots r_{\varphi(m)} \pmod{m}$，可约去 $r_1r_2 \cdots r_{\varphi(m)}$，即得 $a^{\varphi(m)} \equiv 1 \pmod{m}$。

当 $m$ 为素数时，由于 $\varphi(m) = m - 1$，代入欧拉定理可立即得到费马小定理。

费马小定理
定义

若 $p$ 为素数，$\gcd(a, p) = 1$，则 $a^{p - 1} \equiv 1 \pmod{p}$。

另一个形式：对于任意整数 $a$，有 $a^p \equiv a \pmod{p}$。

证明

设一个质数为 $p$，我们取一个不为 $p$ 倍数的数 $a$。

构造一个序列：$A={1,2,3\dots,p-1}$，这个序列有着这样一个性质：

$$
\prod_{i=1}^{p-1}\space A_i\equiv\prod_{i=1}^{p-1} (A_i\times a) \pmod p
$$

证明：

$$
\because (A_i,p)=1,(A_i\times a,p)=1
$$

又因为每一个 $A_i\times a \pmod p$ 都是独一无二的，且 $A_i\times a \pmod p < p$

得证（每一个 $A_i\times a$ 都对应了一个 $A_i$）

设 $f=(p-1)!$, 则 $f\equiv a\times A_1\times a\times A_2\times a \times A_3 \dots \times A_{p-1} \pmod p$

$$
\begin{aligned}
a^{p-1}\times f &\equiv f \pmod p \
a^{p-1} &\equiv 1 \pmod p
\end{aligned}
$$

证毕。

也可用归纳法证明：

显然 $1^p\equiv 1\pmod p$，假设 $a^p\equiv a\pmod p$ 成立，那么通过二项式定理有

$$
(a+1)^p=a^p+\binom{p}{1}a^{p-1}+\binom{p}{2}a^{p-2}+\cdots +\binom{p}{p-1}a+1
$$

因为 $\binom{p}{k}=\frac{p(p-1)\cdots (p-k+1)}{k!}$ 对于 $1\leq k\leq p-1$ 成立，在模 $p$ 意义下 $\binom{p}{1}\equiv \binom{p}{2}\equiv \cdots \equiv \binom{p}{p-1}\equiv 0\pmod p$，那么 $(a+1)^p \equiv a^p +1\pmod p$，将 $a^p\equiv a\pmod p$ 带入得 $(a+1)^p\equiv a+1\pmod p$ 得证。