Euclidean division and the remainder

A reminder of Euclidean division

When an integer a (the dividend) is divided by an integer b (the divisor, which is not zero), the result is a quotient q and a remainder r that satisfy:

a = b × q + r, where 0 ≤ r < b

Example: 29 divided by 6 → 29 = 6 × 4 + 5. The quotient is 4, the remainder is 5, because 6 × 4 = 24 and 29 – 24 = 5.

The link to divisibility

A number a is divisible by b when the remainder r of the Euclidean division of a by b is equal to 0. In this case, a = b × q exactly, with no remainder.

Example: 18 divided by 6 -> 18 = 6 × 3 + 0. The remainder is 0, so 18 is divisible by 6 (and 6 is a divisor of 18).

Counter-example: 20 divided by 6 → 20 = 6 × 3 + 2. The remainder is 2 (not 0), so 20 is not divisible by 6.

Practical method

1. Divide the number a by the number b
2. Look at the remainder obtained
3. If the remainder is 0, then a is divisible by b (b is a divisor of a)
4. If the remainder is not 0, then a is not divisible by b

Common pitfall

The remainder must always be strictly less than the divisor (0 ≤ r < b). If, when checking a calculation, you find a remainder greater than or equal to the divisor, it means that the quotient used is incorrect: you must increase it. For example, for 29 divided by 6, a quotient of 3 would give a remainder of 11, which is greater than 6: this is incorrect; the quotient must be 4.