Divisibility Theorems

Edit Notice

2023-12-06

• Added divisibility rules for 13 and 17
• Added a section about recursive divisibility algorithms

2025-07-23

• Moved fraction flipping to Fraction Flipping

1Divisibility Theorems

When it comes to divisibility, there exist some neat theorems to test a certain number’s different divisibilities, or factors. The following are those theorems and their proofs. Some of the proofs are more trivial than others, such as the proof for divisibility by 1, 2, 5, and 10. From here on out, it’s assumed that every number, when working with divisibility, is an integer.

What is the smallest number that is divisible by 1 through 10?

The answer is 2520. You can try the different divisibility theorems below to prove it.

Divisibility By 1

This theorem is quite easy to remember. Every integer is divisible by 1.

$$\boxed{ 1 \mid a \iff a \in \mathbb{Z} }$$

Divisibility By 2

It’s common knowledge that every even number (numbers ending with an even number) is divisible by 2. This is because even numbers are multiples of 2. In short, if a number ends with either 0, 2, 4, 6, or 8, it is divisible by 2.

Say we have a four-digit number $abcd$, where $a$ represents the number of thousands, $b$ the number of hundreds, $c$ the number of tens, and the number $d$. This number can be represented as $1000a + 100b + 10c + d$. If $d$ is divisible by 2, we can represent it as an even number $2n$, like so:

$$\begin{align*} &1000a + 100b + 10c + 2n \\ &2 \left( 500a + 50b + 5c + n \right) \end{align*}$$

We can now see that the number is divisible by 2 if, and only if, the last digit is divisible by 2. And so the theorem is proven.

$$\boxed{ 2 \mid abcd \iff 2 \mid d }$$

Divisibility By 3

The theorem goes that if the sum of all digits in a number is divisible by 3, the whole number is divisible by 3, i.e.

$$3 \mid abcd \iff 3 \mid \left( a + b + c + d \right)$$

Why is this proposition true?

Let’s use the four-digit number $abcd$, where $a$ represents the number of thousands, $b$ the number of hundreds, $c$ the number of tens, and the number $d$. This number can be represented as $1000a + 100b + 10c + d$. Now let’s break out one $a$, $b$, and $c$ from the first 3 terms, and factor out 3 like so:

$$\begin{align*} & 1000a + 100b + 10c + d \\ & \left( 999a + 99b + 9c \right) + \left( a + b + c + d \right) \\ & 3 \left( 333a + 33b + 3c \right) + \left( a + b + c + d \right) \end{align*}$$

We can now see that the first term is divisible by 3, and the second term is divisible by 3 if, and only if, the sum of $a + b + c + d$ is divisible by 3. And so the theorem is proven.

$$\boxed{ 3 \mid abcd \iff 3 \mid \left( a + b + c + d \right) }$$

We have shown that the procedure above will hold for all cases. The procedure is also recursive. If the sum is too hard to test for divisibility, the procedure can be repeated until a smaller sum is revealed. This is rarely necessary as the divisibility of the sum is often easy to determine.

Divisibility By 4

The theorem goes that if the last two digits of a number are divisible by 4, the whole number is divisible by 4, i.e.

$$4 \mid abcd \iff 4 \mid cd$$

Why is this proposition true?

Let’s use the four-digit number $abcd$, where $a$ represents the number of thousands, $b$ the number of hundreds, $c$ the number of tens, and the number $d$. This number can be represented as $1000a + 100b + 10c + d$. Now let’s factor out 4 from the first two terms, like so:

$$\begin{align*} &1000a + 100b + 10c + d \\ &4 \left( 250a + 25b \right) + \left( 10c + d \right) \end{align*}$$

We can now see that the first term is divisible by 4, so the whole number is divisible by 4 if, and only if, the second term is divisible by 4. And so the theorem is proven.

$$\boxed{ 4 \mid abcd \iff 4 \mid cd }$$

Divisibility By 5

The theorem goes that if the last digits of a number are divisible by 5, the whole number is divisible by 5, i.e.

$$5 \mid abcd \iff 5 \mid d$$

Why is this proposition true?

Let’s use the four-digit number $abcd$, where $a$ represents the number of thousands, $b$ the number of hundreds, $c$ the number of tens, and the number $d$. This number can be represented as $1000a + 100b + 10c + d$. Now let’s factor out 5 from the first three terms, like so:

