欧几里得算法
定理
对于两个整数 $ a $ 和 $ b $ ，有： $ gcd(a,b) = gcd(b,a \mod b) $ 。
证明
令 $ d = gcd(a,b) $ ,且 $ a = q \times b + r $ 。
首先证明：若 $ a|d $ 且 $ b|d $ ，则 $ r|d $ 。
因为 $ a = q \times b + r $ ， 所以 $ r = a - q \times b $ 。由于 $ b|d $ ，所以 $ (q \times b)|d $ 。又因为 $ a|d $ ，由于整除的线性法则，所以 $ (a - q \times b)|d $ ，即 $ r|d $ 。
其次证明：若 $ r|d $ 且 $ b|d $ ，则 $ a|d $ 。
同理，因为 $ a = q \times b + r $ ，用类似上面的证明方法，可以得到 $ a|d $ 。
所以 $ a $ 和 $ b $ 的公因数和 $ b $ 和 $ a \mod b $ 完全相同。即 $ gcd(a,b) = gcd(b,a \mod b) $ 。
证毕。
扩展欧几里得算法
定理
对于两个整数 $ x $ 和 $ y $ ，存在两个整数 $ a $ 和 $ b $ ，使得 $ ax + by = gcd(a,b) $ 。
证明
由于上面证明的欧几里得算法，所以 $ ax + by = gcd(a,b) = gcd(b,a \mod b) $ 。
设有 $ x_0 $ 和 $ y_0 $ ，使得 $ bx_0 + (a \mod b)y_0 = gcd(b,a \mod b) $ 。
所以 $ ax + by = bx_0 + (a \mod b)y_0 $ \(^1\) 。
由于 $ a \mod b = a - \lfloor \frac{a}{b} \rfloor b $ ，所以可以把 1 式改写成： $ ax + by = ay_0 + b(x_0 - \lfloor \frac{a}{b} \rfloor y_0) $ 。
所以，方程的解可以表示为：
注意到，肯定有
所以我们便能得出 $ a = a_0 $ 且 $ b = b_0 $ 时的特解：
通过递归，我们便能得出最初的 $ x $ 与 $ y $ 的解。