Exercise 912Number theory › Divisibility and gcdL1Added 3 Nov 2026

Gauss's lemma

#Gauss lemma#divisibility#coprime

Statement

Let $a,b,c\in\mathbb{Z}$ with $\gcd(a,b)=1$ . Show that if $a\mid bc$ , then $a\mid c$ .

Hint

Bézout: $au+bv=1$ . Multiply by $c$ .

Show solutionHide solution

Bézout. $au+bv=1$ .

Multiply by $c$ . $acu+bcv=c$ .

Divisibility. $a\mid acu$ trivially, and $a\mid bcv$ since $a\mid bc$ . So $a\mid c$ .

Conclusion. Gauss's lemma holds.

Application. If $p$ is prime and $p\mid bc$ , then $p\mid b$ or $p\mid c$ (Euclid's lemma).