欧几里得算法：gcd(a,b) = gcd(b, r)，其中 r = a mod b
怎么理解这个算法是正确的
设 d1为 a和b的任意一个公约数，即d1|a，d1|b ，由于 r = a mod b，可以得到 d1|r
所以a和b的任何一个公约数同时也是b和r的公约数，即两者的公约数集合相同
所以gcd(a,b) = gcd(b,a%b)
欧几里得算法：gcd(a,b) = gcd(b, r)，其中 r = a mod b
怎么理解这个算法是正确的
设 d1为 a和b的任意一个公约数，即d1|a，d1|b ，由于 r = a mod b，可以得到 d1|r
所以a和b的任何一个公约数同时也是b和r的公约数，即两者的公约数集合相同
所以gcd(a,b) = gcd(b,a%b)