Number Theory: Divisibility tests

Understanding Divisibility Tests

Divisibility tests are simple methods used to determine whether one number is a factor or divisor of another.
They are based on the principle of congruences in number theory.
Congruences refer to the remainder left when dividing one number by another.
For example, the divisibility test for 2 says that a number is divisible by 2 if its last digit is 0, 2, 4, 6, or 8.

For 3: A number is divisible by 3 if the sum of its digits is divisible by 3.
For 4: A number is divisible by 4 if the number formed by its last two digits is divisible by 4.
For 5: A number is divisible by 5 if its last digit is 0 or 5.
For 6: A number is divisible by 6 if it is divisible by both 2 and 3.
For 9: A number is divisible by 9 if the sum of its digits is divisible by 9.
For 11: A number is divisible by 11 if the difference between the sum of digits at odd positions and the sum of digits at even positions is either 0 or a multiple of 11.

The Remainder Theorem is a related concept that’s useful in understanding and creating divisibility tests.
It states that if a number n is divided by a number d, the remainder is the same as if the last digit of n is divided by d.
This theorem forms the basis for many divisibility tests, especially those for 2, 5, and 10.

Many divisibility tests utilise the pattern of cyclic numbers where a sequence of remainders repeated in a cycle when applying the modulus operation with a particular divisor.
For example, when dividing by 11, the remainders follow the cyclic pattern: 1, 10, 1, 10,…

Divisibility tests are not only for simple arithmetic, but also have applications in more abstract areas such as cryptography, coding theory, and Computer Science.
In cryptography, understanding the factors of large numbers can be crucial to breaking encryption codes.
In Computer Science, quick tests of divisibility are an important part of designing efficient algorithms.