Euclid's lemma

Remarks

The hypothesis that $p$ is prime is necessary. For example, $6 \mid 4 \cdot 9$, but $6 \nmid 4$ and $6 \nmid 9$. A short proof uses Bézout's identity. If $p \nmid a$, then $\gcd(p, a) = 1$, so $p x + a y = 1$ for some integers $x$ and $y$. Multiply by $b$ to see that $p \mid b$. The generalized Euclid's lemma replaces the prime $p$ by an integer that is coprime to $a$. The lemma is the main step in the proof of the uniqueness part of the fundamental theorem of arithmetic.

History

The lemma is Proposition 30 of Book VII of the Elements of Euclid.