如何通过辗转相除法求出任意两个正整数的最大公约数？

本文共计568个文字，预计阅读时间需要3分钟。

求最大公约数有两种方法：更相减损法，辗转相除法。两种方法原理相同，辗转相除法更简洁。1. 更相减损法：设有两个正整数a和b，且a>b，它们的最大公约数为d，则存在整数m和n，使得a=md，b=nd。设m1=md-nb，m2=nb-md，m3=md+nb，则a和b的最大公约数也是m1、m2、m3的最大公约数。2. 假设有两个数161和63，它们的最大公约数为x。则161和63都能被x整除，它们的差161-63也能被x整除。

求最大公约数有两种方法：更相减损法，辗转相除法

两种方法原理相同，辗转相除法更简洁

1.更相减损法

假设有两个数161和63，设它们的最大公约数为x

161和63都能被x整除，则它们的差161－63=98也能被x整除，所以求161和63的最大公约数变成求98和63的最大公约数，且98和63的最大公约数仍然是x。

98和63都能被x整除，则它们的差98－63=35也能被x整除,所以求98和63的最大公约数变成求63和35的最大公约数，且63和35的最大公约数仍然是x。

同理 63－35=28 求28和35的最大公约数

35－28=7 求28和7的最大公约数

28－7=21 求21和7的最大公约数

21－7=14 求14和7的最大公约数

14－7=7 求7和7的最大公约数，即x=7

直到两个数相同，最大公约数即为其本身。