欧几里德算法与拓展欧几里德算法略解
欧几里德算法/辗转相除法
原理和证明
扩展欧几里德算法
求解不定方程的方法
求解线性同余方程的方法
欧几里德算法(Euclidean algorithm)又叫做辗转相除法,用于求最大公约数.这个算法已经十分常见了.扩展欧几里德算法(Extended Euclidean algorithm)是欧几里德算法的扩展(废话......),这个算法在解不定方程的时候十分常见.
本文中 (a,b) 或者 gcd(a,b) 表示 a,b 的最大公约数; a|b 表示 a 整除 b.
本文隶属⌈ 数论学习系列 ⌋.
在数学中,辗转相除法,又称欧几里得算法(英语:Euclidean algorithm),是