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.