简化剩余系

把完全剩余系中与 m 互素的挑出来（没有 0 了）

元素个数一共有 $φ (n)$ 个

a 和 m 互素，x 遍历模 m 的简化剩余系，则 $a x$ 也遍历模 m 的简化剩余系

这里没有 $a x + b$ 因为可能会导致不互素了，就不是简化剩余系了

x 遍历模 m 简化剩余系，y 遍历模 n 简化剩余系，m n 互素，则 $n x + m y$ 遍历模 $mn$ 的简化剩余系

(x, m) = 1 ⟹ (n x, m) = 1 ⟹ (n x + m y, m) = 1

同理

(n x + m y, n) = 1

两个等式和

(n x + m y, nm) = 1

在 $(n, m)$ 情况下可以互推

这里证明了欧拉函数的一个重要结论，和乘法同构

模 m 剩余类环中与 m 互素的剩余类的集合（简化剩余系）构成乘法群

互素就存在逆元了嘛和有限域的证明类似

推论：

(r, m) = 1 ⟺ \exists s [sr \equiv 1] (m o d m)

🪴 Cyril