Divisibility testing methods

Shaun
Dozens Disciple
Shaun
Dozens Disciple
Joined: Aug 2 2005, 04:09 PM

Nov 26 2011, 03:53 PM #1

(Duplicate post - slightly edited - from "Dozenal" forum to start this topic - for all bases)



The factor 5.
Base twelve - rule for 5 - two digit number: double the dozens digit and addit to the units.
So, for example *2E: 2 x 2 + E = 4 + E = 13, and if you don't know 13 is a multiple of 5, reapeat test: 2 x 1 + 3 = 5. So 2E is divisible by 5.

A bit trivial; after all, we should learn the multiplication table up to *10 x *10, which takes care of all two-digit numbers!

What about more than two digits? Suppose we want to check a large number, N, for divisibility by 5.
(1) If it has an odd number of digits, put a 0 at the front so that we now have an even number of digits.
(2) When it has an even number of digits, split N into two equal parts. Subtract the smaller from the larger.
(3) If there are two digits left, apply the rule we started with. If not, go back to (a) and continue.

Example * 1239756
(1) 01239756, (2) 0123 9756. 9756 - 0123 = 9633
(1) 9633 (2) 96 33. 96 - 33 = 63
(3) 2 x 6 + 3 = 13, and we know this is divisible by 5 in base twelve.
So *1239756 is divisible by 5.

All very well and good, but where does it come from and why does it work?
It's based on power residues.

If we divide *10 by 5 we get a remainder of 2; this can be expressed as:
* 10 = 2 mod 5 (mod stands for the word modulus, and the equals sign for should have three bars here, but I can't type that here).
*100 = *10 x *10 which is 2 x 2 mod 5, or 4 mod 5, or -1 mod 5.
*1,000 = *10 x *100 or 2 x -1 = -2 mod 5
*10,000 = *10 x *1,000 = 2 x -2 = -4 (i.e. - [-1] or just 1 mod 5).
All powers of *10 mod 5 follow this pattern of 1, 2, -1, -2 ..., which explains why we can keep splitting the number N into two blocks and subtract one from the other.

What it means is that we can replace the power of twelve by its power residue mod 5 to check a number for divisibility. The number 2E is 2*10 + E * 1. We can replace the *10 by the residue 2, and this yields the rule given at the beginning.
This idea can produce methods for testing divisibility for other primes (and in other bases for which we might not be inclined to learn our 'tables' !). See the next post and the reference to a pdf on Divisibility.

[Note that the "split and subtract" idea can be applied to other primes.
Testing on a number we think might be divisible by 7.
Following the ideas above, we check to see if the number has an even number of digits. If it hasn't, put a 0 at the beginning - same as in the example for 5.
Split the number into two sections. Subtract the smaller from the larger.
Repeat the pattern (as with 5) until you're down to six digits (Add 0 if needed). Split again, and subtract again. Then there's only three digits to test.]

A word of caution.
One might be tempted to think that all tests of divisibility could become as quick as those we have demonstrated. Using residues helps, but there can be as many as (p-1)/2 different residues in the power sequence.

Here's the sequence for the power residues of twelve mod *15; there are at most *14 residues possible, but using minimal residues (positive and negative) reduces these to 8 (with change of sign). In base twelve the powers of twelve mod *15 (counting down from high power to low) are (expressed as minimal residues):
1 -7 -2 -3 4 6 -8 5 -1, 7 2 3 -4 -6 8 -5 1.
If we want to apply the "split number into two bits and subtract" idea it will work for a number of *14 digits, but once we have an eight-digit number we can't go on splitting and subtracting because the two groups of four residues are not alike.

This also applies in base ten, where the power residues of ten mod 17 are
1 -5 -8 -6 -4 -3 2 7 -1 5 8 6 4 -3 -2 -7 1.
(More to follow)
I use the following conventions for dozenal numbers in my posts.

* prefixes a dozenal number, e.g. *50 = 60.
The apostrophe (') is used as a dozenal point, e.g. 0'6 = 0.5.
T and E stand for ten and eleven respectively.
Quote
Like
Share

Shaun
Dozens Disciple
Shaun
Dozens Disciple
Joined: Aug 2 2005, 04:09 PM

Nov 27 2011, 05:06 PM #2

Quote
Like
Share

Shaun
Dozens Disciple
Shaun
Dozens Disciple
Joined: Aug 2 2005, 04:09 PM

Dec 3 2011, 02:29 PM #3

No-one interested?
Quote
Like
Share

m1n1f1g
Dozens Disciple
m1n1f1g
Dozens Disciple
Joined: Feb 20 2011, 10:15 AM

Dec 3 2011, 05:42 PM #4

All numbers dozenal.

It's interesting, but I think I'd still refrain from using the 7-divisibility rule, as I do in decimal. For 5, I have taken to your suggestion of repetitive subtraction of 101, as well as division by 10 for cases where that becomes the easiest option; namely when the grosses digit is larger than the units digit. For 4-digit numbers, I will use a mixture of the previous methods as well as the digit sums you have described, if needed. Here is one such example, which I tried when listening to the radio (all dozenal):
1215 - 202 = 1013
(1 - 1) * 2 = 0
0 + 3 = 3
0 ≢ 3 (mod 5) ∴
5∤1215

A favourable one for the non-digit-sum methods is 7452:
7452 - 202 = 7250
7250 / 10 = 725
725 - 505 = 20
5∤20 ∴ 5∤7452

I've realised now that you can also subtract multiples of 1010 since that itself is a multiple of 101. That leads to subtracting multiples of 1111 (= 11 * 101). That only works for groups of 4 digits, so you can't subtract 11, 111, 11111, ect. and expect the right answer.

In a similar way to 5, with 7 you can subtract multiples of 1001 (= 7 * 11 * 17), and thus 111111 (= 1001 * 110). Note that you can do the same thing in decimal.

Every base is either a multiple of 5 or "101" is a multiple of 5. We know that 1/5 can have a mantissa length of 1, 2 or 4. We also know that "0.a-1a-2a-3a-4" all recurring = "a-1a-2a-3a-4"/"ΩΩΩΩ", where Ω is the largest digit of the base. This covers all mantissa length cases. Since "a-1a-2a-3a-4"/"ΩΩΩΩ" = 1/5, 5∣"ΩΩΩΩ". And "ΩΩΩΩ" = "ΩΩ" * "101". If 5∤"ΩΩ", then 5∣"101". But if 5∣"ΩΩ", then 5^2∣"ΩΩΩΩ", since 4 repeating digits would be twice enough to represent 1/5, and therefore 5∣"101" still. The same logic can be applied to 5∣"Ω".

I hope that's correct and understandable.
A few little conventions:
- Dozenal integers suffixed with prime (′). This is the uncial point.
- Decimal integers suffixed with middle dot (·). This is the decimal point.

You may see me use * prefix for messages before 11Ɛ7-03-1X, and a whole range of similar radix points. I will often use X and Ɛ for :A and :B.

Sometimes, I will imply that an integer is in dozenal, so I won't add any marks to it. You should be able to tell that "10 = 22 * 3" is in dozenal.
Quote
Like
Share

icarus
Dozens Demigod
icarus
Dozens Demigod
Joined: Apr 11 2006, 12:29 PM

Dec 5 2011, 06:26 PM #5

Quote
Like
Share