Euclid’s lemma: If a/bc, with gcd(a, b) = 1, then a/c.

**Proof:** Since gcd(a, b) = 1 then we can write 1 = ax + by, where x and y are integers. Multiplication of this equation by c, provides

c = 1. c = (ax + by) c = acx + bcy

*Since a\ac and a\bc, it follows that a\ (acx + bcy), which can be recast ac a\c.*