Finding divisors... without dividing

Since primary school, we have known how to tell whether a number is divisible by 2, 3, 4, 5, 6, 8, 10 or 11. With divisors such as 7, 13, 17, 23, 29… or even 271, however, this seems like a high-wire act. Yet it can be done. Let's take a tour of the divisibility tests for integers, from the simplest to the most complicated. When it comes to divisibility, congruences (see box) very often make the task easier.

Did you say "congruences"?

The very existence of the number r allows us to define an equivalence relation on the set ℤ of integers: a and a’ are said to be equivalent if they have the same remainder when divided by b. We also say that "a is congruent to a’ modulo b," written a ≡ a’ [ b ]. This partitions $m a t h b b Z$ into b disjoint subsets called classes, corresponding to the b possible remainders on division by b. Each class corresponds to a remainder from 0 to b – 1; they are denoted by $d o t 0, d o t 1, d o t 2 \hat{a} ¦ d o t (b - 1) . {dot{0},dot{1},dot{2}â¦dot{(b-1)}}.$

The "is congruent to" relation is compatible with addition, subtraction, multiplication and exponentiation.

The map that assigns each integer its value modulo b is a homomorphism: the remainder of the sum of two numbers is congruent modulo b to the sum of their remainders; likewise, the remainder of a product is congruent modulo b to the product of the remainders.

In particular, divisibility can be expressed in the language of congruences: saying that "a is divisible by b" is equivalent to saying that the remainder when a is divided by b is zero, written a ≡ 0 [ b ].

When b is prime, further properties come into play. Every element N not congruent to 0 has a multiplicative inverse: an equivalence class of numbers, all congruent modulo b, whose products with N are congruent to 1 modulo b. For example, if b = 5, it is easy to see that 1 and 4 are their own inverses: 1 $d G l t Z X M =$ 1 ≡ 1 [5], 4 $d G l t Z X M =$ 4 ≡ 16 ≡ 1 [5]. Likewise, 2 and 3 are inverses of each other: 2 $d G l t Z X M =$ 3 ≡ 6 ≡ 1 [5].

Brush up on the classics!

To determine whether an integer is divisible by 2 or 5, we do not even need the properties of congruences. A number N is divisible by 2 if its units digit u is even. Separate the units digit u from N, and call the number N with this digit removed d. Then N = 10 d + u. Since 10 is a multiple of 2, N is divisible by 2 if and only if u is—that is, if it is even.

The same applies to divisibility by 5. Since 10 is also a multiple of 5, N is divisible by 5 if and only if u is—that is, if it equals 0 or 5. In the language of congruences, N ≡ u \[2\] and N ≡ u \[5\]. Thus, whether N is divisible by 2 or by 5 can be determined from its units digit.