# Number Theory: Divisibility tests

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