引用网址 https://www.cnblogs.com/jason2003/p/9797750.html
这个说的挺易懂，如下是原文，留个笔记
我们把证明分为两步骤： 1、证明gcd(a,b)是b,a%b的一个公约数 2、证明这个公约数是最大的。 1、我们设gcd(a,b)=d，再令a=k1*d,b=k2*d. 我们再设，a=k*b+c（也就是a除以b商k余c），那么c就是余数，也就是a%b. 讲上面那个式子移项，得到c=a-k*b，然后再把a=k1*d,b=k2*d，这两个式子里的a、b带入式子，得到: c=k1*d-k*k2*d,在提取公因数d，得到c=(k1-k*k2)*d.这样就说明，c，也就是a%b有d这个约数，因为开始我们设b也有d这个约数，所以gcd(a,b)是b，a%b的一个公约数。 2、现在知道了它是一个公约数，那么怎么证它是最大的？（其实感性分析，a%b都变小了，公约数不可能更大呀！） 但是~~术~~ 数学是一门严谨的学科，我们要严谨证明。我们知道，c（a%b）=（k1-k*k2）*d,b=k2*d，我们只需要证明k1-k*k2、k2互质就好了。 这里可以用到反证法：我们假设k1-k*k2=q*t,k2=p*t,并且t>1（也就是那两个不互质）。 我们将前面那个式子移项，得到k1=q*t+k*k2,再把这个k1代到最开始的a=k1*d，得到a=（q*t+k*k2）*d，再利用乘法分配律，得到： a=q*t*d+k*k2*d，我们这时发现，k2*d不就是最开始的b吗？，将其带入，得到：a=q*t*d+b*d. 这时，我们再把k2=p*t代入开始的b=k2*d,得到b=p*t*d，再把这个式子代到a=q*t*d+b*d.得到了：a=q*t*d+p*t*d.提取公因数：a=(q+p)*t*d 现在，再和b=p*t*d比较，发现他们的最大公因数变成了t*d和开始矛盾，所以假设不成立，反证成功！过程图可参考，还有动图非常直观
https://www.sohu.com/a/314655845_250298
欧几里德算法计算过程： a%b = c b%c = d c%d = e … g%h =0
h 即为最大公约数
a和b的余数 a %b 即 a%b = a - k * b 如果a%b （即c）可以被b整除，那么，它肯定也可以被 a-c （即a-a%b ）整除 ，如果不能整除则继续
依次类推： 如果b%c （即 d）可以被c整除，那么，它肯定也可以被 b-d （即b-b%c ）整除 ，如果不能整除则继续。
余数为0时即为刚好整除。（至少mod1的时候可以是0）
