一只蒟蒻的数论学习笔记（欧拉函数专题篇）

发表于 更新于 分类于

定义

1 到 $N$ 中与 $N$ 互质的数的个数被称为欧拉函数，记为 $\varphi(N)$。

函数式

$\varphi \left ( n \right ) = n \times \prod_{i=1}^{m} \left ( 1-\frac{1}{p_{i}} \right )$

性质

性质一

显然，如果 $N$ 为 质数，则 $\varphi(N)=N-1$

性质二

欧拉函数为 积性函数： 若 $\gcd(a , b ) = 1$，则 $\varphi(ab)=\varphi(a)\varphi(b)$。

积性函数 指对于所有互质的整数 $a$ 和 $b$ 有性质 $f( ab ) = f( a ) f( b )$ 的数论函数。

性质三

若 $n=p^{k}$，$p$ 为 质数，则 $\varphi(n)= n\left (1 - \frac{1}{p} \right )= \left ( p - 1 \right )p^{k-1}$。

证明
$n$ 个数中只有 $p$ 的倍数不与 $n$ 互质，而 $p$ 的倍数 $x$ 则有 $\dfrac{n}{p}=p^{k-1}$ 个，
因此 $\varphi(n)=n-\dfrac{n}{p}=n(1-\dfrac{1}{p})=p^{k}-p^{k-1}=(p-1)p^{k-1}$ 。

性质四

若 $N=p_{1}^{c_{1}}p_{2}^{c_{2}}…p_{m}^{c_{m}}$，则：
$\varphi(N)=N \times \dfrac{p_{1}-1}{p_{1}} \times \dfrac{p_{2}-1}{p_{2}} \times … \times \dfrac{p_{m}-1}{p_{m}}$
$\varphi(N)=N \times \left ( 1-\dfrac{1}{p_{1}} \right ) \times \left ( 1-\dfrac{1}{p_{2}} \right ) \times … \times \left ( 1-\dfrac{1}{p_{m}} \right )$

即：
${\small \varphi \left ( n \right ) = n \times \prod_{i=1}^{m} \left ( 1-\frac{1}{p_{i}} \right )} $

性质五

$\forall n > 1$，1 到 $n$ 中与 $n$ 互质的数的和为 $n \times \dfrac{\varphi(n)}{2}$。

证明
因为 $\gcd( n , x ) = \gcd( n , n-x )$，所以与 $n$ 不互质的数 $x$，$n - x$ 成对出现，平均值为 $\dfrac{n}{2}$ 。
因此，与 $n$ 互质的数的平均数也是 $\dfrac{n}{2}$，进而可得 1 到 $n$ 中所有与 $n$ 互质的数的和为 $\dfrac{n}{2} \varphi(n)$，化简得 $\dfrac{n\times \varphi(n)}{2}$。

性质六

如果 $a \mod p = 0$，其中 $p$ 为质数，则 $\varphi(a \times p)=p \times \varphi(a)$

证明
因为 $a \mod p = 0$，所以 $a \times p$ 与 $a$ 包含相同的质因子，只是其中有一个质因子 $p$ 的指数不同。
直接把 $\varphi(a \times p)$ 和 $\varphi(a)$ 按照函数式写出来，前者除去后者，商为 $p$ ，即 $\dfrac{\varphi(a \times p)}{\varphi(a)}=p$
所以 $\varphi(a \times p)=p \times \varphi(a)$

性质七

如果 $a \mod p \ne 0$， 其中 $p$ 为质数，则 $\varphi(ap)=(p-1)\varphi(a)$

证明
欧拉函数为积性函数。
所以 $\varphi(ap)=\varphi(a)\varphi(p)$，
又因为 $p$ 是质数，由 性质一 可得 $\varphi(p)=p-1$
所以 $\varphi(ap)=(p-1)\varphi(a)$

欧拉定理

若正整数 $a$，$n$ 互质，则 $a^{\varphi(n)} \equiv 1\pmod{n}$，其中 $\varphi(n)$ 为欧拉函数。

证明
设 1 到 $n$ 中所有与 $n$ 互质的数为 $a_{1},a_{2},…,a_{\varphi(n)}$
因为 $a$ 与 $n$ 互质，$a_{1}$ 与 $n$ 互质 （$a \equiv 1\pmod{n}$ 并且 $a_{1} \equiv 1\pmod{n}$
所以 $aa_{1}$ 与 n 互质 （$aa_{1} \equiv 1\pmod{n}$
同理 $aa_{1},aa_{2},…,aa_{\varphi(n)}$ 都与 $n$ 互质
所以 $aa_{1} \times aa_{2} \times … \times aa_{\varphi(n)}=a^{\varphi(n)} \times \left ( a_{1}a_{2}…a_{\varphi(n)}\right )$ 与 $n$ 互质
又因为 $a^{\varphi(n)} \times \left ( a_{1}a_{2}…a_{\varphi(n)}\right ) \equiv a_{1}a_{2}…a_{\varphi(n)} \pmod{n}$
所以 $a^{\varphi(n)} \equiv 1\pmod{n}$

费马小定理

为欧拉定理的一种情况。
若 $p$ 为质数，则对于任意整数 $a$，有 $a^{p} \equiv a \pmod{p}$，即 $a^{p-1} \equiv 1 \pmod{p}$

证明
是欧拉函数的一种情况
将 $\varphi(p)=p-1$ 带入即可

欧拉函数求法

求单个数的欧拉函数

只要在 分解质因数 时顺便将欧拉函数求出来就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int phi(int n) 
{
	int ans = n;
	for (int i = 2; i <= sqrt(n); i++) 
	{
		if (n % i == 0) 
		{
			ans = ans / i * (i - 1);
			while (n % i == 0)n /= i;
		}
	}
	if (n > 1)ans = ans / n * (n - 1);
	return ans;
}

线性求多个数的欧拉函数

在 线性筛 实现的时候顺便求欧拉函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void euler(int x) 
{   // primes数组存质数
	// phi数组存欧拉函数
	for(int i = 2; i <= x; i ++) 
	{
		if(!st[i]) 
		{
			primes[cn++] = i; 
			phi[i] = i - 1;
			//这句利用性质一
		}
		for(int j = 0; primes[j] <= x / i; j ++) 
		{ 
			st[ primes[j] * i ] = 1;
			phi[ primes[j] * i ] = phi[i] * (i % primes[j] ? primes[j] - 1 : primes[j]);
			// 这句利用了性质六、七
			if( i % primes[j] == 0 ) break;
		}
	}
}

OK，笔记完。
本蒟蒻刚学 OI ，如有错误请 D 我！！