如何证明群(Zn\{0}, *)存在逆元？求解[a]_n的逆元方法

首先得明确一个核心前提：不是所有的$[a]_n$都存在乘法逆元！只有当$a$和$n$互质（也就是$\gcd(a,n)=1$）时，$[a]_n$在模$n$的剩余类环里才是可逆元素，才有对应的逆元。

你之前想把逆元写成$1/[a]_n$确实不太对，因为逆元必须是剩余类里的整数代表元，那具体怎么找呢？其实核心用的是扩展欧几里得算法：

当$\gcd(a,n)=1$时，根据贝祖定理，一定存在整数$x$和$y$，使得：

a*x + n*y = 1

把这个式子两边模$n$的话，$n*y$模$n$等于0，就得到：

a*x ≡ 1 (mod n)

这时候$x$模$n$的剩余类$[x]_n$就是$[a]_n$的乘法逆元啦！因为$[a]_n * [x]_n = [a*x]_n = [1]_n$，正好是单位元。

举个实际例子帮你理解：比如$n=15$，$a=7$，$\gcd(7,15)=1$，我们找$x$满足$7x ≡1 \text{ mod }15$。试算一下，$7*13=91$，$91 \text{ mod }15=1$，所以$[7]{15}$的逆元就是$[13]{15}$。

再说说你提到的“阶”的问题：元素的阶是指最小的正整数$k$，使得$[a]_n^k = [1]_n$，这和逆元是两个概念。逆元是直接和$[a]_n$相乘得到单位元的元素，而阶是通过幂次得到单位元的最小次数。当然，欧拉定理告诉我们，当$\gcd(a,n)=1$时，$[a]_n^{\phi(n)} = [1]_n$（$\phi(n)$是欧拉函数），但这不是找逆元的直接方法，扩展欧几里得算法才是更直接的逆元求解方式。

内容的提问来源于stack exchange，提问作者ashtonn