欧拉函数

$\phi (n)$ 统计模 $n$ 下可逆的剩余类：其中每个类都有一个乘法搭档，使乘积模 $n$ 等于 $1$。对于素数幂 $p^k$，失去可逆性的恰是 $p$ 的倍数。在 $0,1,\dots ,p^k-1$ 中，这样的数有 $p^{k-1}$ 个，所以单位数为 $p^k-p^{k-1}$。

若 $m,n$ 互素，中国剩余定理理路整数中国剩余定理Chinese remainder theorem for integers用最大公因数判定一般联立同余的相容性，并构造模最小公倍数唯一的解。把模 $mn$ 的单位对应到“一个模 $m$ 的单位、一个模 $n$ 的单位”。任意一对都能拼合，因此两边的单位数相乘。把 $n$ 分解为互素的素数幂，再使用上一段的计数，就得到乘积公式。

$\phi (12)=4$，对应单位类 $1,5,7,11$。计数区间既可取 $1\le a\le n$，也可取 $0\le a<n$：两种写法各选取每个剩余类一次。特别地，定义给出 $\phi (1)=1$。

对 $45=3^2\cdot 5$，容斥或乘积公式给出

也可以逐项做容斥：先从 $45$ 个剩余类中去掉 $15$ 个 $3$ 的倍数和 $9$ 个 $5$ 的倍数，再加回被重复去掉的 $3$ 个 $15$ 的倍数，得到 $45-15-9+3=24$。

乘法性需要互素条件。例如 $\phi (4)\phi (2)=2$，而 $\phi (8)=4$。另一方面，不同模数可以拥有相同数量的单位：

这说明 $\phi$ 不是单射，仅凭单位群大小无法唯一恢复模数。

单位群的阶为 $\phi (n)$，因此当 $gcd(a,n)=1$ 时，Lagrange 定理理路拉格朗日定理Lagrange's theorem有限群的阶等于子群阶与指数之积，因此子群阶必整除群阶。给出 Euler 定理 $a^{\phi (n)}\equiv 1(\mathrm{mod}n)$。素数模数下 $\phi (p)=p-1$，就恢复了Fermat 小定理理路费马小定理Fermat's little theorem素数 p 与不被 p 整除的整数 a 满足 a^(p−1)≡1 mod p。。这一指数关系也是 RSA 指数选择所使用的群论基础。

在阶为 $n$ 的循环群理路循环群Cyclic group能由一个元素的全部整数次幂生成的群。中，若 $g$ 是生成元，则 $g^a$ 仍为生成元恰好要求 $gcd(a,n)=1$，所以生成元共有 $\phi (n)$ 个。再按元素的阶分类：对每个 $d\mid n$，唯一的 $d$ 阶子群有 $\phi (d)$ 个生成元，把它们相加便得到 $\sum _{d\mid n}\phi (d)=n$。

同样的互素计数也出现在分数中。对 $n>1$，分母恰为 $n$、落在 $(0,1)$ 内的最简分数共有 $\phi (n)$ 个，因为分子需要与分母互素；这解释了 Euler 函数为何用于 Farey 序列统计。