Euclid's Lemma (For Prime Divisors)

Euclid's Lemma states that given a prime $p$ and integers $a, b$, if $p | ab$, then $p|a$ or $p|b$. Note that the "or" is inclusive, so it is also possible (but not guaranteed) that $p$ divides both $a$ and $b$. Intuitively, this should make sense. If it doesn't, take a moment and play around with some numbers to gain some intuition.

One of the first things we might think of is prime factorization - given the prime factorization of two integers, if a certain prime appears in the product, then that prime should also appear in the prime factorization of at least one of the two integers. While this is great reasoning and definitely helps build intuition, this will not pass as a proof. One reason is that the idea of "prime factorization" depends on the Fundamental Theorem of Arithmetic, which in turn is proved using Euclid's Lemma, so we would be guilty of circular reasoning!

The typical proof, while it only uses very elementary techniques, is not obvious to someone who has not seen it before. We will need to use Bezout's Lemma (also known as Bezout's Identity), which is the following: For any nonzero integers $a, b$, there exist integers $x, y$ such that $ax + by = \gcd(a, b)$. This can be easily shown by reversing the steps in the Euclidian Algorithm.

We are now ready to prove Euclid's Lemma. If $p | a$, then we are done. Otherwise, $\gcd(p, a) = 1$, so by Bezout's Lemma, there exist integers $x, y$ such that $px + ay = 1$. The next step is to multiply both sides by $b$, so $pbx + aby = b$. Since $p | pbx$ obviously and $p | aby$ by the hypothesis $p | ab$, then $p$ divides their sum, so $p | b$, hence we are done. Notice that our motivation for multiplying by $b$ was so that we could create an $ab$ term to which we could apply the hypothesis.

As an extension, consider what happens when we replace $p$ with any integer $n$. We will have to adjust our statement slightly. When you are ready, see here.