Divisibility Criteria

Casting out nines

We study now some useful applications that make use of the congruence. Casting out of nines is a necessary condition to check the exactness of a multiplication. We try first to understand what's behind this method and what the number 9 has to do with it. Let a be an integer, and let a₀, a₁, ..., a_n be its decimal digits. In other words,

where 0 ≤ a_i ≤ 9 for i = 0,...,n.

A number as 2134 corresponds to

Whatever n > 0

by using the properties of congruences,

thus any integer number, written in decimal notation is congruent modulo 9 to the sum of its digits.

Suppose we want to multiply two integers: 3455 ⋅ 2134, obtaining as result 7282970. We want to check the exactness of the result. We proceed as follows: write the sum of the digits of each number:

and them multiply the sums obtained by each other 8 ⋅ 1: if the result is correct this number is equal to the the sum of the digits in the result 35 = 3 + 5 = 8.

Indeed we know from the discussion above that 3455 ≡₉ 8, 2134 ≡₉ 1 e 7282970 ≡₉ 8. Thus 3455 ⋅ 2134 ≡₉ 8 ⋅ 1 = 8.

If instead of 8 we would have obtained a different number that would have signified with certainty that the result of the multiplation was incorrect. However, having obtained 8, does not guarentee the corecteness of the result.

Divisibility criteria

Per studiare la divisibilità di un numero per n sfruttiano le seguenti relazioni.

z = z₁ (mod n)  ⇒  z− z₁ = nh  ⇒  z = z₁ + nh

Dato che la somma di due numeri divisibili per n (cioè z₁ e n) è ancora un numero divisibile per n, allora z sarà divisibile per n se lo è anche z₁.

Proposition 4.11. A number is dibisible by 3 (by 9), only if the sum of its digits is divisible by 3 (by 9).

Proof. The reason this divisibility test works is easy to detect. If we write an integer z as

in terms of its digits a_n, a_n−1, a₁, a₀, then the sum S of its digits is

So, the difference between z and the sum S of its digits is

which is divisible by 3. Thus,

Hence z is divisible by 3 (by 9) if and only if the sum S of its digits is divisible by 3 (by 9). □

Proposition 4.12. An integer number is divisible by 2 or by 5 if and only if its rightmost digit, is divisible by 2 or by 5;

Proof. For each n > 0, 10ⁿ ≡ 0 both mod 2 and mod 5. So, z ≡ a₀ both mod 2 and mod 5, and this proves the corresponding divisibility tests. □

Proposition 4.13. An integer number is divisible by 4 (or by 25, respectively) if and only if the number (a₁a₀) formed by its last two digits a₁a₀ is divisible by 4 (or by 25, respectively);

Proof. 100 = 2² 5² ≡ 0 both modulo 4 and modulo 25, and so every integer is congruent modulo 4 and modulo 25 to the integer formed by its rightmost two digits.□

Proposition 4.14. An integer z = (a_n + a_n−1 + ... + a₁ + a₀)₁₀ is divisible by 2^k if and only if 2^k divides the number (a_k−1 a_k−2, ..., a₁a₀)₁₀ formed by the last k digits of z.

Proof. 10ⁿ = 2ⁿ 5ⁿ ≡ 0 (mod 2^k) for all n ≥ k, proving the divisibility test for 2^k. In particular, an integer is divisible by 8 if and only if (a₂ a₁ a₀)₁₀ is divisible by 8. □

Divisibility by 6. If the given number is divisible by both 2 and 3. The number 619230 has 0 as last digit, so it is divisible by 2, and the sum of its digits is 21 which is divisible by 3.

Proposition 4.15 (Divisibility by 7). To determine whether n is divisible by 7, we take the last digit, double it and subtract it from the first part of the number. If you get an answer divisible by 7, then the original number is divisible by 7. You may have to apply the rule repeatedly. The result of the divisibility test for 7 will not only determine divisibility, but also the remainder upon dividing by 7.

Example 4.16. Take 8631. Split into 863 and 1. Subtract 1x2 = 2 from 863 to get 861. Now split 861 into 86 and 1. Subtract 2 from 86. Maybe you recognize 84 as a multiple of 7. If not, double 4 and subtract from 8 to get 0, which is divisible by 7.

Take 522. Split into 52 and 2. Subtract 4 from 52 to get 50. Since 50 isn’t divisible by 7, neither is 522.

Proof. Let n consist of two parts: A, which contains all digits aside from the units digit, and B, the units digit, so that the numerical value of N is 10A + b. We want to show that, iff A − 2B is a multiple of 7, then so is n. Setting A − 2B = 7k for some positive integer k, we multiply both sides by 10 to obtain 10A − 20B = 70k. Adding 21B to both sides yields 10A + B = 70k + 21 = 7(10k + 3), as desired.

Next we prove the contrary. If we suppose 10A + B = 7k for some positive integer k, then 10A − 20B = 7k − 21B (after subtraction of 21B from both sides) and 10(A − 2B) = 7(k − 3B). This implies that A − 2B, is a multiple of 7. This completes the proof.  □

Proposition 4.17. An integer is divisible by 11 if and only if the sum of its digits taken with alternating signs

is divisible by 11.

Proof. Notice that 10 ≡ −1 (mod 11), we can write

and z is congruent to the alternating sum of its digits. □