欧几里得算法和扩展欧几里得算法

欧几里得算法 在数学中，辗转相除法，又称欧几里得算法（英语：Euclidean algorithm），是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。 过程 欧几里得算法基于一个非常简单的原理：对于两个数a和b(a > b)， a和b的最大公约数与b和a - b的最大公约数相同。