Maths WorkshopMaths problems with full solutions
Exercise 1124Number theory › PrimesL1Added 3 Nov 2026

Divisibility by coprime integers

#coprime#divisibility#product

Statement

Let a,ba,b be coprime. Show that if a∣na\mid n and b∣nb\mid n, then ab∣nab\mid n.

Hint

By Bézout, au+bv=1au+bv=1. Multiply by nn.

Show solutionHide solution

Solution

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

Multiply. n=n(au+bv)=aun+bvnn=n(au+bv)=aun+bvn.

Divisibility. a∣auna\mid aun; and b∣nb\mid n, so bvn=b⋅(multiple of b)⋅vbvn=b\cdot(\text{multiple of }b)\cdot v. But we need a∣bvna\mid bvn: since a∣na\mid n, n=kan=ka, so bvn=bvka=ab(vk)bvn=bvka=ab(vk), which is divisible by abab. Similarly aun=au⋅kb=ab(uk)aun=au\cdot kb=ab(uk), divisible by abab.

Conclusion. ab∣nab\mid n.