Exercise 1133Number theory › PrimesL1Added 3 Nov 2026

Euclid's lemma

#Euclid lemma#prime#divisibility

Statement

Let $p$ be prime. Show that if $p\mid ab$ , then $p\mid a$ or $p\mid b$ .

Hint

If $p\nmid a$ , then $\gcd(p,a)=1$ . Apply Gauss's lemma.

Show solutionHide solution

Case 1. If $p\mid a$ , done.

Case 2. If $p\nmid a$ , then since $p$ prime, $\gcd(p,a)=1$ . By Gauss's lemma, $p\mid b$ .

Conclusion. Euclid's lemma holds.

Application. Iterated: if $p\mid a_1\cdots a_k$ , then $p$ divides some $a_i$ .