欧拉函数与欧拉定理

欧拉函数

\(\varphi(n) \ or \ \phi(n)\)

表示小于n的正整数与n互质的数的个数.

性质:

当n为质数时 \(\varphi(n)=n-1\)

当n为奇数时 \(\varphi(2n) = \varphi(n)\)

证明：

\(\because\)欧拉函数为积性函数.

\(\therefore \varphi(2n) = \varphi(2) \ast \varphi(n)\)

\(\because \varphi(2)=1\)

\(\therefore \varphi(2n) = \varphi(n)\)

欧拉函数是一个积性函数

若\(gcd(a, b) = 1\) 则 \(\varphi (a \ b) = \varphi(a) \ \varphi(b)\)

欧拉函数的积性证明.

条件是m与n互质

可以得到\(\phi(m \ n) = \phi(m) \ast \phi(n)\)

\(m = p_1^{a_1}p_2^{a_2}...p_k^{a_k}\)

\(\phi (m) = m(1- \frac {1}{p_1})(1- \frac {1}{p_2})...(1- \frac {1}{p_k})\)

\(n = p_1'^{a_1'}p_2'^{a_2'}...p_k'^{a_k'}\)

\(\phi(n) = n(1- \frac {1}{p_1'})(1- \frac {1}{p_2'})...(1- \frac {1}{p_k'})\)

\(\because m与n互质\)

\(\therefore p_1,p_2...p_k与p_1'p_2'...p_k'\)两两互不相同

\(\therefore \phi(mn) = mn(1- \frac {1}{p_1})(1- \frac {1}{p_2})...(1- \frac {1}{p_k})(1- \frac {1}{p_1'})(1- \frac {1}{p_2'})...(1- \frac {1}{p_k'})\)

\(\therefore \phi(mn) = \phi(m) \ast \phi(n)\)

欧拉函数通项公式

\(\varphi (n)= n (1 - \frac {1} {p_1})(1 - \frac {1} {p_2})(1 - \frac {1} {p_3})...(1 - \frac {1} {p_k})\)

若\(n = p ^ k ,p\)为质数,则\(\varphi (p^k) = p ^k - p ^{k - 1}\)

当一个数不包含质因子\(p\)时就能与\(n\)互质，

小于等于\(n\)的数中包含质因子\(p\)的只有\(p^{k-1}\) 个，他们是:

\(p, 2*p, 3* p, ...,p ^{k - 1} ∗p\)，把他们去除即可.

由唯一分解定理可得: \(n = p_1 ^{a_1} p_2 ^{a_2}p_3 ^{a_3}...p_k ^{a_k}\)

则 \(\varphi (n) = \varphi(p_1^{a_1})\varphi(p_2^{a_2})\varphi(p_3^{a_3})...\varphi(p_k^{a_k})\)

根据上述\(\varphi (p^k) = p ^k - p ^{k - 1}\)可得:

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

则 \(\varphi (n) = \varphi(p_1^{a_1})\varphi(p_2^{a_2})\varphi(p_3^{a_3})...\varphi(p_k^{a_k})\)可化为

\(\ \ \ \ \varphi (n) = p_1 ^{a_1}(1 - \frac {1} {p_1}) p_2 ^{a_2}(1 - \frac {1} {p_2})p_3 ^{a_3}(1 - \frac {1} {p_3})...p_k ^{a_k}(1 - \frac {1} {p_k})\)

\(\ \ \ \ \ \ \ \ \ \ \ = n (1 - \frac {1} {p_1})(1 - \frac {1} {p_2})(1 - \frac {1} {p_3})...(1 - \frac {1} {p_k})\)

欧拉定理:

当\(a\) 与 \(p\)互质的时候则有 \(a^{\varphi(p)} \equiv 1 \ (mod \ p)\)

证明

设A= \(\{x_1, x_2,x_3...x_{\phi(n)}\}\)为1—n中与n互质的数的集合.

则他们模n两两不相同，且余数与n互质

下面我们来证明B=\(\{ax_1, ax_2,ax_3...ax_{\phi(n)}\}\)也有这个性质

mod n 两两互不相同 （反证法）：

假设\(i != j\), \(x_i, x_j \in B\)那么就有\(ax_i \equiv ax_j (mod \ n)\)

那么就有\(ax_I - ax_J \equiv 0 (mod \ n)\)

因为\(x_i - x_J\) 与n互质，所以不会有这样的解，得证。

余数都与\(n\)互质：因为\(a\)与\(n\)互质，\(x_i\)与\(n\)互质，

所以\(ax_i\)也与\(n\)互质，\(ax_i\)模\(n\)后也与\(n\)互质。

\(\displaystyle \prod_{i = 1}^{\varphi(n)}ax_i \equiv \prod_{i=1}^{\varphi(n)}x_i (mod \ n)\)

\(\displaystyle a^{\varphi(n)} \prod_{i = 1}^{\varphi(n)}x_i \equiv \prod_{i=1}^{\varphi(n)}x_i (mod \ n)\)

\(\therefore a^{\varphi(n)} \equiv 0 (mod \ n)\)

特别的，当n为质数的时候\(\varphi(n) = n - 1\)

那么式子就变成了\(a^{n-1} \equiv 0 (mod \ n)\)

这就是费马小定理，可以用来求逆元.

欧拉定理的应用

求 \(a^b \ mod \ m\) 时，用欧拉定理缩小指数\(b\)

例题：求 \(7^{222} \ mod \ 10\)

分析：\(gcd(7,10) = 1\), 故 \(7^{φ(10)} = 7^5 ≡ 1 \ (mod \ 10)\)

所以 \(7^{222} ≡ 7^{222 \ mod \ 5} = 7^2 = 49 ≡ 9 \ (mod \ 10)\)

即 \(7^{222} \ mod \ 10 = 9\)

欧拉定理的拓展

定理：\(a^{2φ(n)} ≡ a^{φ(n)} \ (mod \ n)\)

首先我们提出一个引理：

引理一：设 \(p\) 为 \(n\) 的一个质因子，\(k\) 为 \(p\) 的次数；

则有 \(φ(n) ≥ k\) 成立。

引理的证明：

设 \(n = p^k ·t\)；则 \(φ(n) = φ(p^k ) \ φ(t) ≥ φ(p^k ) ≥ k\)

设 \(n = n_1 n_2\) , 其中 \(n_1 = (a^∞ ,n)\)

则有 \((a,n_2 ) = (n_1 ,n_2 ) = 1\)

由引理一可得 \(n_1 \mid a^{φ(n)}\) ，

因此 \(a^{φ(n)} ≡ a^{2φ(n)} ≡ 0 \ (mod \ n_1 )...(1)\)

又由\((n_1 ,n_2 ) = 1\) 得 \(φ(n) = φ(n_1 )φ(n_2 )\),

由欧拉定理 \(a^{φ(n)} ≡ a^{2φ(n)} ≡ 1 \ (mod \ n_2 )...(2)\)

中国剩余定理合并 \(1 \ 2\) 两式得证。

推论：当 \(b ≥ φ(n)\) 时，\(a^b ≡ a^{b \ mod \ φ(n)+φ(n)} \ (mod \ n)\)