$$\begin{align*} &1000a + 100b + 10c + d \\ &5 \left( 500a + 50b + 5c \right) + d \end{align*}$$

We can now see that the first term is divisible by 5, so the whole number is divisible by 5 if, and only if, the second term is divisible by 5. And so the theorem is proven. As the only one-digit numbers that are divisible by 5 are 0 and 5, another way of putting it is that if the last digit is 0 or 5, the number is divisible by 5.

$$\boxed{ 5 \mid abcd \iff 5 \mid d }$$

Divisibility By 6

This theorem is a combination of the theorem for divisibility by 2 and divisibility by 3.

$$\boxed{ 6 \mid abcd \iff 3 \mid \left( a + b + c + d \right) \land 2 \mid d }$$

Warning

Be careful when combining theorems like this. Don’t be fooled and try to combine the divisibility theorems for 2 and 4 to get the theorem for 8, as numbers divisible by 4 are always divisible by 2. The number 4 is, for instance, both divisible by 2 and by 4, but not by 8. Make sure the theorems you combine doesn’t share a factor, like 4 and 2 sharing factor 2. It’s, of course, possible to use theorems 4 and 2 together, but it’s not certain in all cases that the two theorems prove divisibility by 8.

Divisibility By 7

Probably one of the most useful theorems is the theorem of divisibility by 7, as it is recursive (just like the theorems of divisibility by 3 and 9). The theorem states that if the difference between the last digit multiplied by 2 and the remaining digits in a number is divisible by 7, the whole number is divisible by 7. I’ll show you the procedure with an example below:

$$\begin{align*} &7 \stackrel{?}{\mid} 3423 \\ &342 - 3 \times 2 &= 336 \\ &33 - 6 \times 2 &= 21 \\ &7 \mid 21 &\Rightarrow 7 \mid 3423 \end{align*}$$

Neat! So how and why does it work? For simplicity’s sake, we use a two-digit number $ab$, represented as $10a + b$. The theorem says that if (A) $7 | a - 2b$ then (B) $7 | 10a + b$. Let’s prove it!

In order to prove the theorem, we must prove both A and B. So let’s start with A. If we have $a - 2b$, and it’s divisible by 7, we know that 7 must be a factor of the expression. We can now create an equation.

$$a - 2b = k$$

Multiply the whole equation by 10, and add one extra $b$:

$$\begin{align*} \hi{10}a - \hi{20}b = \hi{70}k \\ 10a - 20b \hi{+ b} = 70k \hi{+ b} \\ 10a - \hi{19b} = 70k + b \end{align*}$$

Now add $20b$ to each side of the equation, and try to factor out 7:

$$\begin{align*} 10a - 19b \hi{+ 20b} = 70k + b \hi{+ 20b} \\ 10a \hi{+ b} = 70k \hi{+ 21b} \\ 10a + b = \hi{7 \left( 10k + 3b \right)} \end{align*}$$

We can now see that the right side of the equation is divisible by 7, and our left side says $10a + b$. Neat, we now know that the two-digit number $ab$ is divisible by 7. Now we must show that B implies A. That is, if $a - 2b$ is divisible by 7, then $10a + b$ is divisible by 7. Let’s prove B.

Just as for A, we know that 7 must be a factor of the expression. We can now create another equation:

$$10a + b = 7$$

Subtract $21b$ from the whole equation, and factorize:

$$\begin{align*} 10a + b \hi{- 21b} = 7k \hi{- 21b} \\ 10a \hi{- 20b} = 7k - 21b \\ \hi{10 \left( a - 2b \right) } = \hi{7 \left( k - 3b \right) } \end{align*}$$

We can now see that the right side of the equation is divisible by 7, and on our left hand, 10 is not divisible by 7, so the expression inside the parenthesis must be. But isn’t that expression $a - 2b$? We now have the proof for the theorem and can conclude that, indeed,

$$\boxed{ 7 \mid ab \iff 7 \mid a - 2b }$$

We have shown that the procedure above will hold for all cases.

Divisibility By 8

The theorem is quite similar to the theorem for divisibility by 4. The theorem goes that if the last three digits of a number are divisible by 8, then the whole number is divisible by 8, i.e.

