Exercise 204Number theory › Divisibility and gcdHigh schoolAdded 2 Nov 2026
Basic divisibility and linear combinations
#divisibility#linear combinations#divisors
Statement
- Show that if and , then and .
- More generally, show that for all integers .
- Find all positive divisors of .
Hint
For (1) and (2), write and . For (3), factor or test divisibility systematically.
Show solutionHide solution
Solution
1. If and , there exist integers with , . Then
so and .
2. With the same notation, , so .
3. . The positive divisors are
There are of them.
Remark. Part (2) is the fundamental tool for all divisibility problems: any common divisor of and divides every integer linear combination of and .