欧拉函数相关概念

article/2025/11/10 18:58:52

一、欧拉函数

给定正整数n，欧拉函数φ(n)=不大于n且和n互质的正整数的个数(包括1)。
φ(1)=1
$\varphi \left( n \right) =\varSigma_{i=1}^{n}\left[ gcd\left( i,n \right) ==1 \right]$

完全余数集合: Zn={ 不大于n 且和n 互质的数} |Zn| ＝φ(n)

性质

(1)p为素数，则 φ( p)=p -1

质数与小于它的每一个，都构成互关系。质数与小于它的每一个，都构成互关系。

(2)p为素数，正整数 $n=p^k$ ，则 $\varphi \left( n \right) =p^k-p^{k-1}$ 或者写作 $\varphi \left( n \right) =p^{k-1}\left(p-1 \right) =p^k\left( 1-\frac{1}{p} \right)$

证明：

小于 $p^k$ 的正整数个数为 $p^k-1$ 个，其中与 $p^k$ 不互质的正整数有{p,2p,3p,4p,…, $p^{k-1}-1)p$ },共计 $p^{k-1}-1$ 个

所以 $\varphi \left( n \right) =p^k-1-\left( p^{k-1}-1\right) =p^k-p^{k-1}$

（3）两个素数 p,q ,n=p * q，则 φ(n) =( p-1) * ( q-1)

证明：

Zn={1,2,3,…,n-1}-{p,2p,3p,…,(q-1)p}-{q,2q,3q,…,(p-1)q}

φ(n)=(n-1)-(q-1)-(p-1)
=(p * q-1)-(p-1)-(q-1)
=(p * q-p)-(q-1)
=p(q-1)-(q-1)
=(p-1)(q-1)

在这里插入图片描述

(4)当b时质数,a%b=0,则φ(ab)=φ(a)b

证明：

设 $a=kb^n$ 且gcd(k,b)=1，则 $φ(a)=φ(k)φ(b^n)$ ， $φ(k)=\frac{φ(a)}{φ(b^n)}$

$φ(ab)=φ(kb^{n+1})=φ(k)φ(b^{n+1})=\frac{φ(a)}{φ(b^n)}φ(b^{n+1})=φ(a)(\frac{φ(b^{n+1})}{φ(b^n)})=φ(a)b$

$φ(b^{n+!})=b^{n+1}-b^n,φ(b^n)=b^n-b^{n-1}$

(5)任意正整数n： $n=p^{a_1}_1p^{a_2}_2...p^{a_m}_m$ ( $p_i$ 为素数)， $φ(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_m})$

证明：

$φ(n)=φ(p^{a_1}_1)φ(p^{a_2}_2)...φ(p^{a_m}_m)$

$=(p^{a_1}_1p^{a_2}_2...p^{a_m}_m)(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_m})$ (由性质(2)知）

$=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_m})$ (被称为欧拉函数计算公式)

如何进一步理解欧拉函数计算公式？

在这里插入图片描述

(6)欧拉函数递推式：可用于线性求1~n所有数的欧拉函数

给定质数p，满足p|x,

若p²|x不成立，则 $φ(x)=φ(\frac{x}{p})*(p-1)$

若p²|x成立，则 $φ(x)=φ(\frac{x}{p})*p$

欧拉函数打表：

int primes[N], euler[N], cnt;
bool st[N];
void get_eulers(int n)
{euler[1] = 1;for (int i=2; i <= n; i++ ){if ( !st[i] ){primes[cnt++] = i;euler[i] = i-1;}for ( int j=0; primes[ j] <= n/i; j++ ){st[ primes[ j]*i ] = true;if ( i % primes[ j] == 0 ) {euler[ i*primes[ j] ] = euler[i] * primes[ j];break;}euler[ i*primes[ j] ] = euler[i] * ( primes[j]-1 );}}
}

(7)整数n 等于n的所有约数(包括1和n)的欧拉函数之和，即 $n=\varSigma_{d|n}\varphi \left( d \right)$

在这里插入图片描述

(8)给定整数n，所有小于n且与n互质的数的和是 $n∗\frac{φ(n)}{2}$

小于n的与n互质数i 和n-i 总是成对出现，且它们的和是n；

小于n的且与n互质数的个数是φ(n)。
所以， $\varSigma _{i=1}^{n-1}i\left[ gcd\left( i,n\right) ==1 \right] =n*\varphi \left( n \right) /2$ ，还需分析i=n-i的情况 (即n为偶数情况)

(1)如果n是奇数，i≠n-i

(2)如果n是大于2的偶数，gcd(n,n/2)≠1

(3)如果n是2， $\frac{φ(n)}{2}=2*\frac{1}{2}=1$

`性质：若 gcd(n,i)=1，则 gcd(n,n-i)=1(1≤i≤n)`

反证法：

如果存在k≠1 使gcd(n,n-i)=k，那么(n-i)%k=0，n%k=0，n=k * j

→ (k * j-i)%k=0 → k * j%k-i%k=0 → i%k=0

因为k是n的因子， i%k=0 → gcd(n,i)=k，与原命题矛盾。

在这里插入图片描述

二、欧拉定理

1.欧拉定理

正整数a和n互质，有 $a^{φ(n)}≡1\ mod\ n$

证明：

1.令Zn={ $x_1,x_2,...,x_{φ(n)}$ }为 φ(n)个<n且与n互质的数 $x_i$ ,

构造S={ $ax_1$ %n , $ax_2$ %2 , … $ax_{φ(n)}$ %n}

即要证：Zn=S

（1）a与n互质且 $x_i$ 与n互质 → $ax_i$ 与n互质 → $ax_i\ mod\ n∈Zn$

（2）若i≠j，则 $x_i≠x_j$ → $ax_i$ %n ≠ $ax_j$ %n (否则由模运算消去律， $x_i=x_j$ )

2.证： $a^{φ(n)}x_1x_2...x_{φ(n)}\ mod\ n≡(ax_1)(ax_2)...(ax_{φ(n)}\ mod\ n)$

$ax_1\ mod\ n)(ax_2\ mod\ n)...(ax_{φ(n)}\ mod\ n)≡x_1x_2...x_{φ(n)}\ mod\ n$

所以有： $a^{φ(n)}x_1x_2...x_{φ(n)}≡x_1x_2...x_{φ(n)}\ mod\ n$

因为 $x_i$ （1≤i≤φ(n) ）与n互质，所以 $a^{φ(n)}≡1\ mod\ n$ （消去律）