对于欧几里得算法和拓展欧几里得算法的讨论

背景：源于对于除法的失望，以及对于取模极高出现频率的恐惧。引入逆元这个神奇的货十分有必要。但为了介绍逆元的一种求法。先简要的介绍标题中的算法。 首先，是比较简单常见基础的欧几里得算法。简单的来说就是辗转相除法。用来求两个数的最大公约数。简单的表示一下： 证明：a可以表示成 假设d是a,b的一个公约数，则有, ，而的公约数 假设d 是 因此d也是的公约数 因此的公约数是一样的，，其最大公约数也必然相等，得证 附c++代码：

　int Gcd(int a, int b)　　{　　if(b == 0)　　return a;　　return Gcd(b, a % b);　　}

接下来我要给出拓展欧几里得算法的代码

int exGcd(int a, int b, int &x, int &y) { if(b == 0) { x = 1; y = 0; return a; } int r = exGcd(b, a % b, x, y); int t = x; x = y; y = t – a / b * y; return r; }

以上代码可以求出的一组解。 如果想要求则有整数解，否则没有。然后在求得的一组解上乘就可以得到多组整数解了。 然后。最后一句就是，求 a 关于 m 的乘法逆元x,就等价于解这个不定方程的最小整数解x,最后将x mod m即可。

重新开始吧!下次我会吸取教训，不让自己犯同样的错误的;