$$8 \mid abcd \iff 8 \mid bcd$$

Why is this proposition true?

Let’s use the four-digit number $abcd$, where $a$ represents the number of thousands, $b$ the number of hundreds, $c$ the number of tens, and the number $d$. This number can be represented as $1000a + 100b + 10c + d$. Now let’s factor out 8 from the first term, like so,

$$\begin{align*} 1000a + 100b + 10c + d \\ 8 \left( 125a \right) + \left( 100b + 10c + d \right) \end{align*}$$

We can now see that the first term is divisible by 8, so the whole number is divisible by 8 if, and only if, the second term is divisible by 8. And so the theorem is proven.

$$\boxed{ 8 \mid abcd \iff 8 \mid bcd }$$

Divisibility By 9

Much like the theorem for divisibility by 3, the theorem goes that if the sum of all digits in a number is divisible by 9, the whole number is divisible by 9, i.e.

$$9 \mid abcd \iff 9 \mid \left( a + b + c + d \right)$$

Why is this proposition true?

Let’s use the four-digit number $abcd$, where $a$ represents the number of thousands, $b$ the number of hundreds, $c$ the number of tens, and the number $d$. This number can be represented as $1000a + 100b + 10c + d$. Now let’s break out one $a$, $b$, and $c$ from the first 3 terms, and factor out 9 like so:

$$\begin{align*} 1000a + 100b + 10c + d \\ \left( 999a + 99b + 9c \right) + \left( a + b + c + d \right) \\ 9 \left( 111a + 11b + 1c \right) + \left( a + b + c + d \right) \end{align*}$$

We can now see that the first term is divisible by 9, and the second term is divisible by 9 if, and only if, the sum of $a + b + c + d$ is divisible by 9. And so the theorem is proven.

$$\boxed{ 9 \mid abcd \iff 9 \mid \left( a + b + c + d \right) }$$

We have shown that the procedure above will hold for all cases. The procedure is also recursive. If the sum is too hard to test for divisibility, the procedure can be repeated until a smaller sum is revealed. This is rarely necessary as the divisibility of the sum is often easy to determine.

Divisibility By 10

The theorem goes that if the last digits of a number are divisible by 10, the whole number is divisible by 10, i.e.

$$10 \mid abcd \iff 10 \mid d$$

Why is this proposition true?

Let’s use the four-digit number $abcd$, where $a$ represents the number of thousands, $b$ the number of hundreds, $c$ the number of tens, and the number $d$. This number can be represented as $1000a + 100b + 10c + d$. Now let’s factor out 10 from the first three terms, like so:

$$\begin{align*} 1000a + 100b + 10c + d \\ 10 \left( 100a + 10b + c \right) + d \end{align*}$$

We can now see that the first term is divisible by 10, so the whole number is divisible by 10 if, and only if, the second term is divisible by 10. And so the theorem is proven. As the only one-digit number that is divisible by 10 is 0, another way of putting it is that if the last digit is 0, the number is divisible by 10.

$$\boxed{ 10 \mid abcd \iff 10 \mid d }$$

Divisibility By 11

The theorem goes that a number is divisible by 11 if, and only if, the alternate sum of its digits is divisible by 11. Like so,

$$\begin{align*} 11 \stackrel{?}{\mid} 190905 \\ 1 - 9 + 0 - 9 + 0 - 5 = -22 \\ 11 \mid -22 \Rightarrow 11 \mid 190905 \end{align*}$$

Neat! So how and why does it work? For simplicity’s sake, we use a four-digit number $abcd$, where $a$ represents the number of thousands, $b$ the number of hundreds, $c$ the number of tens, and the number $d$. This number can be represented as $1000a + 100b + 10c + d$. This expression can also be represented in another way by manipulating the terms. We give and take in an alternating fashion, like so:

$$\begin{align*} 1000a + 100b + 10c + d \\ \hi{ a \left( 1000 \right) } + \hi{ b \left( 100 \right) } + \hi{ c \left( 10 \right) } + d \\ a \left( \hi{ 1001 - 1 } \right) + b \left( \hi{ 99 + 1 } \right) + c \left( \hi{ 11 - 1 } \right) + d \\ \hi{ 1001a - a } + \hi{ 99b + b } + \hi{ 11c - c} + d \\ 1001a \hi{ + 99b + 11c - a + b} - c + d \end{align*}$$

