\(a\)を\(b\)で割った商を\(q\)とすると、
\(a=qb+r\)
と表される。

\(\gcd(a,b)\leq\gcd(b,r)\)の証明

\(a\)と\(b\)の公約数を\(g\)とすると\(a=ga'\)、\(b=gb'\)となるので、\(r=a-qb=g(a'-qb')\)となり、\(g\)は\(r\)の約数になる。これより、\(a\)と\(b\)の公約数ならば\(b\)と\(r\)の公約数であるので\(\gcd(a,b)\leq\gcd(b,r)\)となる。

\(\gcd(a,b)\geq\gcd(b,r)\)の証明

\(b\)と\(r\)の公約数を\(h\)とすると\(b=hb'\)、\(r=hr'\)となるので、\(a=qb+r=h(qb'+r')\)となり、\(h\)は\(r\)の約数になる。これより、\(b\)と\(r\)の公約数ならば\(a\)と\(b\)の公約数であるので\(\gcd(a,b)\geq\gcd(b,r)\)となる。

-

これより、\(\gcd(a,b)=\gcd(b,r)\)となる。