想问一下辗除法的分析 - 数学吧

level 4

清欢寥寥¤ 楼主

就是求最大公约数的那个方法，找不到证明过程 [小乖]

2023年11月17日 12点11分 1

level 15

☞达瓦里希☜

辗转相除法，或曰Euclid算法

2023年11月17日 12点11分 2

清欢寥寥¤

有证明过程没，大佬，感觉这个方法好神奇，却不知道原理是啥 [委屈]

2023年11月18日 07点11分

☞达瓦里希☜

@清欢寥寥¤ 比方说你要找m和n的最大公约数gcd，那么即便m不能整除n，剩下的余数r也一定被任何他们的公约数整除，特别地，被gcd整除。因此gcd是m与r的公约数，容易验证gcd是m与r的最大公约数（否则...？）。

2023年11月18日 09点11分

☞达瓦里希☜

@清欢寥寥¤ 重复上边那个过程，（如果r不能整除m，则...）因为每次余数都要比上次的小，所以不能重复无限次。这个过程中出现的所有余数都能被gcd整除，所以结束的时候的那个余数被gcd整除。但是你反过来推会发现这个余数能整除之前的所有余数，所以他也是m与n的公约数。因此这个数只能是gcd。

2023年11月18日 09点11分

清欢寥寥¤

@☞达瓦里希☜ 为啥剩下的余数r一定能被任何他们的公约数整除啊，我想不明白

2023年11月18日 11点11分

level 15

Zerg234

你想想余数除法是什么意思
a除以b等于c余d的意思是，bc+d=a
那么a有约数k，b有约数k，显然d也有约数k
为什么这能得到最大公约数呢？
可以发现，每一次操作总能使得数字变小，最终总能变为0
然而，它们的公约数不会变
在变为0的前一步
比如a除以b等于c余0，那么a直接就是b的倍数了，最大公约数就是b

2023年11月18日 11点11分 3

level 4

清欢寥寥¤ 楼主

这个bc+d=a真的很精髓哎，我明白了，谢谢大佬 [不听]

2023年11月18日 11点11分 4