Exercise 913Number theory › Divisibility and gcdL1Added 3 Nov 2026

GCD and product of coprime factors

#gcd#coprime#factorization

Statement

Let $a,b,c\in\mathbb{N}^*$ with $\gcd(a,b)=1$ and $a\mid c$ , $b\mid c$ . Show that $ab\mid c$ .

Hint

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

Show solutionHide solution

Solution

Bézout. $au+bv=1$ for some $u,v\in\mathbb{Z}$ .

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

Divisibility. $a\mid acu$ trivially. For $bcv$ : $a\mid c$ , so $a\mid bcv$ iff $a\mid b\cdot(\text{multiple of }a)\cdot v$ ... hmm, this needs $b\mid c$ , not $a\mid c$ .

Let me redo. Since $b\mid c$ , $c=kb$ . Then $a\mid kb$ and $\gcd(a,b)=1$ , so $a\mid k$ (Gauss). Thus $ab\mid kb=c$ .

Conclusion. $ab\mid c$ .

GCD and product of coprime factors

Statement

Solution

More problems in Divisibility and gcd