euclids-lemma

��# Euclid's lemma Euclid's lemma captures a fundamental property of prime numbers: If a prime p divides the product of two integers `ab then p must divide at least one of those integers (p|a or p|b`). > p|ab -> p|a (" p|b for prime p and a,b " $! Example: for p=19, a=133, b=143: 19|19019 (=133�143) -> 19|133 (19�7=133) This property is the key in the proof of the fundamental theorem of arithmetic. It is used to define prime elements, a generalization of prime numbers to arbitrary commutative rings. Euclid's Lemma shows that in the integers irreducible elements are also prime elements. The proof uses induction so it does not apply to all integral domains.