在RSA密码体系中, 欧几里得算法是加密或解密运算的重要组成部分。它的基本运算过程就是解 $ax\equiv 1\pmod n$ 这种方程。整个解的过程是这样的，我们用一个例子来说明。 当 a = 1001 ，n = 3837 时，方程为 x * 1001 ≡ 1 (mod 3837)我们有3837 = 3 * 1001 + 8341001 = 1 * 834 + 167 834 = 4 * 167 + 166 167 = 1 * 166 + 1 所以 1 = 167 + (–1) * 166 = 167 - (834 - 4 * 167) = -1 * 834 + 5 * 167 = 5 *(1001 - 834) – 834 = 5 * 1001 + (-6) * 834 = 5 * 1001 - 6 * (3837 -3 * 1001) = -6 * 3837 + 23 * 1001 然后对等式两端同时模 3837 得 23 * 1001 ...