5.5 KiB
欧拉定理(从理论到应用)
费马小定理和欧拉定理、威尔逊定理、中国剩余定理并称为初等数论四大定理。
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
- 直接求
- 筛法求 还可以在素数筛的同时求欧拉函数,效率更高。 这一块的内容，直接看我单独总结的欧拉函数章节，这里不再赘述。
3、欧拉定理
数学世界中最美妙的定理,也称费马-欧拉定理或欧拉函数定理。莱昂哈德·欧拉，瑞士数学家，极其牛B的大神，没有之一。
3.1定理内容
若 a, n为正整数，且a,n互质 ，则 \large a^{φ(n)}≡1(mod \ n)
其中\phi(n)指欧拉函数值。
3.2 证明
设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)\Leftrightarrowa^{\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<r<x)
又 $\displaystyle \large \left{\begin{matrix} 10^x \equiv 1 (mod \ c) \Rightarrow 10^{qx} \equiv 1 (mod \ \ c ) \ \ ①\ 10^{\phi(c)} \equiv 1 (mod \ \ c ) \Rightarrow 10^{qx+r} \equiv 1 (mod \ \ c ) \ \ ② \end{matrix}\right. $
由2式除以1式得\large 10^r \equiv 1 (mod \ \ c ) \ \ \ \ \ (0<r<x)
故存在比 x 更小的正整数满足该式子，矛盾了，因此得证。