Divisibility in the integers
The division algorithm, properties of divisibility, and the gcd written as a combination of the two numbers.
- France: grade 12
- Iran: grade 12
Guide
We say b divides a when there is an integer q with a = bq, written b|a. For example 7|21 because 21 = 7×3.
If b does not divide a there is a remainder. For any integers a and b (b ≠ 0) there is exactly one quotient q and one remainder r with a = bq + r, where r is not less than 0 and is less than b. This is the division algorithm.
If b divides both a and c, it also divides every number ax + cy (x and y any integers).
Going back through Euclid's steps lets you write the highest common factor (HCF) of two numbers as ax + by. The converse matters too: ax + by = c has integer solutions only when the highest common factor (HCF) of a and b divides c.
Work on the division sheet or the answer box in each mission; read the hint if you get stuck.