欧几里得算法euclids algorithm

欧几里得算法又称辗转相除法，用于计算两个正整数a、b的最大公约数(greatest common divisor)。计算公式gcd(a,b) = gcd(b, a%b)。用于RSA加密。
证明过程：参见

欧几里得算法扩展

给定两个正整数a、b，在计算a、b最大公约数d的同时，也能计算出两个整数x，y使得ax+by=d，x，y不一定同时是正整数。
证明过程：参见

总结

以上是生活随笔为你收集整理的欧几里得算法以及推论的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。