【数论基础】——欧拉定理

大家好，欢迎来到IT知识分享网。

1. 内容

欧拉定理的内容如下，其中 $\varphi (n)$ 是欧拉函数，不知道的可以学习这里

如果 $a,n$ 为正整数，且 $gcd(a,n)=1$, 则
$$a^{\varphi (n)}\equiv 1(\mathrm{mod}n)$$

2. 证明

这里的证明运用了大量的反证法与构造法

首先设集合 S = { x 1 , x 2 , ⋯   , x ϕ ( n ) } S = \{x_1, x_2, \cdots, x_{\phi(n)}\} S={
x1​,x2​,⋯,xϕ(n)​} (其实就是跟 $n$ 互质的所有整数)

然后再设 T = { a × x 1 % n , a × x 2 % n , ⋯   , a × x ϕ ( n ) % n } T = \{a\times x_1 \%n , a \times x_2 \% n, \cdots,a\times x_{\phi(n)} \% n\} T={
a×x1​%n,a×x2​%n,⋯,a×xϕ(n)​%n}

然后神奇的事情出现了： 我们发现如果 $T$ 集合中因为 $gcd(a,n)=1$ , 所有的 $gcd(x_i,n)=1$ 所以这其中的每一个数和 $n$也是互质的。（不知道为什么？这不就是扩展欧几里得 $gcd(a,b)=gcd(b,a\%b)$吗？$gcd(a\times x_i,n)=gcd(n,x_i\times n\%n)=1$）

更神奇的事情： 那么如果这些数是两两不同的，那么这 $\varphi (n)$ 个数就是所有与 $n$ 互质的正整数。这不就是 $S$ 集合吗?

证明（反证法）：
如果其中 $a\times x_i\%n=a\times x_j\%n=b$ 。
那么我们不妨假设 $a\times x_i=k_1\times n+b$, $a\times x_j=k_2\times n+b$。
那么 $a\times (x_i-x_j)=(k_1-k_2)\times n$ (两式相减）。
又因为 $gcd(a,b)=1$ 。
所以只可能 $x_i-x_j=n$ 。
但是 $x_i,x_j<n$ 显然不可能存在 $x_i-x_j=n$ 。
所以假设不成立，$T$ 集合的数两两不同的。

所以， 我们成功的推导出 $S$ 集合就是 $T$ 集合。

最后，
$$\begin{gathered} a^{\varphi (n)}\times x_1\times x_2\times \cdots \times x_{\varphi (n)}\equiv \\ (a\times x_1)\times (a\times x_2)\times \cdots \times (a\times x_{\varphi (n)})[T集合]\equiv \\ {x}_1\times x_2\times x_3\times \cdots \times x_{\varphi (n)}[S集合] \end{gathered}$$

最后的最后，所以由上式得

$$a^{\varphi (n)}\equiv 1(\mathrm{mod}n)$$

3. 应用

你知道 $7^{222}\%10=?$ 吗？试试用欧拉定理解决吧！

提示

1. $gcd(7,10)=1$
2. $\varphi (10)=4$
3. $7^{222}=(7^4{)}^{55}\times 7^2$