Now we factorize the expression, like so:

$$\hi{ 11 \left( 91a + 9b + c \right) } - a + b - c + d$$

We can see that the first term in the expression is divisible by 11. This means that if, and only if, the sum of the other terms is divisible by 11, then the whole expression is divisible by 11, and so the theorem is proven.

$$\boxed{ \begin{align*} { 11 \mid abcd \iff 11 \mid -a + b - c + d } \\ { 11 \mid abcd \iff 11 \mid a - b + c - d } \end{align*} }$$

We have shown that the procedure above will hold for all cases, as the number can be extended with infinite digits and still follow the same pattern.

Divisibility By 13

Just like the theorem of divisibility by 7, the theorem of divisibility by 13, is recursive. The theorem states that if the sum of the last digit multiplied by 4 and the remaining digits in a number is divisible by 13, the whole number is divisible by 13. I’ll show you the procedure with an example below:

$$\begin{align*} { 13 \stackrel{?}{\mid} 76752 } \\ { 7675 + 2 \times 4 = 7683 } \\ { 768 + 3 \times 4 = 780 } \\ { 78 + 0 \times 4 = 78 } \\ { 7 + 8 \times 4 = 39 } \\ { 13 \mid 39 \Rightarrow 13 \mid 76752 } \end{align*}$$

Neat! So how and why does it work? For simplicity’s sake, we use a two-digit number $ab$, represented as $10a + b$. The theorem says that if (A) $13 | a + 4b$ then (B) $13 | 10a + b$. Let’s prove it!

In order to prove the theorem, we must prove both A and B. So let’s start with A. If we have $a + 4b$, and it’s divisible by 13, we know that 13 must be a factor of the expression. We can now create an equation.

$$a + 4b = 13k$$

Multiply the whole equation by 10, and add one extra $b$:

$$\begin{align*} { \hi{10}a + \hi{40}b = \hi{130}k } \\ { 10a + 40b \hi{+ b} = 130k \hi{+ b} } \\ { 10a + \hi{41b} = 130k + b } \end{align*}$$

Now subtract $40b$ from each side of the equation, and try to factor out 13:

$$\begin{align*} { 10a + 41b \hi{- 40b} = 130k + b \hi{- 40b} } \\ { 10a \hi{+ b} = 130k \hi{- 39b} } \\ { 10a + b = \hi{13 \left( 10k - 3b \right)} } \end{align*}$$

We can now see that the right side of the equation is divisible by 13, and our left side says $10a + b$. Neat, we now know that the two-digit number $ab$ is divisible by 13. Now we must show that B implies A. That is, if $a + 4b$ is divisible by 13, then $10a + b$ is divisible by 13. Let’s prove B.

Just as for A, we know that 13 must be a factor of the expression. We can now create another equation:

$${ 10a + b = 13k }$$

Add $39b$ to both sides of the equation, and factorize:

$$\begin{align*} { 10a + b \hi{+ 39b} = 13k \hi{+ 39b} } \\ { 10a \hi{+ 40b} = 13k + 39b } \\ { \hi{10 \left( a + 4b \right) } = \hi{13 \left( k + 3b \right) } } \end{align*}$$

We can now see that the right side of the equation is divisible by 13, and on our left hand, 10 is not divisible by 13, so the expression inside the parenthesis must be. But isn’t that expression $a + 4b$? We now have the proof for the theorem and can conclude that, indeed,

$$\boxed{ 13 \mid ab \iff 13 \mid a + 4b }$$

We have shown that the procedure above will hold for all cases.

Divisibility By 17

Just like the theorem of divisibility by 7 and 13, the theorem of divisibility by 17, is recursive. The theorem states that if the difference between last digit multiplied by 5 and the remaining digits in a number is divisible by 17, the whole number is divisible by 17. I’ll show you the procedure with an example below:

$$\begin{align*} { 17 \stackrel{?}{\mid} 206091 } \\ { 20609 - 1 \times 5 = 20604 } \\ { 2060 - 4 \times 5 = 2040 } \\ { 204 - 0 \times 5 = 204 } \\ { 20 - 4 \times 5 = 0 } \\ { 17 \mid 0 \Rightarrow 17 \mid 206091 } \end{align*}$$

