ユークリッドの互助法について

////////////////////////////////////////////////////////////////////////
[定理]

a = q×b + r
であるとき、
aとbの最大公約数はbとrの最大公約数に等しい

[証明]
aとbの最大公約数をmとします。すると、
a = a'm
b = b'm

となるa'とb'が存在します。それで上の式を置き換えます。
a'm = q×b'm + r

右辺はmで割り切れます。左辺の第一項もmで割り切れます。したがって、rもmで割り切れる必要があります。

aをbで割った余りrはbより小さいです。次にbとrについて同じことを行います。するとその剰余はrより小さくなります。これを繰り返すと、剰余はいつか必ずゼロになるので、この計算は終了します。
///////////////////////////////////////////////////////////////////////////////////
http://aitech.ac.jp/~koikelab/webp/cipher/cipher_02.html
このサイトにこう書いてありました
しかし、一点だけ理解できない部分があります。
確かにrがmで割り切れることはわかったのですが、だからといってaとbの最大公約数、つまりmがbとrの最大公約数になるという点が腑に落ちません
bとrはmで割り切れることは納得できるが、最大公約数がmであることが理解できません
どなたか説明お願いします