- gf25008 的博客
《GF日记》——《欧拉函数》-学习笔记
-
gf25008
LV 5
@
2025-8-4 17:32:55
欧拉函数
定义：
1.欧拉函数，表示的是小 于等于n和n互质的数的个数；
性质：
1.欧拉函数是积性函数：
1.积性函数的定义:
1.若函数满足，且对任意互质的都成立，则为积性函数；
2.若函数满足，且对任意的都成立，则为完全积性函数；
2.若，其中是质数，那么
3.对任意不全为的整数，
实现：
1.如果只要求一个数的欧拉函数值，那么直接根据定义质因数分解的同时求就好了，这个过程可以用分解质因数算法优化；
欧拉定理：
1.与欧拉函数紧密相关的一个定理就是欧拉定理，其描述如下：
1.若，则；
2.扩展欧拉定理：
1.扩展欧拉定理，用于处理一般的a和m的情形：
1.
{
，
(m)+(m)，b>=；
}
原文：
# 欧拉函数
## 定义：
1.欧拉函数$（Euler's totient function）$，表示的是小
于等于n和n互质的数的个数；
## 性质：
### 1.欧拉函数是积性函数：
#### 1.积性函数的定义:
1.若函数$f(n)$满足$f(1)=1$，且$f(xy)=f(a)f(y)$对任意互质的$x，y$$\sum$$N*$都成立，则$f(n)$为积性函数；
2.若函数$f(n)$满足$f(1)=1$，且$f(xy)=f(a)f(y)$对任意的$x，y$$\sum$$N*$都成立，则$f(n)$为完全积性函数；
#### 2.若$n=p^k$，其中$p$是质数，那么$\phi$$(n)=p^k-p^k-1；$
#### 3.对任意不全为$0$的整数$m，n$，$\phi$$(mn)$$\phi$$(gcd(m,n))=$$\phi$$(m)$$\phi$$(n)gcd(m,n)；$
## 实现：
1.如果只要求一个数的欧拉函数值，那么直接根据定义质因数分解的同时求就好了，这个过程可以用分解质因数算法优化；
## 欧拉定理：
### 1.与欧拉函数紧密相关的一个定理就是欧拉定理，其描述如下：
#### 1.若$\gcd(a,m)=1$，则$a ^{\phi(m)}≡1(\mod m)$；
### 2.扩展欧拉定理：
##### 1.扩展欧拉定理，用于处理一般的a和m的情形：
###### 1.$a^b≡$
{
$a^b$ $mod$$\phi$$(m)，$$gcd(a,m)=1；$
$a^b$， $gcd(a,m)!=1，b<$$\phi$$(m)$$(mod m)；$
$a^b$ $mod$ $\phi$(m)+$\phi$(m)$，$$gcd(a,m)!=1$，b>=$\phi$$(m)$；
}