【acm】【数论】欧拉定理与欧拉函数

发表于 2017-06-04 更新于 2022-07-21 分类于 acm_number 阅读次数：本文字数： 2.2k 阅读时长 ≈ 2 分钟

欧拉定理

定义

设\(m >= 2, (a, m) = 1\)。若\(\phi (m)\)表示小于\(m\)且与\(m\)互素的正整数的个数，则有

\[a^{\phi(m)} \equiv 1 \pmod m \tag{1.1}\]

tips

其中\(m\)不一定为素数。

若\(m\)为素数，则\(\phi(m) = m-1\), 上式变为费马小定理，即

\[a^{m-1} \equiv 1 \pmod m\]

证明

欧拉定理的证明与费马小定理的证明类似，需要以下引理。

引理1 若\((a, m ) = 1, r_1, r_2, \cdots, r_{\phi(m)}\)是小于\(m\)且与\(m\)互素的正整数，则

\[ ar_1, ar_2, \cdots, ar_{\phi(m)}\]

的最小剩余(mod m)是

\[r_1, r_2, \cdots, r_{\phi(m)}\]

的一排列。

tips

此引理的证明使用反证法即可。

下证欧拉定理。

由引理1可得

\[r_1* r_2*\cdots*r_{\phi(m)} \equiv (ar_1)*(ar_2)* \cdots*ar_{\phi(m)} \pmod m\]

即

\[r_1* r_2*\cdots*r_{\phi(m)} \equiv a^{\phi(m)}*(r_1* r_2*\cdots*r_{\phi(m)}) \pmod m\]

由于\(r_1, r_2, \cdots, r_{\phi(m)}\)每一个都与\(m\)互素，所以可消去，得

\[1 \equiv a^{\phi(m)} \pmod m\]

得证。

欧拉函数

定义

上面所提及的\(\phi(m)\)即为欧拉函数，表示小于m且与m互素的正整数的个数。

其有以下计算公式。

若n的素幂分解式为\(n = p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}\)，则有

\[\phi(n) = n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots (1-\frac{1}{p_k}) \tag{2.1}\]

另一种形式为

\[\phi(n) = p_1^{e_1-1}(p_1-1)p_2^{e_2-1}(p_2-1)\cdots p_k^{e_k-1}(p_k-1) \tag{2.2}\]

显然二者是等价的。

证明

欧拉函数可由由积性函数的性质得出。

证明所需要引理。

引理2 对一切正整数\(n\), 有

\[\phi(p^n) = p^{n-1}(p-1)\]

引理3 若\(r_1, r_2, \cdots, r_{\phi(m)}\)的最小剩余(mod m)是\(0, 1, 2, \cdots, m-1\)的一个排列，则

\[r_1, r_2, \cdots, r_{\phi(m)}\]

中恰有\(\phi(m)\)个元素与\(m\)互素。

引理3可证\(\phi(m)\)为积性函数，而积性函数具有以下性质。

若\(f\)是一个积性函数，\(n\)的素幂分解式为\(n = p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}\)，则

\[f(n) = f(p_1^{e_1})f(p_2^{e_2})\cdots f(p_k^{e_k})\]

再由引理2求得的素数幂项，即可求得正整数范围内的\(\phi(n)\)。

实现

给定整数\(n\)，求得其欧拉函数的一个实现如下。

// 求单个整数的欧拉函数
int Euler(int x) {
    int ans = x, m = (int)sqrt(x*1.0)+1;
    for(int i = 2; i < m; ++i) if(x%i == 0) {
        ans = ans / i * (i-1);
        while(x%i == 0) x /= i;
    }
    if(x > 1) ans = ans / x * (x-1);
    return ans;
}

//递推求[1, n]的欧拉函数值phi[i]
void PhiTable(int n, int* phi) {
    for(int i = 1; i <= n; ++i) phi[i] = i;
    for(int i = 2; i <= n; i += 2) phi[i] /= 2;
    for(int i = 3; i <= n; i += 2) if(phi[i] == i) {    //i是质数
        for(int j = i; j <= n; j += i) {
            phi[j] = phi[j] / i * (i-1);                //i是j的一个因子
        }
    }
}