Euclidean Algorithm for GCDs.

We write d|a if d divides a evenly.
To wit, if there is some integer q so d*q = a.

If a and b are integers, and d|a and d|b, d is a common
divisor of a and b.  The number 1 divides every pair of integers.


Properties of gcd:

gcd(a,b) = gcd(b,a)
gcd(\pm a, \pm b) = gcd(a,b)          \pm is plus or minus
gcd(a, 0) = |a|
gcd(0, 0) is not defined.


Theorem.  If a, b, q and r are integers and if b = aq + r,
then gcd(b, a) = gcd(a, r)

b = a*(b//a) + b%a
gcd(255, 34)  = gcd(34, 17) = gcd(17, 0) = 17

proof.
suppose d | a and d|b,  r = b - a*q; d is a factor a*q  and   
a factor of b.  therefore it's a factor of r.
Every common divisor of a and b is a common divisor of a and r.

If d|a and d|r, likewise d | b = a*q + r.

Same common divisors, so same gcd.

`