If you are not satisfied with 0 being the numerator, here is another example:

$$\begin{align*} { 17 \stackrel{?}{\mid} 2057 } \\ { 205 - 7 \times 5 = 170 } \\ { 17 - 0 \times 5 = 17 } \\ { 17 \mid 17 \Rightarrow 17 \mid 2057 } \end{align*}$$

Neat! So how and why does it work? For simplicity’s sake, we use a two-digit number $ab$, represented as $10a + b$. The theorem says that if (A) $17 | a - 5b$ then (B) $17 | 10a + b$. Let’s prove it!

In order to prove the theorem, we must prove both A and B. So let’s start with A. If we have $a - 5b$, and it’s divisible by 17, we know that 17 must be a factor of the expression. We can now create an equation.

$$a - 5b = 17k$$

Multiply the whole equation by 10, and add one extra $b$:

$$\begin{align*} { \hi{10}a - \hi{50}b = \hi{170}k } \\ { 10a - 50b \hi{+ b} = 170k \hi{+ b} } \\ { 10a - \hi{49b} = 170k + b } \end{align*}$$

Now add $50b$ to each side of the equation, and try to factor out 17:

$$\begin{align*} { 10a - 49b \hi{+ 50b} = 170k + b \hi{+ 50b} } \\ { 10a \hi{+ b} = 170k \hi{+ 51b} } \\ { 10a + b = \hi{17 \left( 10k + 3b \right)} } \end{align*}$$

We can now see that the right side of the equation is divisible by 17, and our left side says $10a + b$. Neat, we now know that the two-digit number $ab$ is divisible by 17. Now we must show that B implies A. That is, if $a - 5b$ is divisible by 17, then $10a + b$ is divisible by 17. Let’s prove B.

Just as for A, we know that 17 must be a factor of the expression. We can now create another equation:

$$10a + b = 17k$$

Subtract 51b from both sides of the equation, and factorize:

$$\begin{align*} { 10a + b \hi{- 51b} = 17k \hi{- 51b} } \\ { 10a \hi{- 50b} = 17k + 51b } \\ { \hi{10 \left( a - 5b \right) } = \hi{17 \left( k - 3b \right) } } \end{align*}$$

We can now see that the right side of the equation is divisible by 17, and on our left hand, 10 is not divisible by 17, so the expression inside the parenthesis must be. But isn’t that expression $a - 5b$? We now have the proof for the theorem and can conclude that, indeed,

$$\boxed{ 17 \mid ab \iff 17 \mid a - 5b }$$

We have shown that the procedure above will hold for all cases.

2Recursive Divisibility Algorithms

As you might have noticed, there are some divisibility rules that are quite similar. The rules for divisibility by 7, 13, and 17 are all based on a recursive algorithm in which the last digit is multiplied by a certain number and then either added to or subtracted from the number represented by the remaining digits. Similar to this:

$$abcd \rightarrow abc + d \times n$$

where $n$ represents the number that is multiplied by the last digit $d$. In the theorems proven above, the rules for divisibility by 7, 13 and 17 could be summarized like so:

$$\begin{align*} {7 \mid abcd \iff 7 \mid abc -2 \times d} \\ {13 \mid abcd \iff 13 \mid abc +4 \times d} \\ {17 \mid abcd \iff 17 \mid abc -5 \times d} \end{align*}$$

Except for $n$ being different in each algorithm, they are all the same. They could, in fact, be summarized even shorter by only stating the divisor and the number $n$ in this way:

$$7: -2 13: +4 17: -5$$

Divisibility by 11 could also be tested in this manner by having $n = -1$. However, the rule of alternating subtraction and addition between the digits in a number is much more effective than using the recursive algorithm for testing divisibility by 11.

There are, in fact, multiple divisibility rules that can be constructed using the recursive algorithm by only changing the number $n$. I have written a short Python script that finds all recursive divisibility rules along with their corresponding n. However, I haven’t ensured that all the rules found actually work in all cases; there could be false positives. They would need to be proven algebraically first. The ones I have proven to be correct, including 11, are:

$$7: -2 11: -1 13: +4 17: -5$$

