09.欧拉函数

title: 09. 欧拉函数 tags: zk basic euler's totient function WTF zk教程第9讲：欧拉函数 给定一个整数 $n$，小于等于 $n$ 的正整数中有多少和 $n$ 互质的数呢？这一讲，我们将研究这个问题，知识点包括单元集和欧拉函数。 单元集 如果 $x \in \mathbb{Z}n$ 是可逆的（即存在乘法逆元），那么我们称 $x$ 为 $\mathbb{Z}n$ 的单元（unit）。 $\mathbb{Z}n$ 所有单元的组成的集合被称为单元集（Set of units），记为 $\mathbb{Z}n^$。 通过之前的学习，我们知道 $x \in \mathbb{Z}n$ 可逆的充要条件是 $x$ 与 $n$ 互质。因此 $\mathbb{Z}n^$ 中的元素就是 $[1, ..., n-1]$ 中与 $n$ 互质的正整数。在同余理论中，这个集合也被称为模 $N$ 的互质同余类。 举个几个例子： $\mathbb{Z}^2 = \{1\}$ $\mathbb{Z}^3 = \{1,2\}$ $\mathbb{Z}^5 = \{1, ...