Euclid's Lemma

In number theory, Euclid's lemma (also called Euclid's first theorem) is a lemma that captures one of the fundamental properties of prime numbers. It states that if a prime divides the product of two numbers, it must divide at least one of the factors. For example since 133 × 143 = 19019 is divisible by 19, one or both of 133 or 143 must be as well. In fact, 19 × 7 = 133. It is used in the proof of the fundamental theorem of arithmetic.

The lemma is not true for composite numbers. For example, 8 does not divide 4 and 8 does not divide 6, yet 8 does divide their product 24.