问题
求x,y的最大公约数
定理
$\gcd(x, y)$=$\gcd(y, $x%y$)$
证明
设x=$ay+b$，
则b = $x-ay$，b=x%y。
再设d，有$x \equiv y \equiv 0 \pmod{d}$
则$x-ay \equiv 0 \pmod{d}$
则$b \equiv 0 \pmod{d}$
$x \equiv y \equiv $x%y$ \equiv 0 \pmod{d}$
又因为对于，都满足以上性质
所以$\gcd(x, y)$=$\gcd(y, $x%y$)$
标签：浅谈,pmod,gcd,欧几里得,x%,ay,朴素,equiv From： https://www.cnblogs.com/cdx1221/p/17365018.html