commit: 8f8adf531f4d61f6bfbebbf2a0f41ab924a8c1e2
parent: d6da6302647471c03d68f0020488bff96e521b97
author: Chris Noxz <chris@noxz.tech>
date: Thu, 7 Dec 2023 11:01:11 +0100
add new rules to divisibility article
2 files changed, 467 insertions(+), 3 deletions(-)
diff --git a/noxz.tech/articles/divisibility_theorems_and_fraction_flipping/.edit b/noxz.tech/articles/divisibility_theorems_and_fraction_flipping/.edit
@@ -0,0 +1,4 @@
+START 2023-12-06
+ Added Divisibility rules for 13 and 17
+ Added a section about recursive divisibility algorithms
+END
diff --git a/noxz.tech/articles/divisibility_theorems_and_fraction_flipping/index.www b/noxz.tech/articles/divisibility_theorems_and_fraction_flipping/index.www
@@ -40,13 +40,22 @@
.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"
+.LI
+3
.URL #math-fractions "Fractions"
.ULS
.LI
-2.1
+3.1
.URL #math-fractions-flip "The fraction flip when dividing"
.ULE
.ULH
@@ -379,7 +388,7 @@ In order to prove the theorem, we must prove both
and
.B B .
So let's start with
-.I A .
+.B A .
If we have
.I a
-
@@ -680,7 +689,7 @@ represents the number of thousands,
the number of hundreds,
.I c
the number of tens, and the number
-.I d
+.I d .
This number can be represented as
.I a "" 1000
+
@@ -735,6 +744,457 @@ above
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:
+
+.EQ
+lpile {
+{ 13 ~|~ 76752 ~? }
+above
+{ 7675 ~+~ 2 ~times~ 4 ~=~ 7683 }
+above
+{ 768 ~+~ 3 ~times~ 4 ~=~ 780 }
+above
+{ 78 ~+~ 0 ~times~ 4 ~=~ 78 }
+above
+{ 7 ~+~ 8 ~times~ 4 ~=~ 39 }
+above
+{ 13 ~|~ 39 ~implies~ 13 ~|~ 76752 }
+}
+.EN
+
+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.
+
+.EQ
+{ a ~+~ 4b ~=~ 13k }
+.EN
+
+Multiply the whole equation by 10, and add one extra
+.I b :
+
+.EQ
+lpile {
+{ hi{10}a ~+~ hi{40}b ~=~ hi{130}k }
+above
+{ 10a ~+~ 40b hi{~+~ b} ~=~ 130k hi{~+~ b} }
+above
+{ 10a ~+~ hi{41b} ~=~ 130k ~+~ b }
+}
+.EN
+
+Now subtract
+.I b "" 40
+from each side of the equation, and try to factor out 13:
+
+.EQ
+lpile {
+{ 10a ~+~ 41b hi{~-~ 40b} ~=~ 130k ~+~ b hi{~-~ 40b} }
+above
+{ 10a hi{~+~ b} ~=~ 130k hi{~-~ 39b} }
+above
+{ 10a ~+~ b ~=~ hi{13 left ( 10k ~-~ 3b right )} }
+}
+.EN
+
+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:
+
+.EQ
+{ 10a ~+~ b ~=~ 13k }
+.EN
+
+Add
+.I b "" 39
+to both sides of the equation, and factorize:
+
+.EQ
+lpile {
+{ 10a ~+~ b hi{~+~ 39b} ~=~ 13k hi{~+~ 39b} }
+above
+{ 10a hi{~+~ 40b} ~=~ 13k ~+~ 39b }
+above
+{ hi{10 left ( a ~+~ 4b right ) } ~=~ hi{13 left ( k ~+~ 3b right ) } }
+}
+.EN
+
+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
+.EQ
+13 ~|~ ab ~iff~ 13 ~|~ a ~+~ 4b
+.EN
+.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:
+
+.EQ
+lpile {
+{ 17 ~|~ 206091 ~? }
+above
+{ 20609 ~-~ 1 ~times~ 5 ~=~ 20604 }
+above
+{ 2060 ~-~ 4 ~times~ 5 ~=~ 2040 }
+above
+{ 204 ~-~ 0 ~times~ 5 ~=~ 204 }
+above
+{ 20 ~-~ 4 ~times~ 5 ~=~ 0 }
+above
+{ 17 ~|~ 0 ~implies~ 17 ~|~ 206091 }
+}
+.EN
+
+If you are not satisfied with 0 being the numerator, here is another example:
+
+.EQ
+lpile {
+{ 17 ~|~ 2057 ~? }
+above
+{ 205 ~-~ 7 ~times~ 5 ~=~ 170 }
+above
+{ 17 ~-~ 0 ~times~ 5 ~=~ 17 }
+above
+{ 17 ~|~ 17 ~implies~ 17 ~|~ 2057 }
+}
+.EN
+
+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.
+
+.EQ
+{ a ~-~ 5b ~=~ 17k }
+.EN
+
+Multiply the whole equation by 10, and add one extra
+.I b :
+
+.EQ
+lpile {
+{ hi{10}a ~-~ hi{50}b ~=~ hi{170}k }
+above
+{ 10a ~-~ 50b hi{~+~ b} ~=~ 170k hi{~+~ b} }
+above
+{ 10a ~-~ hi{49b} ~=~ 170k ~+~ b }
+}
+.EN
+
+Now add
+.I b "" 50
+to each side of the equation, and try to factor out 17:
+
+.EQ
+lpile {
+{ 10a ~-~ 49b hi{~+~ 50b} ~=~ 170k ~+~ b hi{~+~ 50b} }
+above
+{ 10a hi{~+~ b} ~=~ 170k hi{~+~ 51b} }
+above
+{ 10a ~+~ b ~=~ hi{17 left ( 10k ~+~ 3b right )} }
+}
+.EN
+
+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:
+
+.EQ
+{ 10a ~+~ b ~=~ 17k }
+.EN
+
+Subtract
+.I b "" 51
+from both sides of the equation, and factorize:
+
+.EQ
+lpile {
+{ 10a ~+~ b hi{~-~ 51b} ~=~ 17k hi{~-~ 51b} }
+above
+{ 10a hi{~-~ 50b} ~=~ 17k ~+~ 51b }
+above
+{ hi{10 left ( a ~-~ 5b right ) } ~=~ hi{17 left ( k ~-~ 3b right ) } }
+}
+.EN
+
+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
+.EQ
+17 ~|~ ab ~iff~ 17 ~|~ a ~-~ 5b
+.EN
+.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
+
+.EQ
+abcd -> abc ~+~ d times n
+.EN
+
+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:
+
+.EQ
+lpile {
+{7 ~|~ abcd ~iff~ 7 ~|~ abc -2 times d}
+above
+{13 ~|~ abcd ~iff~ 13 ~|~ abc +4 times d}
+above
+{17 ~|~ abcd ~iff~ 17 ~|~ abc -5 times d}
+}
+.EN
+
+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 know to be correct, including 11, are:
+
+.CDS
+.COS
+7: -2
+11: -1
+13: +4
+17: -5
+19: +2
+23: +7
+.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
+appear to be included when I tested numbers up to 100. However, as I mentioned,
+I have not algebraically proven them.
+
+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 len(str(num)) > 1:
+ # 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 - n)
+ print("{:d}: {:+d}".format(div, n))
+ break
+.COE
+.CDE
+
+Happy hunting!
+
.HnS 1
.TAG "math-fractions"
Fractions
