$\clubsuit$ $a=bq+r$ の式において$$\text{GCD}(a,b)=\text{GCD}(b,r)$$が成り立つことの証明
《証明》
$a,b$の最大公約数$\text{GCD}(a,b)$を$d$、$b,r$の最大公約数$\text{GCD}(b,r)$を$d’$とする。題意を証明するためには$d=d’$を示せば良い。
$a=bq+r$について$bq$を移項すると$a-bq=r$となる。仮定より、この左辺は$d$の倍数だから、右辺の$r$も$d$の倍数となる。このことから、$d$は$b,r$をともに割り切るから、$d$はそれらの最大公約数$\text{GCD}(b,r)$と同じかそれより小さくなければならない。故に$$d=\text{GCD}(a,b) \leqq \text{GCD}(b,r)=d’$$が必要である。
また、仮定より、$a=bq+r$の右辺は$d’$の倍数だから、左辺の$a$も$d’$の倍数となる。このことから、$d’$は$a,b$をともに割り切るから、$d’$はそれらの最大公約数$\text{GCD}(a,b)$と同じかそれより小さくなければならない。故に$$d=\text{GCD}(a,b) \geqq d’=\text{GCD}(b,r)$$が必要である。
$\text{GCD}(a,b) \leqq \text{GCD}(b,r) $ かつ $\text{GCD}(a,b) \geqq \text{GCD}(b,r)$が成立するためには$\text{GCD}(a,b)=\text{GCD}(b,r)$でなければならない。
以上より、$a=bq+r$の式において$\text{GCD}(a,b)=\text{GCD}(b,r)$、つまり $d=d’$ が成り立つことが示された。