noxz-sites A collection of a builder and various scripts creating the noxz.tech sites
	git clone https://noxz.tech/git/noxz-sites.git
	Log | Files | README | LICENSE

.\".fam C

.DIVS toc
.SPAN toc-title Contents
.ULS
.LI
1
.URL #math-div-theorems "Divisibility theorems"
.ULS
.LI
1.1
.URL #math-div-theorems-1 "Divisibility by 1"
.LI
1.2
.URL #math-div-theorems-2 "Divisibility by 2"
.LI
1.3
.URL #math-div-theorems-3 "Divisibility by 3"
.LI
1.4
.URL #math-div-theorems-4 "Divisibility by 4"
.LI
1.5
.URL #math-div-theorems-5 "Divisibility by 5"
.LI
1.6
.URL #math-div-theorems-6 "Divisibility by 6"
.LI
1.7
.URL #math-div-theorems-7 "Divisibility by 7"
.LI
1.8
.URL #math-div-theorems-8 "Divisibility by 8"
.LI
1.9
.URL #math-div-theorems-9 "Divisibility by 9"
.LI
1.10
.URL #math-div-theorems-10 "Divisibility by 10"
.LI
1.11
.URL #math-div-theorems-11 "Divisibility by 11"
.LI
1.13
.URL #math-div-theorems-13 "Divisibility by 13"
.LI
1.17
.URL #math-div-theorems-17 "Divisibility by 17"
.ULE
.LI
2
.URL #math-rec-div-alg "Recursive divisibility algorithms"
.ULS
.LI
2.1
.URL #math-rev-div-alg-script "Python script for finding recursive divisibility algorithms"
.LI
2.2
.URL #math-rev-div-alg-find "Finding all divisibility algorithms for primes"
.HnE
.LI
2.3
.URL #math-rev-div-alg-alt "Alternative way of deriving recursive divisibility algorithms"
.ULE
.LI
3
.URL #math-fractions "Fractions"
.ULS
.LI
3.1
.URL #math-fractions-flip "The fraction flip when dividing"
.ULE
.ULH
.DIVE

.HnS 1
.TAG "math-div-theorems"
Divisibility theorems
.HnE

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
.SPAN spoiler 2520 .
You can try the different divisibility theorems below to prove it.

.HnS 2
.TAG "math-div-theorems-1"
Divisibility by 1
.HnE

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

.DIVS theorem
.TEXS
\[ 1 \mid a \iff a \in \mathbb{Z} \]
.TEXE
.DIVE

.HnS 2
.TAG "math-div-theorems-2"
Divisibility by 2
.HnE
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
.I abcd ,
where
.I a
represents the number of thousands,
.I b
the number of hundreds,
.I c
the number of tens, and the number
.I d .
This number can be represented as
.I a "" 1000
+
.I b "" 100
+
.I c "" 10
+
.I d .
If
.I d
is divisible by 2, we can represent it as an even number
.I n , 2
like so:

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

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.

.DIVS theorem
.TEXS
\[ 2 \mid abcd \iff 2 \mid d \]
.TEXE
.DIVE

.HnS 2
.TAG "math-div-theorems-3"
Divisibility by 3
.HnE
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.

.TEXS
\[ 3 \mid abcd \iff 3 \mid \left( a + b + c + d \right) \]
.TEXE

Why is this proposition true?

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

.TEXS
\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*}
.TEXE

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
.I a
+
.I b
+
.I c
+
.I d
is divisible by 3. And so the theorem is proven.

.DIVS theorem
.TEXS
\[ 3 \mid abcd \iff 3 \mid \left( a + b + c + d \right) \]
.TEXE
.DIVE

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.

.HnS 2
.TAG "math-div-theorems-4"
Divisibility by 4
.HnE
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.

.TEXS
\[ 4 \mid abcd \iff 4 \mid cd \]
.TEXE

Why is this proposition true?

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

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

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.

.DIVS theorem
.TEXS
\[ 4 \mid abcd \iff 4 \mid cd \]
.TEXE
.DIVE

.HnS 2
.TAG "math-div-theorems-5"
Divisibility by 5
.HnE
The theorem goes that if the last digits of a number are divisible by 5, the
whole number is divisible by 5, i.e.

.TEXS
\[ 5 \mid abcd \iff 5 \mid d \]
.TEXE

Why is this proposition true?

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

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

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.

.DIVS theorem
.TEXS
\[ 5 \mid abcd \iff 5 \mid d \]
.TEXE
.DIVE

.HnS 2
.TAG "math-div-theorems-6"
Divisibility by 6
.HnE
This theorem is a combination of the theorem for
.URL #math-div-theorems-2 "divisibility by 2"
and
.URL #math-div-theorems-3 "divisibility by 3" .

.DIVS theorem
.TEXS
\[ 6 \mid abcd \iff 3 \mid \left( a + b + c + d \right) \land 2 \mid d \]
.TEXE
.DIVE

.B 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
.I 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.

