(0)

\(a\)を\(b\)で割った商を\(q\)とすると、
\[ a=qb+r \] と表される。
\(a\)と\(b\)の最大公約数を\(g\)とすると\(g=\gcd\left(a,b\right)\)、ある\(a',b'\in\mathbb{N}\)が存在し\(a=a'g,b=b'g\)と表すことができる。
このとき、
\begin{align*} \gcd\left(b,r\right) & =\gcd\left(b,a-qb\right)\\ & =\gcd\left(b'g,a'g-qb'g\right)\\ & =\gcd\left(b'g,\left(a'-qb'\right)g\right)\\ & =g\gcd\left(b',\left(a'-qb'\right)\right)\\ & \geq g\\ & =\gcd\left(a,b\right) \end{align*} となる。
また、\(b\)と\(r\)の最大公約数を\(h\)とすると\(h=\gcd\left(b,r\right)\)、ある\(b'',r'\in\mathbb{N}\)が存在し\(b=b''h,r=r'h\)と表すことができる。
このとき、
\begin{align*} \gcd\left(a,b\right) & =\gcd\left(bq+r,b\right)\\ & =\gcd\left(b''hq+r'h,b''h\right)\\ & =\gcd\left(\left(b''q+r'\right)h,b''h\right)\\ & =h\gcd\left(b''q+r',b''\right)\\ & \geq h\\ & =\gcd\left(b,r\right) \end{align*} となる。
これより、\(\gcd\left(b,r\right)\geq\gcd\left(a,b\right)\)かつ\(\gcd\left(a,b\right)\geq\gcd\left(b,r\right)\)となるので、\(\gcd\left(a,b\right)=\gcd\left(b,r\right)\)となる。
従って題意は成り立つ。

(0)-2

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

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

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

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

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

-

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