# 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.

## Divisibility Rules

• 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.

## Remainder Theorem

• 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.

## Cyclic Number Pattern

• 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,…

## Applications of Divisibility Tests

• 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.