# 欧几里得算法

> 在数学中，辗转相除法，又称欧几里得算法（英语：Euclidean algorithm），是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。

- ID: m06119
- 分类: technical
- 领域: 算法

## 定义

辗转相除法。求两个大数的最大公约数，不需要分解质因数，只需反复用较小数去除较大数，取余数，直到余数为零。脚手架作用： 化繁为简的递归。面对两个庞大且矛盾的体系（如两家公司的合并、两套理论的冲突），寻找它们的最大公约数（共识）时，不要试图全面分析。不断地"取余"（剥离差异），剩下的那个不可再分的核心，就是连接双方的基础。

## 机制

gcd(a,b)=gcd(b, a mod b)，每步以余数替代较大数，规模递减直至余数为 0，末非零余数即最大公约数。

## 练习

1）取两数；2）大除小取余；3）以除数与余数迭代；4）余 0 时除数即结果。

## 脚手架用法

化繁为简的递归。面对两个庞大且矛盾的体系（如两家公司的合并、两套理论的冲突），寻找它们的最大公约数（共识）时，不要试图全面分析。不断地"取余"（剥离差异），剩下的那个不可再分的核心，就是连接双方的基础。

[阅读网页](https://thinkingmodels.site/entries/detail/m06119)