欧几里得定理简述如下：
有非负整数：p,q,r,n,k，如果q和p的最大公约数是k，让：
p = n1 * k , q = n2 * k, p = n * q + r 那么：q 和 r 的最大公约数也是 k。简单来说用c语言求三个数的最大公约数，如果 p = n * q + r ，那么 p 和 q 的最大公约数就是 q 和 r 的最大公约数。
先从数学的角度证明定理：
由于 p = n1 * k , q = n2 * k , p = n * q + r 所以 p – n * q = r, 即：
r = n1 * k – n * n2 * k ，而 k 是 q = n1 * k 和 q = n2 * k 的最大公约数，所以：n1 和 n2 除了 1 之外没有其他公约数用c语言求三个数的最大公约数，所以 k是r = n1 * k – n * n2 * k和q = n2 * k的最大公约数，定理得到证明。
附上用Java实现的欧几里得算法求最大公约数的代码：
Java实现蛮力求最大公约数（Greatest common divisor）的代码：
以上两种方法都可以求最大公约数，欧几里得定理的递归实现很简单
常见问题FAQ
- 免费下载或者VIP会员专享资源能否直接商用？
- 本站所有资源版权均属于原作者所有，这里所提供资源均只能用于参考学习用，请勿直接商用。若由于商用引起版权纠纷，一切责任均由使用者承担。更多说明请参考 VIP介绍。
- 提示下载完但解压或打开不了？
- 找不到素材资源介绍文章里的示例图片？
- 欧资源网
