逆元的三种核心求解算法：原理、证明与实现 前置定义与核心定理 模乘法逆元的严格定义 设 $m$ 为正整数，对于整数 $a$ ，若存在整数 $x$ 满足同余式： $a \cdot x \equiv 1 \pmod{m}$ 则称 $x$ 为 $a$ 在模 $m$ 下的乘法逆元，记作 $\mathrm{inv}(a) \pmod{m}$ 。 逆元存在性充…

欧几里得算法与扩展欧几里得算法：原理、证明及实现 1 欧几里得算法 1.1 定义与基本符号 设 $a, b$ 为不全为0的正整数， $\gcd(a, b)$ 表示 $a$ 与 $b$ 的最大公约数。 对 $a, b$ 做带余除法： $a = q\cdot b + r,\quad 0\le r < b$ 其中 $q = \lfloor \fra…