更相减损法为什么可以求出两个数的最大公约数你?数学原理是什么?_百度...

发布网友发布时间：2024-03-08 19:24

共1个回答

热心网友时间：2024-03-16 18:57

举个例子，比如 98和63的最大公约数是7。 98-63=35 63-35=28 35-28=7 28-7=21 21-7=14 14-7=7 这样之所以能求出来，是因为假定98和63最大公约数是M 那么98=a*M，63=b*M，a b都是正整数。 98-63=35 所以这个差应该是（a-b）M 接下来M就可以看作是求63和35的公约数。那么M为什么又是63和35最大的公约数呢？假设有个数N是63和35最大的公约数而且N大于M，使得63=A*N,35=B*N。那么98=63+35=（A+B）N，也就是说98和63的最大公约数变成了N，这就与一开始矛盾了。于是这样循序渐进地减下去，M一直是2个数的最大公约数，最后可以得出M的值。还有另一种比较容易懂的理解方式。如果要求两个数X,Y的最大公约数T 把X,Y看成由若干个T组成的数。X:T T T T T T T T T…… Y:T T T T T…… 因为那么X-Y是啥意思呢？意思就是X比Y多的T构成的数，这样减的话这个差永远是整数个T，于是一直这样互相减下去，最后减出来肯定是只有一个T（遇到偶数除个2就行了），所以T是多少就浮出水面了。