-->

# Divisibility Rules Formulas

Finding remainders is one of an important concept in arithmetic.  For example, in finding units digit of an expression, H.C.F etc finding remainder is very important.

When 100 is divided by 8, we get 4 as remainder.  This can be represented as 100 = 8×k + 4.  Here k = 12 and remainder is 4.
In competitive exams, the problems are not straight forward.  So learn the following rules and techniques carefully.
The following rules are very important:

Rule 1: If $N = A \times B \times C....$ then the remainder when N is divided by D is equal to the product of the remainders when A, B, C ... are divided by D.
$\Rightarrow {\displaystyle\left( {\frac{N}{D}} \right)_R}$ = ${\left( {\displaystyle\frac{A}{D}} \right)_R}$ × ${\left( {\displaystyle\frac{B}{D}} \right)_R}$ × ${\left( {\displaystyle\frac{C}{D}} \right)_R}...$
Here ${\displaystyle\left( {\frac{N}{D}} \right)_R}$ means the remainder when N is divided by D

Rule 2: If $N = A + B + C....$ then the remainder when N is divided by D is equal to the sum of the remainders when A, B, C ... are divided by D.
$\Rightarrow {\displaystyle\left( {\frac{N}{D}} \right)_R}$ = ${\left( {\displaystyle\frac{A}{D}} \right)_R}$ + ${\left( {\displaystyle\frac{B}{D}} \right)_R}$ + ${\left( {\displaystyle\frac{C}{D}} \right)_R}...$

## General Divisibility rules:

Let us a take a number ABCDEF.  In decimal system this number can be written as
100,000A + 10,000B + 1000C + 100D + 10E + F

### Divisibility Rule for 2:

We can easily observe that from rule 2, if ABCDEF has to be divisible by 2, 2 must divide all the six terms above.  It is evident that except F remaining numbers are divisible by 2.  So if F is divisible by 2 then the number ABCDEF is divisible by 2.

### Divisibility Rule for 5:

Since all the terms except F is divisible by 5, the number is divisible when F is divisible by 5, or F must be 0 or 5.

### Divisibility Rule for 4:

We can see that Except last two terms 10E and F, the remaining terms are divisible by 4. so If the last two digits are divisible by 4, the entire number is divisble by 4.

### Divisibility Rule for 8:

Except last three terms the remaining terms are divisible by 8. So if the last three digits are divisible by 8 then the number is divisible by 8.
Thumb Rule: for 2, 4, 8, 16... we need to check the last 1, 2, 3, 4 ... digits. Observer there 1, 2, 3, 4 are the powers of the divisor with base 2.

### Divisibility Rule for 3, 9:

100,000A + 10,000B + 1000C + 100D + 10E + F = 99999A + 9999B + 999C + 99D + 9E + (A + B + C + D + E + F)
We can see that Except (A + B + C + D + E + F) remaining terms are divisible by 3, 9.  If the digit sum is divisible by 3, 9 then the number ABCDEF is divisible by 3, 9. (A + B + C + D + E + F) is called digit sum of a number.

### Divisibility Rule for 11:

100,000A + 10,000B + 1000C + 100D + 10E + F = 100,001A + 9,999B + 1,001C + 99D + 11E + (-A + B - C + D - E + F)
From above we know that except (-A + B - C + D - E + F) the remaining digits are divisible by 11. So if the difference between the sum of the digists in the even places and odd places is 0 or multiple of 11 then the number is divisible by 11.

### Divisibility Rule for 6, 12 or any composite number:

If a composite divisor can be written as a product of co-primes and each of these co-primes divide the given number exactly, then that number is divisible by the divisor.  So if 2, 3 divide the given number exactly then 6 divides that number exactly.  Similarly, divisibility for 12 is to check divisibility for 3, 4.

### Divisibility for 7, 13, 17...:

The existing seed method rule is not good enough to solve problems given in examination.  So we learn some important formulas to solve questions easily.

### Rules related to ${a^n} \pm {b^n}$:

$\begin{array}{|c|c|} \hdashline & Divisor & divisible\,when \\[4px]\hline a^n - b^n & a-b & for\,all\,values\,of\,n \\[4px] \hline a^n - b^n & a+b & n\,is\,even \\[4px] \hline a^n + b^n & a+b & n\,is\,odd \\[4px] \hline a^n + b^n & a-b & never \\[4px] \hline \end{array}$

## Fermat's little theorem:

A number $a^{p-1}$ is divided by p, then remainder is 1. Here P is prime.
Simbolically, ${\left( {\displaystyle\frac{{{a^{p - 1}}}}{p}} \right)_R} = 1$
or ${a^{p - 1}} \equiv 1({\text{mod P}})$
The advantage of using above format is that we can add, subtract, multiply and raise to some power to the numbers on the both sides of equivalent sign.

## Wilson's theorem:

If P is a prime number then (P - 1)! + 1 is divided by P the remainder is 0. or ${\left( {\displaystyle\frac{{\left( {P - 1} \right)! + 1}}{P}} \right)_R} = 0$
or $(p - 1)! + 1 \equiv 0\left( \text{mod P} \right)$

### Simplifying using congruence mod m:

${{a}} \equiv {{b}}\left( {\,{{mod }}\,{{m}}} \right)$
The above expression can be read as, 'a' is congruent to $b$, $mod$ $m$.
This means, when $a$ is divided by '$m$' the remainder is $b$.  (or) $a, b$ gives same remainder when divided by $m$.
Now the following rules follows,
1. ${{a + k}} \equiv {{b + k}}\left( {\,{{mod }}\,{{m}}} \right)$
If you add a value k on both sides and continue your calculation
2. ${{a}} \times {{k}} \equiv {{b}} \times {{k}}\left( {\,{{mod }}\,{{m}}} \right)$
3. ${{{a}}^k} \equiv {{{b}}^k}\left( {\,{{mod }}\,{{m}}} \right)$
Important: Never divide $a, b$ with number $k$.

## Euler's Totient theorem:

If the divisor is not a prime number we cannot apply fermat little theorem.  So we learn Euler Totient theorem.
The remainder when ${N^{\phi (N)}}$ is divided by N is 1.  Here $\phi (N) = N\left( {1 - \dfrac{1}{a}} \right)\left( {1 - \dfrac{1}{b}} \right)\left( {1 - \dfrac{1}{c}} \right)...$
a, b, c .. are prime factors of the number N when N is written in prime factorization format.  $N = {a^p}.{b^q}.{c^r}...$