Euclid's rule

Statement

Euclid's rule

For integers where we have

Proof

We prove more generally that which will give the desired result from the definition of modular arithmetic.

Note that if () and () then ().

Also if () and () then ()).

Therefore both sides share divisors and so the greatest common divisor.