.HnS 2
.TAG "math-div-theorems-7"
Divisibility by 7
.HnE
Probably one of the most useful theorems is the theorem of
.I "divisibility by 7" ,
as it is recursive (just like the theorems of
.I "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:

.TEXS
\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*}
.TEXE

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

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

.TEXS
\[ a - 2b = 7k \]
.TEXE

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

.TEXS
\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*}
.TEXE

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

.TEXS
\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*}
.TEXE

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

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

.TEXS
\[ 10a + b = 7k \]
.TEXE

Subtract
.I b "" 21
from the whole equation, and factorize:

.TEXS
\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*}
.TEXE

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
.I a
-
.I b ? 2
We now have the proof for the theorem and can conclude that, indeed,

.DIVS theorem
.TEXS
\[ 7 \mid ab \iff 7 \mid a - 2b \]
.TEXE
.DIVE

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

.HnS 2
.TAG "math-div-theorems-8"
Divisibility by 8
.HnE
The theorem is quite similar to the theorem for
.URL #math-div-theorems-4 "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.

.TEXS
\[ 8 \mid abcd \iff 8 \mid bcd \]
.TEXE

Why is this proposition true?

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

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

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.

.DIVS theorem
.TEXS
\[ 8 \mid abcd \iff 8 \mid bcd \]
.TEXE
.DIVE

.HnS 2
.TAG "math-div-theorems-9"
Divisibility by 9
.HnE
Much like the theorem for
.URL #math-div-theorems-3 "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.,

.TEXS
\[ 9 \mid abcd \iff 9 \mid \left( a + b + c + d \right) \]
.TEXE

Why is this proposition true?

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

.TEXS
\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*}
.TEXE

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
.I a
+
.I b
+
.I c
+
.I d
is divisible by 9. And so the theorem is proven.

.DIVS theorem
.TEXS
\[ 9 \mid abcd \iff 9 \mid \left( a + b + c + d \right) \]
.TEXE
.DIVE

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.

.HnS 2
.TAG "math-div-theorems-10"
Divisibility by 10
.HnE
The theorem goes that if the last digits of a number are divisible by 10, the
whole number is divisible by 10, i.e.

.TEXS
\[ 10 \mid abcd \iff 10 \mid d \]
.TEXE

Why is this proposition true?

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

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

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.

.DIVS theorem
.TEXS
\[ 10 \mid abcd \iff 10 \mid d \]
.TEXE
.DIVE

.HnS 2
.TAG "math-div-theorems-11"
Divisibility by 11
.HnE
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,

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

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

.TEXS
\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*}
.TEXE

Now we factorize the expression, like so:

.TEXS
\[ \hi{ 11 \left( 91a + 9b + c \right) } - a + b - c + d \]
.TEXE

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.

.DIVS theorem
.TEXS
\begin{align*}
{ 11 \mid abcd \iff 11 \mid -a + b - c + d }
\\
{ 11 \mid abcd \iff 11 \mid a - b + c - d }
\end{align*}
.TEXE
.DIVE

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.

.HnS 2
.TAG "math-div-theorems-13"
Divisibility by 13
.HnE
Just like the theorem of divisibility by 7,
the theorem of
.I "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:

.TEXS
\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*}
.TEXE

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

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

.TEXS
\[
a + 4b = 13k
\]
.TEXE

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

.TEXS
\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*}
.TEXE

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

.TEXS
\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*}
.TEXE

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

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

.TEXS
{ 10a + b = 13k }
.TEXE

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

.TEXS
\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*}
.TEXE

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
.I a
+
.I b ? 4
We now have the proof for the theorem and can conclude that, indeed,

.DIVS theorem
.TEXS
\[
13 \mid ab \iff 13 \mid a + 4b
\]
.TEXE
.DIVE

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

.HnS 2
.TAG "math-div-theorems-17"
Divisibility by 17
.HnE
Just like the theorem of divisibility by 7 and 13,
the theorem of
.I "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:

.TEXS
\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*}
.TEXE

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

.TEXS
\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*}
.TEXE

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

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

.TEXS
\[
a - 5b = 17k
\]
.TEXE

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

.TEXS
\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*}
.TEXE

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

.TEXS
\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*}
.TEXE

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

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

.TEXS
\[
10a + b = 17k
\]
.TEXE

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

.TEXS
\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*}
.TEXE

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
.I a
-
.I b ? 5
We now have the proof for the theorem and can conclude that, indeed,

.DIVS theorem
.TEXS
\[
17 \mid ab \iff 17 \mid a - 5b
\]
.TEXE
.DIVE

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

.HnS 1
.TAG "math-rec-div-alg"
Recursive divisibility algorithms
.HnE
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

.TEXS
\[
abcd \rightarrow abc + d \times n
\]
.TEXE

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

.TEXS
\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*}
.TEXE

Except for
.I 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
.I n
in this way:

.CDS
.COS
7: -2
13: +4
17: -5
.COE
.CDE

