commit: cc8f13ec27ee72c599e072d9a28445c4e9ef263d
parent: 8f8adf531f4d61f6bfbebbf2a0f41ab924a8c1e2
author: Chris Noxz <chris@noxz.tech>
date: Thu, 7 Dec 2023 13:58:02 +0100
update article about divisibility theorems
1 file changed, 143 insertions(+), 1 deletion(-)
diff --git a/noxz.tech/articles/divisibility_theorems_and_fraction_flipping/index.www b/noxz.tech/articles/divisibility_theorems_and_fraction_flipping/index.www
@@ -50,6 +50,14 @@
.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-alt "Alternative way of deriving recursive divisibility algorithms"
+.ULE
.LI
3
.URL #math-fractions "Fractions"
@@ -1148,6 +1156,11 @@ algorithm with divisibility by 27 using
appear to be included when I tested numbers up to 100. However, as I mentioned,
I have not algebraically proven them.
+.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:
@@ -1187,7 +1200,7 @@ for div in range(1, 100):
# 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)
+ n -= div
print("{:d}: {:+d}".format(div, n))
break
.COE
@@ -1195,6 +1208,135 @@ for div in range(1, 100):
Happy hunting!
+.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.
+
+.EQ
+lpile {
+{ 1000a ~+~ 100b ~+~ 10c ~+~ d }
+above
+{ 1000a hi{~+~ 300a} ~+~ 100b hi{~+~ 30b} ~+~ 10c hi{~+~ 3c} ~+~ d hi{~+~ 12d}
+ hi{~-~ 300a} hi{~-~ 30b} hi{~-~ 3c} hi{~-~ 12d}
+}
+above
+{ hi{1300a} hi{~+~ 130b} hi{~+~ 13c} hi{~+~ 13d}
+ ~-~ 300a ~-~ 30b ~-~ 3c ~-~ 12d
+}
+above
+{ hi{13 left ( 100a ~+~ 10b ~+~ c ~+~ d right ) }
+ hi{~-~ 3 left ( 100a ~+~ 10b ~+~ c ~+~ 4d right ) }
+}
+}
+.EN
+
+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.
+
+.EQ
+lpile {
+{ 100a ~+~ 10b ~+~ c ~+~ 4d }
+above
+{ roman{let}~ 100a ~+~ 10b ~+~ c = abc }
+above
+{ implies~ abc ~+~ 4d }
+}
+.EN
+
+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:
+
+.EQ
+lpile {
+{ 1000a ~+~ 100b ~+~ 10c ~+~ d }
+above
+{ 1000a hi{~+~ 300a} ~+~ 100b hi{~+~ 30b} ~+~ 10c hi{~+~ 3c} ~+~ d hi{~-~ 27d}
+ hi{~-~ 300a} hi{~-~ 30b} hi{~-~ 3c} hi{~+~ 27d}
+}
+above
+{ hi{1300a} hi{~+~ 130b} hi{~+~ 13c} hi{~-~ 26d}
+ ~-~ 300a ~-~ 30b ~-~ 3c ~+~ 27d
+}
+above
+{ hi{13 left ( 100a ~+~ 10b ~+~ c ~-~ 2d right ) }
+ hi{~-~ 3 left ( 100a ~+~ 10b ~+~ c ~-~ 9d right ) }
+}
+}
+.EN
+
+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.
+
+.EQ
+lpile {
+{ 100a ~+~ 10b ~+~ c ~-~ 9d }
+above
+{ roman{let}~ 100a ~+~ 10b ~+~ c = abc }
+above
+{ implies~ abc ~-~ 9d }
+}
+.EN
+
+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
