逆元补充

· · 个人记录

这是对 初等数论学习笔记 中逆元的补充。

逆元其实包括加法逆元和乘法逆元，就像平常的运算中，减法是加法的逆运算，除法是乘法的逆运算一样。

------------ 证明 $a$ 在模 $p$ 意义下当 $\gcd(a,p) \ne 1$ 时 $a$ 没有乘法逆元。 设 $n=\gcd(a,p)$ 则 $n \ne 1$ 且 $1\le \dfrac{p}{n} < p$，$a$ 的乘法逆元为 $a^{-1}$。 那么 $a \times \dfrac{p}{n}$ 一定是 $p$ 的倍数。（$a \times \dfrac{p}{n}$ 就相当于 $\operatorname{lcm}(a,p)$） 则 $a \times \dfrac{p}{n} \equiv 0 \pmod p

等式两边同时乘上 a 的乘法逆元 a^{-1}，得 a^{-1} \times a \times \dfrac{p}{n} \equiv 0 \times a^{-1} \pmod p

化简，得 \dfrac{p}{n} \equiv 0 \pmod p

\because 1\le \dfrac{p}{n} < p \therefore \dfrac{p}{n} \not\equiv 0 \pmod p

前后矛盾。