辗转相除求 gcd

$\gcd(a,b)=\gcd(b,\ a\bmod b)$
反复取余直到余数为 $0$，最后的非零余数即 $\gcd$。这是最古老也最高效的算法之一（复杂度 $O(\log)$）。

扩展欧几里得与裴蜀定理

裴蜀定理：存在整数 $x,y$ 使
$ax+by=\gcd(a,b)$
扩展欧几里得算法在求 gcd 的同时回代出这组系数。

模逆元

当 $\gcd(a,n)=1$ 时，$a$ 模 $n$ 可逆，逆元 $a^{-1}$ 满足 $a,a^{-1}\equiv1\pmod n$，由 $ax+ny=1$ 取 $x$ 即得。模逆是「模运算下的除法」。

例题

例　求 $17^{-1}\bmod 43$：扩展欧几里得得 $17\times38-43\times15=1$，故 $17^{-1}\equiv38\pmod{43}$（验证 $17\times38=646=15\times43+1$）。

应用

RSA 的私钥指数 $d$ 正是公钥 $e$ 模 $\varphi(n)$ 的逆元，由扩展欧几里得算出；模逆元也用于 ECC 点运算、CRT 合并与许多协议的「解密/还原」步骤。