Proof. Recall that
mod(a,b) is the
unique 0≤r<b such that
∃q:a=qb+r.
Then it is sufficient to show that if
a=qb+r then
gcd(a,b)=gcd(b,r).
To do this,
fix a,b,q,r and assume
a=qb+r; let
d=gcd(a,b). Want to show that
d=gcd(b,r); we will do this by showing that (1)
d∣b; that (2)
d∣r; and that (3) given
e such that
e∣b and
e∣r we have
e∣d.
1. Since
d=gcd(a,b) then we already know
d∣b.
2. Since
d=gcd(a,b) then
d∣a and
d∣b so exists
ka,kb where
a=dka and
b=dkb. We know
a=qb+r so we have
r=a−qb=dka−qdkb=d(ka−qkb) and thus
d∣r.
3. Assume existence of an
e such that
e∣b and
e∣r. Then exists
kb,kr where
b=ekb and
r=ekr. Then
a=qb+r=qekb+ekr=e(qkb+kr), so
e∣a. Since
e∣a and
e∣b, then
e∣d and so
e≤d.