Maths WorkshopMaths problems with full solutions
Exercise 204Number theory › Divisibility and gcdHigh schoolAdded 2 Nov 2026

Basic divisibility and linear combinations

#divisibility#linear combinations#divisors

Statement

  1. Show that if d∣ad\mid a and d∣bd\mid b, then d∣a+bd\mid a+b and d∣a−bd\mid a-b.
  2. More generally, show that d∣ax+byd\mid ax+by for all integers x,yx,y.
  3. Find all positive divisors of 6060.
Hint

For (1) and (2), write a=dka=dk and b=dℓb=d\ell. For (3), factor 6060 or test divisibility systematically.

Show solutionHide solution

Solution

1. If d∣ad\mid a and d∣bd\mid b, there exist integers k,ℓk,\ell with a=dka=dk, b=dℓb=d\ell. Then
a+b=d(k+ℓ),a−b=d(k−ℓ),a+b=d(k+\ell),\qquad a-b=d(k-\ell),
so d∣a+bd\mid a+b and d∣a−bd\mid a-b.

2. With the same notation, ax+by=dkx+dℓy=d(kx+ℓy)ax+by=dkx+d\ell y=d(kx+\ell y), so d∣ax+byd\mid ax+by.

3. 60=22⋅3⋅560=2^2\cdot3\cdot5. The positive divisors are
1,2,3,4,5,6,10,12,15,20,30,60.1,2,3,4,5,6,10,12,15,20,30,60.
There are (2+1)(1+1)(1+1)=12(2+1)(1+1)(1+1)=12 of them.

Remark. Part (2) is the fundamental tool for all divisibility problems: any common divisor of aa and bb divides every integer linear combination of aa and bb.