Divisibility by 11 could also be tested in this manner by having
.I n
= -1. However, the
.URL #math-div-theorems-11 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
.I n .
I have written a short Python script that finds all recursive divisibility
rules along with their corresponding
.I 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:

.CDS
.COS
7: -2
11: -1
13: +4
17: -5
.COE
.CDE

Before you think that the pattern is connected to prime numbers, try the
algorithm with divisibility by 27 using
.I 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...

.HnS 2
.TAG "math-rev-div-alg-script"
Python script for finding recursive divisibility algorithms
.HnE

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:

.CDS
.COS
#!/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
.COE
.CDE

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

.CDS
.COS
        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    |+
.COE
.CDE

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:
.URL https://oeis.org/A333448 https://oeis.org/A333448

.HnS 2
.TAG "math-rev-div-alg-find"
Finding all divisibility algorithms for primes
.HnE
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:
.OLS
.LI
The divisibility rule for the prime number 2: is the last digit an even number?

.TEXS
\[
2 \mid abcd \iff 2 \mid d
\]
.TEXE

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

.TEXS
\[
5 \mid abcd \iff 5 \mid d
\]
.TEXE

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

.TEXS
\[
n \mid abcd \iff n \mid abc + D(n) \times d
\]
.TEXE

.LI
A way to calculate D(n):

.TEXS
\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*}
.TEXE

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

.TEXS
\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*}
.TEXE
.OLE

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

.TEXS
\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*}
.TEXE

Find out if 87614 is divisible by 71:

.TEXS
\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*}
.TEXE

.HnS 2
.TAG "math-rev-div-alg-alt"
Alternative way of deriving recursive divisibility algorithms
.HnE

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
.I abcd .
Let me explain by deriving the rule of divisibility by 13, both for
.I n
= 4 and
.I n
= -9 (4 - 13).

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

.TEXS
\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*}
.TEXE

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.

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

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

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

.TEXS
\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*}
.TEXE

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.

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

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

.HnS 1
.TAG "math-fractions"
Fractions
.HnE

.HnS 2
.TAG "math-fractions-flip"
The fraction flip when dividing
.HnE
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:

.TEXS
\[
{ 3 \over 2 } / { 4 \over 5 }
\]
.TEXE

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

.TEXS
\[
\dfrac{3}{2} / \dfrac{4}{5}
= \dfrac{\dfrac{3}{2}}{\dfrac{4}{5}}
\]
.TEXE

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
.I x ,
either by
.I "x(a + b)"
or
.I "xa + xb" .

.TEXS
\[
\dfrac{3}{2} / \dfrac{4}{5}
= \dfrac{\dfrac{3}{2}}{\dfrac{4}{5}}
= \dfrac{\dfrac{3}{2} \hi{\times \dfrac{5}{4}}}{\dfrac{4}{5} \hi{\times \dfrac{5}{4}}}
= \dfrac{\dfrac{3}{2} \times \dfrac{5}{4}}{\hi{\dfrac{4 \times 5}{5 \times 4}}}
= \dfrac{\dfrac{3}{2} \times \dfrac{5}{4}}{\hi{\dfrac{20}{20}}}
= \dfrac{\dfrac{3}{2} \times \dfrac{5}{4}}{\hi{1}}
= \dfrac{3}{2} \times \dfrac{5}{4}
\]
.TEXE

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:

.TEXS
\[
{ 3 \over 2 } \times { 5 \over 4 }
= {{ 3 \times 5 } \over { 2 \times 4 }}
= { 15 \over 18 }
\]
.TEXE

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.

.TEXS
\[
1 / 2
= \dfrac{1}{1} / \dfrac{2}{1}
= \dfrac{\dfrac{1}{1}}{\dfrac{2}{1}}
\]
.TEXE

.TEXS
\[
\dfrac{1}{1} / \dfrac{2}{1}
= \dfrac{\dfrac{1}{1}}{\dfrac{2}{1}}
= \dfrac{\dfrac{1}{1} \hi{\times \dfrac{1}{2}}}{\dfrac{2}{1} \hi{\times \dfrac{1}{2}}}
= \dfrac{\dfrac{1}{1} \times \dfrac{1}{2}}{\hi{\dfrac{2 \times 1}{1 \times 2}}}
= \dfrac{\dfrac{1}{1} \times \dfrac{1}{2}}{\hi{\dfrac{2}{2}}}
= \dfrac{\dfrac{1}{1} \times \dfrac{1}{2}}{\hi{1}}
= \dfrac{1}{1} \times \dfrac{1}{2}
\]
.TEXE

.TEXS
\[
{ 1 \over 1 } \times { 1 \over 2 }
= {{ 1 \times 1 } \over { 1 \times 2 }}
= { 1 \over 2 }
\]
.TEXE

.DIVS theorem
.TEXS
\[
{a \over b} / {c \over d} = {a \over b} \times {d \over c}
\]
.TEXE
.DIVE