Exercise 746Number theory › Divisibility and gcdL1Added 2 Nov 2026

Divisors of a product

#divisibility#coprime#product divisibility

Statement

Let $a,b,c$ be integers with $\divisibility(a,b)=1$ . Show that if $a\mid bc$ , then $a\mid c$ .

Hint

Use Bézout: there exist $u,v$ with $au+bv=1$ . Multiply by $c$ .

Show solutionHide solution

Bézout. Since $\divisibility(a,b)=1$ , there exist integers $u,v$ such that
$au+bv=1.$
Multiplying by $c$ :
$acu+bcv=c.$

Divisibility. $a\mid acu$ trivially, and $a\mid bcv$ since $a\mid bc$ . Hence $a$ divides the sum, i.e. $a\mid c$ .

Remark. This is Gauss's lemma, a fundamental tool in number.