这里写一下为什么下面式子 \(a\) 和 \(p\) 是互质的。
\[ax \equiv 1\ (mod \ p) \]其实就是逆元定义。
考虑如下的反证法：
分情况讨论
- 1.\(a\) 是 \(p\) 的倍数。
此时则有
\[kpx \equiv 1\ (mod \ p) \](其中 \(k\) 是一个参数，表示 \(a\) 是 \(p\) 的倍数)
显然，左边的模 \(p\) 等于 \(0\)。
- 2.\(a\) 是 \(p\) 的约数。
此时有
\[ax \equiv 1\ (mod \ ka) \]（\(k\) 同上面的）
考虑 \(ax\) 模 \(ka\) 什么时候等于 \(1\)。
发现这两个代数式都是 \(a\) 的倍数，而模可以堪称 \(ax\) 减去若干个 \(ka\) 所得的余数，发现差一定是 \(a\) 的倍数。
特殊的，如果 \(a=1\)，则原式不成立。
所以，逆元的充要条件是 \(a\) 与 \(p\) 互质。
标签：ka,数学,倍数,equiv,ax,随笔,互质,mod From： https://www.cnblogs.com/infinite2021/p/18312357