欧拉函数（Euler's totient function），即 $\varphi(n)$，表示的是小于等于 $n$ 并且 $n$ 互质的正整数的个数。

形式化的讲，若集合 $A=\{ x\ | \gcd(x,n)=1,x \in [1,n] \}$，则 $\varphi(n)=\operatorname{card}(A)$，其中，$\operatorname{card}(A)$ 表示有限集 $A$ 中的元素个数（见人教 $2019$ 版数学必修一第 $15$ 页）。

举个例子，$\varphi(7)=6$，$\varphi(10)=4$。

循环 $x$ 从 $1$ 到 $n$，对于每一个 $x$，求 $\gcd(x,n)$ 是否为 $1$，$\varphi(n)$ 为 $\gcd(x,n)$ 是 $1$ 的次数。

$\gcd$ 函数的时间复杂度为 $\Theta(\log n)$，由于重复 $n$ 次，所以整体时间复杂度为 $\Theta(n \log n)$。

若

由唯一分解定理，有

证明如下：

代码如下：

ll phi(ll n){
	ll ans=n;
	for(register int i=2;i*i<=n;i++){
		if(!(n%i)){
			while(!(n%i))n/=i;
			ans/=i;
			ans*=(i-1);
		}
	}
	if(n>1){
		ans/=n,ans*=(n-1);
	}
	return ans;
}

时间复杂度 $\Theta(\sqrt{n})$。

欢迎大家在练习题目中提交。

费马小定理是欧拉定理的一个推论。

若 $p$ 为质数，$\gcd(a,p)=1$，且 $a,p \in \mathbb{Z}$，则

证明见 OI-Wiki。

当 $a,n \in \mathbb{Z}$，且 $\gcd(a,n)=1$ 时有：

所以

a^b \equiv a^{b \operatorname{mod} (n-1)}(\operatorname{mod} n)

a^b \equiv \left{ \begin{array}{rcl} a^{b \operatorname{mod} \varphi(n)}, & \gcd(a,n)=1,\ a^b & \gcd(a,n) \neq 1, &b<\varphi(n), \ a^{(b \operatorname{mod} \varphi(n))+\varphi(n)}& \gcd(a,n) \neq 1,&b \geq \varphi(n), \end{array}\right. \lparen \operatorname{mod} n \rparen.