Before you think that the pattern is connected to prime numbers, try the algorithm with divisibility by 27 using n = -8. The next working number after 27 is, in fact, 29, and all prime numbers are included. There are in fact some other interesting patterns…

Python Script For Finding Recursive Divisibility Algorithms

If you would like to discover and prove the remaining ones, as I have done for 7, 13, and 17, you can try using this Python script:

#!/usr/bin/env python3

# find all recursive divisibility algorithms from 1 through 99
for div in range(1, 100):

 # test all recursive additions from 2 up to the div
 for n in range(2, div):

 # create a large number with div as a known factor
 num = div * 123456789123456

 # perform recursive calculations while number is divisible by the div
 while num % div == 0 and num > div:
 # keep track of the previous number
 prev = num

 # perform recursive calculation (abcd -> abc + d*n)
 num = int(str(num)[:-1]) + int(str(num)[-1]) * n

 # break on infinite loop
 if (prev == num or prev == div):
 break

 # make last check to see if the number is divisible by the div
 if (num % div == 0):

 # use the smallest (disregarding if it's negative or positive)
 # number in the recursive calculations.
 # this means that there is always to ways to perform the recursive
 # calculations, either by addition or by subtraction
 #
 # ex: 13: abcd -> abc -9d or abc +4d
 # in this example 4 < 9, so 4 is the smallest
 if (div - n < n):
 n -= div
 print("{:d}: {:+d}".format(div, n))
 break

When running the script, you might discover some interesting patterns from 11 and up:

        1 --->    11: -1     |-
        3 |       13: +4               <---
   +10  7 |       17: -5         <--      |
        9 |       19: +2     |+    |      | +3
        1 --->    21: -2     |-    | -3   |
        3 |       23: +7           |   <---
   +10  7 |       27: -8         <--      |
        9 |       29: +3     |+    |      | +3
        1 --->    31: -3     |-    | -3   |
        3 |       33: +10          |   <---
   +10  7 |       37: -11        <--      |
        9 |       39: +4     |+    |      | +3
        1 --->    41: -4     |-    | -3   |
        3 |       43: +13          |   <---
   +10  7 |       47: -14        <--      |
        9 |       49: +5     |+    |      | +3
        1 --->    51: -5     |-    | -3   |
        3 |       53: +16          |   <---
   +10  7 |       57: -17        <--      |
        9 |       59: +6     |+    |      | +3
        1 --->    61: -6     |-    | -3   |
        3 |       63: +19          |   <---
   +10  7 |       67: -20        <--      |
        9 |       69: +7     |+    |      | +3
        1 --->    71: -7     |-    | -3   |
        3 |       73: +22          |   <---
   +10  7 |       77: -23        <--      |
        9 |       79: +8     |+    |      | +3
        1 --->    81: -8     |-    | -3   |
        3 |       83: +25          |   <---
   +10  7 |       87: -26        <--      |
        9 |       89: +9     |+    |      | +3
        1 --->    91: -9     |-    | -3   |
        3 |       93: +28          |   <---
        7 |       97: -29        <--
        9 |       99: +10    |+

Even if the script won’t output 3 and 9, they do follow the same pattern. And the same could technically be said about 1. So, the pattern actually starts at 1 and continues into infinity. And as all prime numbers end with either 1, 3, 7 or 9, except for 2 and 5, all prime numbers are included. This is a known sequence: https://oeis.org/A333448

Finding All Divisibility Algorithms For Primes

Based on the output from the script and the knowledge about all primes being included, except for 2 and 5, we could construct a short list of everything we need to find out if a number is divisible by any prime number.

What we need:

1. The divisibility rule for the prime number 2: is the last digit an even number?

   $$2 \mid abcd \iff 2 \mid d$$

2. The divisibility rule for the prime number 5: is the last digit a 5 or a 0?

   $$5 \mid abcd \iff 5 \mid d$$

3. A general rule for any number with the last digit being 1, 3, 7 or 9, including the rest of all prime numbers:

   $$n \mid abcd \iff n \mid abc + D(n) \times d$$

4. A way to calculate D(n):

   $$\begin{align*} D(n) = \begin{cases} 9a + 1, & \text{if } n = 10a + 1 \\ 3a + 1, & \text{if } n = 10a + 3 \\ 7a + 5, & \text{if } n = 10a + 7 \\ a + 1, & \text{if } n = 10a + 9 \end{cases} \end{align*}$$

