欧几里得算法证法一a可以表示成a = kb + r（a，b，k，r皆为正整数，且r不为0）假设d是a,b的一个公约数，记作d|a,d|b，即a和b都可以被d整除
而r = a - kb，两边同时除以d，r/d=a/d-kb/d，由等式右边可知m=r/d为整数，因此d|r因此d也是b,a mod b的公约数
因(a,b)和(b,a mod b)的公约数相等，则其最大公约数也相等，得证
以上内容由大学时代综合整理自互联网，实际情况请以官方资料为准。
