Divisibility theorems and fraction flipping

Chris Noxz

September 21, 2019

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

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:

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.

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.

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:

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.

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.

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:

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.

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.

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:

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.

Divisibility by 6

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

Note: 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 & 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:

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.

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

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

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:

Subtract 21b from the whole equation, and factorize:

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,

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.

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,

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.

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

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:

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.

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.

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:

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.

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,

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:

Now we factorize the expression, like so:

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.

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:

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.

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

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

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:

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

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,

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:

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

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.

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

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

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:

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

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,

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

Recursive 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

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:

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. The divisibility rule for the prime number 5: is the last digit a 5 or a 0?

   

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

   

4. A way to calculate D(n):

   

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

   

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

Find out if 87614 is divisible by 71:

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 as, bs, cs and ds so that we can deduce the circumstances under which divisibility by 13 is possible.

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.

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 × 9) instead of first adding and subtracting 12 (3 × 4), as demonstrated above:

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.

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

Fractions

The fraction flip when dividing

Many of you have probably been taught the trick of flipping the right fraction in a division to instead use simpler multiplication. This is how it works:

We start with the division:

From there, we can reconstruct the two fractions as the dividend over the divisor with a horizontal line, for simplicity’s sake, like so:

After that, the "trick" can begin. First, we multiply both the dividend and the divisor with the inverse of the divisor. As long as we treat the dividend and the divisor the same way, this is fine. However, keep PEMDAS in mind! If any of the dividend or the divisor would have been an addition or subtraction, you would have to multiply both terms by x, either by x(a + b) or xa + xb.

As you can see, the right fraction has now "flipped", and not by magic, but with logic and reason. So, as division by 1 is equal to the dividend, we can then solve the expression, like so:

As the final cherry on top, we can prove the procedure by dividing 1 by 2, as we know this should result in one half.