- 上网查找什么是求两个数的最大公约数的欧几里得算法（辗转相除法），提交算法说明和网上链接。
①简要介绍
欧几里德算法又称辗转相除法，是指用于计算两个正整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。
欧几里德算法是用来求两个正整数最大公约数的算法。是由古希腊数学家欧几里德在其著作《The Elements》中最早描述了这种算法,所以被命名为欧几里德算法
②简要举例
假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里德算法，是这样进行的：
1997 / 615 = 3 (余 152)
615 / 152 = 4(余7)
152 / 7 = 21(余5)
7 / 5 = 1 (余2)
5 / 2 = 2 (余1)
2 / 1 = 2 (余0)
至此，最大公约数为1
以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 1997 和 615 的最大公约数 1。
③计算证明
a可以表示成a = kb + r（a，b，k，r皆为正整数，且r<b），则r = a mod b
假设d是a,b的一个公约数，记作d|a,d|b，即a和b都可以被d整除。
而r = a - kb，两边同时除以d，r/d=a/d-kb/d=m，由等式右边可知m为整数，因此d|r
因此d也是b,a mod b的公约数
假设d是b,a mod b的公约数, 则d|b,d|(a-k*b),k是一个整数。
进而d|a.因此d也是a,b的公约数
因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证。
参考资料:https://blog.csdn.net/mid_Faker/article/details/105378524
- 参考教材，用伪代码（英语或汉语）实现欧几里得算法（辗转相除法），提交伪代码。
写入数字1 读取数字1 写入数字2 读取数字2 如果数字1小于数字2 计算数字2除以数字1 当余数不为0时 计算上述除数除以余数 输出余数为0时的除数 否则 计算数字1除以数字2 当余数不为0时 计算上述除数除以余数 输出余数为0时的除数
- 选择几组数据，手动走一下伪代码，测试你写的伪代码是否正确，提交测试过程截图。
