Euclid's Lemma

Euclid's lemma is a fundamental result in number theory stating that if a prime number divides the product of two integers, it must divide at least one of those two integers. The lemma first appeared in Euclid's Elements and is one of the oldest results in the field. It fails for composite numbers: for example, 10 divides the product of 4 and 15, which is 60, even though 10 divides neither 4 nor 15 on its own. Euclid's lemma is the key step in the proof of the fundamental theorem of arithmetic, the fact that every integer greater than one has a unique factorization into primes, and it generalizes to define what is meant by a prime element in more abstract algebraic settings such as commutative rings.