If we want a small number, $D(n)$, to add or subtract:

$$\begin{align*} D_{s}(n) = \begin{cases} D(n) - n, & \text{if } n - D(n) < D(n) \\ D(n), & \text{otherwise} \end{cases} \end{align*}$$

Example, get the divisibility algorithm for the prime number 71:

$$\begin{align*} { D(71) = 9 \times 7 + 1 = 64 } \\ { D_{s}(n) = 64 - 71 = -7 } \\ { \Rightarrow 71 \mid abcd \iff 71 \mid abc -7d } \end{align*}$$

Find out if 87614 is divisible by 71:

$$\begin{align*} { 8761 -7 \times 4 = 8733 } \\ { 873 -7 \times 3 = 852 } \\ { 85 -7 \times 2 = 71 } \\ { 71 \mid 71 \Rightarrow 71 \mid 87614 } \end{align*}$$

Alternative Way of Deriving Recursive Divisibility Algorithms

Another way of proving the recursive divisibility theorems, instead of using a two-way implication as I have done above, is to derive each rule from a four-digit number abcd. Let me explain by deriving the rule of divisibility by 13, both for $n = 4$ and $n = -9$ ($4 - 13$).

Say we have a four-digit number, $abcd$, where $a$ represents the number of thousands, $b$ the number of hundreds, $c$ the number of tens, and the number $d$. This number can be represented as $1000a + 100b + 10c + d$. We then add and subtract different amounts of $a$s, $b$s, $c$s and $d$s so that we can deduce the circumstances under which divisibility by 13 is possible.

$$\begin{align*} { 1000a + 100b + 10c + d } \\ { 1000a \hi{+ 300a} + 100b \hi{+ 30b} + 10c \hi{+ 3c} + d \hi{+ 12d} \hi{- 300a} \hi{- 30b} \hi{- 3c} \hi{- 12d} } \\ { \hi{1300a} \hi{+ 130b} \hi{+ 13c} \hi{+ 13d} - 300a - 30b - 3c - 12d } \\ { \hi{13 \left( 100a + 10b + c + d \right) } \hi{- 3 \left( 100a + 10b + c + 4d \right) } } \end{align*}$$

We can now observe that the first term is divisible by 13 since 13 is clearly a factor of that term. The second term has the factor 3, which is not divisible by 13. Therefore, for the entire expression to be divisible by 13, the sum of the terms inside the parenthesis must also be divisible by 13.

$$\begin{align*} { 100a + 10b + c + 4d } \\ { \text{let } 100a + 10b + c = abc } \\ { \Rightarrow abc + 4d } \end{align*}$$

In other words, $abcd$ is divisible by 13, if and only if, $abc + 4d$ is divisible by 13, thus deriving the rule.

To demonstrate its applicability when $n = 4 - 13 = -9$, we simply subtract and add 27 ($3 \times 9$) instead of first adding and subtracting 12 ($3 \times 4$), as demonstrated above:

$$\begin{align*} { 1000a + 100b + 10c + d } \\ { 1000a \hi{+ 300a} + 100b \hi{+ 30b} + 10c \hi{+ 3c} + d \hi{- 27d} \hi{- 300a} \hi{- 30b} \hi{- 3c} \hi{+ 27d} } \\ { \hi{1300a} \hi{+ 130b} \hi{+ 13c} \hi{- 26d} - 300a - 30b - 3c + 27d } \\ { \hi{13 \left( 100a + 10b + c - 2d \right) } \hi{- 3 \left( 100a + 10b + c - 9d \right) } } \end{align*}$$

Once again, the first term is divisible by 13 since 13 is a factor of that term. While the second term has the factor 3, which is not divisible by 13, the sum of the terms inside the parentheses must be divisible by 13 for the entire expression to be divisible by 13.

$$\begin{align*} { 100a + 10b + c - 9d } \\ { \text{let } 100a + 10b + c = abc } \\ { \Rightarrow abc - 9d } \end{align*}$$

In other words, abcd is divisible by 13, if and only if, $abc - 9d$ is divisible by 13, thus deriving the second rule.