整数の性質｜ユークリッドの互除法について

割り算と最大公約数の定理の証明
\begin{align*}
&\text{自然数 $a$ を自然数 $b$ で割った商 $q$ と余り $r$ を用いると、} \\[ 5pt ]
&\quad a = bq+r \quad \text{…①} \\[ 5pt ]
&\text{これを変形すると、} \\[ 5pt ]
&\quad r = a – bq \quad \text{…②} \\[ 5pt ]
&\text{ここで、$a$ と $b$ の最大公約数を $g$ とし、$b$ と $r$ の最大公約数を $g’$ とすると、} \\[ 5pt ]
&\quad a = \alpha g \quad \text{…③} \\[ 5pt ]
&\quad b = \beta g = \beta’ g’ \quad \text{…④} \\[ 5pt ]
&\quad r = \gamma g’ \quad \text{…⑤} \\[ 5pt ]
&\text{ただし、$\alpha$ と $\beta$、$\beta’$ と $\gamma$ はそれぞれ互いに素} \\[ 10pt ]
&\text{② , ③ , ④より} \\[ 5pt ]
&\quad r = \alpha g – \beta g q = g(\alpha – \beta q) \\[ 5pt ]
&\text{となるので、$g$ は $r$ の約数である。} \\[ 5pt ]
&\text{これより、$g$ は $b$ と $r$ の公約数となるので、} \\[ 5pt ]
&\quad g \leqq g’ \quad \text{…⑥} \\[ 10pt ]
&\text{また、① , ④ , ⑤より} \\[ 5pt ]
&\quad a = \beta’ g’q + \gamma g’ = g'(\beta’ q + \gamma) \\[ 5pt ]
&\text{となるので、$g’$ は $a$ の約数である。} \\[ 5pt ]
&\text{これより、$g’$ は $a$ と $b$ の公約数となるので、} \\[ 5pt ]
&\quad g’ \leqq g \quad \text{…⑦} \\[ 10pt ]
&\text{⑥ , ⑦より $g = g’$ が成り立つ。} \\[ 5pt ]
&\text{したがって、$a$ と $b$ の最大公約数は、$b$ と $r$ の最大公約数に等しい。}
\end{align*}

必ずしも $0 \leqq r \lt b$ である必要はない例
\begin{align*}
&\text{30と4の最大公約数を求めるとする。} \\[ 5pt ]
&\quad 30 = 4 \cdot 7 + 2 \\[ 5pt ]
&\text{について、4と2の最大公約数は2より、30と4の最大公約数は2。} \\[ 5pt ]
&\text{また、} \\[ 5pt ]
&\quad 30 = 4 \cdot 6 + 6 \\[ 5pt ]
&\text{について、4と6の最大公約数は2より、30と4の最大公約数は2。} \\[ 5pt ]
&\text{したがって、定理が成り立つのに必ずしも $0 \leqq r \lt b$ である必要はない。}
\end{align*}