在书上看到求gcd（a，b）时用的是欧式方法（看了也没搞懂），我认为那种方法不方便，请问各位有没有更好的方法？

[ 本帖最后由 harold0 于 2008-7-23 21:14 编辑 ]

gsd？？什么啊

设a=cx，b=dx，其中gcd（a，b）=x，设d>c
那么在求gcd（a，b）时，先b-a=x（d-c），再a/（b-a）=c/（d-c），b/（b-a）=d/（b-a）
比较这两个数可得出d和c，便可求出x

[ 本帖最后由 harold0 于 2008-7-23 21:17 编辑 ]

抱歉打错了，已改
两个数a和b（都不是0）的最大公因数是整除他们的最大数，记作gcd（a，b）

为什么发这种和书本没太大关系的贴就没人想回呢？
数学可不止是书本上的东西

不方便么? 挺方便的啊

如果质因数分解比较容易, 那么标准分解后就可以看出了

比如
2100=2²·3·5²·7
1720=2³·5·43

那么 gcd(2100, 1720)=2²·5=20

求最大公因数小学不是就学过了么？欧式方法不一定，不过如果学过辗转相除法的话，其实就是欧式方法

求最大公因数小学不是就学过了么
呵呵，我在数上看到作者出了：gcd（1160718174，316258250）
这个...小学方法....不敢指望
我其实是想用其他方法，而不依靠前人

那你自己研究吧

不过估计不会比欧式方法简单了。想要新方法，最好也先了解前人的想法。

小学方法也没什么不敢指望的，其实就是欧式方法，不是么？

您看我的方法呢？

期望解一个二元方程是吧，你有具体做过么？

a=2100, b=1720
2100-1720=380

2100/380=c/(c-d)； 1720/380=d/(c-d)

即
2100(c-d)=380c
1720(c-d)=380d

(2100-380)c=2100d
1720c=(1720+380)d

很遗憾，解不出d和c

其实解不出是肯定的，回顾你的过程，推理一下，就知道你的两个方程完全是等价的，实际上没有两个独立方程，只有一个

如果真能找出更好的方法来，现在不知道有多少教科书就要改写了