## 欧拉定理(从理论到应用) 费马小定理和欧拉定理、威尔逊定理、中国剩余定理并称为初等数论四大定理。 ### 1、引入基本概念 #### 1.1 互质公约数只有$1$的两个 **整数**，称为互质。$a$与$b$互质，则写作 $(a,b)=1$。 #### 1.2 质因数质因数指能**整除给定整数的质数**，例如$6$的质因数为$2$和$3$。 #### 1.3 余数的基本性质 $(a+b)\%c = ((a\%c)+(b\%c)) \% c$ $(a-b)\%c = ((a\%c) - (b\%c)) \% c$ $(a*b)\%c = ((a\%c) * (b\%c)) \% c$ 注意：除法没有这个性质，需要用到逆元！ #### 1.4 同余给定一个正整数$m$，如果两个整数$a$和$b$满足$a-b$能够被$m$整除，那么就称整数$a$与$b$对模$m$同余，记作$a≡b(mod \ m)$。这玩意咋理解呢？我们可以想像一下生活中的例子，比如$1$号是星期一，那么$8$号也是星期一。因为一周有$7$天，$7$天一循环嘛。此时我们认为 $$1 \equiv 8 (mod \ 7)$$ 说的再直白些，就是从一个大数当中，扣去循环节的整数倍，得到的余数与小数是相等的。 ### 2、欧拉函数 #### 2.1 定义对正整数$n$，欧拉函数是小于$n$的正整数中与$n$互质的数的数目。 #### 2.2 欧拉函数通项公式 $φ(n)=n*(1-1/p_1)*(1-1/p_2)*(1-1/p_3)*(1-1/p_4)*……*(1-1/p_n)$ 其中,$p$为$n$的质因数，$n$是不为$0$的正整数，$φ(1)=1$，质数的$φ$为自己减$1$ 例如$φ(2)=1$ 1. 直接求 2. 筛法求还可以在素数筛的同时求欧拉函数,效率更高。这一块的内容，直接看我单独总结的欧拉函数章节，这里不再赘述。 ### 3、欧拉定理数学世界中最美妙的定理,也称费马-欧拉定理或欧拉函数定理。莱昂哈德·欧拉，瑞士数学家，极其牛$B$的大神，没有之一。 #### 3.1定理内容若 $a, n$为正整数，且$a,n$互质 ，则 $$\large a^{φ(n)}≡1(mod \ n)$$ 其中$\phi(n)$指欧拉函数值。 #### 3.2 证明 [参考文档](https://blog.csdn.net/ymzqwq/article/details/96269772) 设$X_1,X_2,X_3,...,X_{\phi(n)}$ 是$[1 \sim n)$里与$n$互质的数，容易发现他们 * **模$n$两两不同** * **余数都与$n$互质**。其实这个不证明也行，都是废话，$X_i \%n$还是$X_i$,$X_i$当然两两不同，模了之后的余数就是$X_i$自己本身，可不是还与$n$互质。然后我们发现$aX_1,aX_2,...,aX_{\phi(n)}$ 也有上面两个性质:(用到条件：$a,n$互质) * 模$n$ 两两不同 **反证法**：若$aX_i \equiv aX_j (mod \ n) \Leftrightarrow aX_i-aX_j \equiv 0 (mod \ n) \Leftrightarrow a(X_i-X_j) \equiv 0 (mod \ n)$ ,由于$gcd(a,n)=1$，所以$X_i-X_j$必然是$n$的倍数!而我们知道$X_i$,$X_j$都是比$n$小的，差不可能是$n$的倍数，出现矛盾，假设错误，不存在任意两个$aX_i \equiv aX_j (mod \ n)$,即$aX_1,aX_2,...,aX_{\phi(n)}$模$n$两两不同。 * 余数都与 $n$ 互质 $a$ 与 $n$ 互质，$X_i$ 与 $n$ 互质，所以 $aX_i$也与$n$互质有了这两个性质，我们就可以发现$aX_1,aX_2,aX_3,...,aX_{\phi(n)}$模$n$后一定是$\phi(n)$个不同的与$n$互质的数，那不就肯定是$X_1,X_2,X_3,...,X_{\phi(n)}$这个集合嘛。所以得到 $$X_1 \cdot X_2 \cdot X_3 \cdot ... \cdot X_{\phi(n)} \equiv aX_1 \cdot aX_2 \cdot aX_3 \cdot ... \cdot aX_{\phi(n)} (mod \ n)$$ $$\Leftrightarrow$$ $$a^{\phi(n)} \equiv 1 (mod \ n)$$ $\large QED$ 证毕~ #### 3.3 费马小定理若存在整数$a,p$，$a$为整数，$p$为质数，那么$a^{(p-1)}≡ 1(mod \ p)$。 费马小定理是欧拉定理的一种特殊情况 （当$n$为质数时$φ(n)$为$n-1$） #### 3.4 费马小定理应用见我整理的费马小定理章节。 #### 3.5 欧拉定理应用首先看一个基本的例子。令$a = 3，n = 5$，这两个数是互素的。比$5$小的正整数中与$5$互素的数有$1、2、3$和$4$，所以$φ(5)=4$。计算:$a^{φ(n)} = 3^4 =81$，而$81= 80 + 1 \equiv 1 （mod \ 5）$。与定理结果相符。这个定理可以用来简化幂的模运算。比如计算$7^{222}$的个位数，实际是求$7^{222}$被$10$除的余数。$7$和$10$**互素**，且比$10$小的正整数中与$10$互素的数有$1,3,7,9$,$φ(10)=4$。由欧拉定理知$7^4 \equiv 1(mod \ 10)$。所以$7^{222}=7^{4*55}*7^2 \equiv 1^{55}*7^2 \equiv 49 \equiv 9 (mod \ 10)$。 #### 3.6 推论:最小正整数解的性质满足欧拉定理的最小正整数 $x$一定是$φ(c)$的约数，即 $x|φ(c)$,如果想找到最小正整数$x$,可以枚举$\phi(c)$的所有约数即可。 #### 3.7 推论证明反证法：假设该最小正整数 $x$ 不是 $φ(c)$ 的约数则$\displaystyle \large \phi(c)=qx+r \ \ \ \ \ (0