A divisibility test is a mentally applicable test to discern whether one number divides by another without a remainder. Summing the digits and long division are two examples of divisibility tests, although they widely differ in their difficulty level; dividing one number by the other on a calculator is not considered a divisibility test, because it relies on an external aid.
Dozenal is a number base with many divisibility tests available, most of them trivial, because of the richness of the base in divisors. Compared to decimal, dozenal relies almost exclusively on its divisor (2, 3, 4, 6, 10) and regular (power-divisor) relationships (i.e. 3-smooth numbers, such as 8 and 9), which in decimal are relatively few, while in dozenal one has little use of the two tests derived from the neighbours of the base (E and 11), instead having two tests (5 and 25) based on the square-neighbor 101 (gross and one), and having two tests (7 and 17) based on the cube-neighbor 1001 (great-gross and one).
Contents
Practical Tests[edit | edit source]
In this section we consider only the tests that are likely to be needed in real life in a dozenal civilisation. Testing for divisibility by the following numbers will probably be useful: the binary powers 2, 4, 8, 14, 28, 54, X8; the ternary powers 3, 9, 23, 69; the co-prime 5, 7, E, 11. Testing for binary divisibility is useful for knowing how many times a quantity can be halved successively; trisection is also of use, hence the test for 3, although being able to trisect more than once is rarely needed; finally, 5 and 7 are sometimes needed for quintile and septile division, where there is a middle between the middle and each of the two extremes.
The dozenal tests, however, are not ordered by the above sequence, but according to their relationship to the base: divisors, non-divisor regular numbers, the power-neighbour test for 5, 7 and compound tests.
Divisor Tests[edit | edit source]
These tests are trivial, involving just a glance at the last digit:
- Divisible by 2 if the number ends in 0, 2, 4, 6, 8 or X.
- Divisible by 3 if the number ends in 0, 3, 6 or 9.
- Divisible by 4 if the number ends in 0, 4 or 8.
- Divisible by 6 if the number ends in 0 or 6.
- Divisible by 10 if the number ends in 0.
Those rules can be extended to multiples of the base. For example, a number is divisible by 20 if the last digit is 0 and the second-last digit is 0, 2, 4, 6, 8 or X.
Non-Divisor Regular Tests[edit | edit source]
Regular numbers divide the higher powers of 10, not 10 itself. For example, 8, 9 and 14 are divisors of 100. Their tests involve checking as many digits as the power of 10 they divide by (therefore, two digits in the case of 8, 9 and 14); those sequences of multiple-digit numbers are either few enough to be memorised, or they can be derived by a rule from a memory-based test.
- A number is divisible by 8 if one of two conditions holds:
- The second-last digit is 0, 2, 4, 6, 8 or X and the last digit is 0 or 8.
- The second-last digit is 1, 3, 5, 7, 9 or E and the last digit is 4.
- A number is divisible by 9 if one of three conditions holds:
- The second-last digit is 0, 3, 6 or 9 and the last digit is 0 or 9.
- The second-last digit is 1, 4, 7 or X and the last digit is 6.
- The second-last digit is 2, 5, 8 or E and the last digit is 3.
- A number is divisible by 14 if the last two digits are 00, 14, 28, 40, 54, 68, 80, 94 or X8.
Dozenal Test for 5[edit | edit source]
This is a test that works two digits at a time, because it is based on the relationship to the square of the base; see the Theory section for details. The test is informally called SPD, standing for 'Split, Promote, Discard', which are the three main steps involved.
The following steps are taken to test a number for divisibility by 5:
- The last two digits are split away from all the rest, giving a left-hand number and a right-hand number.
- The right-hand number is promoted to a two-digit multiple of 5 through addition or subtraction. For example, 25 can be promoted to 26 (adding 1), 73 can be promoted to 71 (subtracting 2), and 1E can be promoted to 2E (adding 10).
- The same operation as in the previous step is performed on the left-hand number. For instance, if in the previous step we subtracted 2 from the right-hand number, we now subtract 2 from the left-hand number.
- The right-hand number is discarded, and all the steps are redone on the remaining number (that is, it is split into two, the right-hand number is promoted, and so on).
- Once it is impossible to shorten the number any further (when one is left with a number having one or two digits), the check is complete: if the remaining number divides by 5, then so does the original number, and if it does not divide by 5, then neither does the original number.
Testing the number 23XX93854 will serve as an example:
- Split the number into two: 23XX938 and 54.
- Promote the right-hand number: 54 → 55, by adding 1.
- Perform the same operation on the left-hand number: 23XX938 → 23XX939, by adding 1.
- Discard the right-hand number, giving a new number to begin the operations on: 23XX939.
- Split the number into two: 23XX9 and 39.
- In this case the right-hand number is already a multiple of 5, so we can obtain the new number straight away: 23XX9.
- Split the number into two: 23X and X9.
- Promote the right-hand number: X9 → XX, by adding 1.
- Perform the same operation on the left-hand number: 23X → 23E, by adding 1.
- Discard the right-hand number, giving a new number to begin the operations on: 23E.
- Split the number into two: 2 and 3E.
- Promote the right-hand number: 3E → 39, by subtracting 2.
- Perform the same operation on the left-hand number: 2 → 0, by subtracting 2.
- Discard the right-hand number. This gives 0, which can no longer be shortened. 0 is a multiple of 5, so 23XX93854 is divisible by 5.
Here is an animated illustration of the SPD test:
Dozenal Test for 7[edit | edit source]
This is a test that works three digits at a time, because it is based on the relationship to the cube of the base; see the Theory section for details. The test is informally called SPD, standing for 'Split, Promote, Discard', which are the three main steps involved.
The following steps are taken to test a number for divisibility by 7:
- The last three digits are split away from all the rest, giving a left-hand number and a right-hand number.
- The right-hand number is promoted to a three-digit multiple of 7 through addition or subtraction. For example, 138 can be promoted to 139 (adding 1), 597 can be promoted to 595 (subtracting 2), and 321 can be promoted to 331 (adding 10).
- The same operation as in the previous step is performed on the left-hand number. For instance, if in the previous step we subtracted 2 from the right-hand number, we now subtract 2 from the left-hand number.
- The right-hand number is discarded, and all the steps are redone on the remaining number (that is, it is split into two, the right-hand number is promoted, and so on).
- Once it is impossible to shorten the number any further (when one is left with a number having one or two digits), the check is complete: if the remaining number divides by 7, then so does the original number, and if it does not divide by 7, then neither does the original number.
Compound Tests[edit | edit source]
The test for 5 can be combined with the divisor and regular tests so as to test for divisibility by numbers such as X, 13 and 18. X is 2·5, so a number that passes the test for 5 and ends in 0, 2, 4, 6 or 8 is divisible by X; similarly, a number passing the divisor test for 3 (or 4) and the test for 5 is divisible by 13 (or 18).
The test for 7 can be combined with the divisor and regular tests so as to test for divisibility by numbers such as 12 and 19. 12 is 2·7, so a number that passes the test for 7 and ends in 0, 2, 4, 6 or 8 is divisible by 12; similarly, a number passing the divisor test for 3 and the test for 7 is divisible by 19.
Divisibility Tests of Numbers 1 to 20[edit | edit source]
1
Any integer is divisible by 1.
2
If a number is divisible by 2 then the unit digit of that number will be 0, 2, 4, 6, 8 or X.
3
If a number is divisible by 3 then the unit digit of that number will be 0, 3, 6 or 9.
4
If a number is divisible by 4 then the unit digit of that number will be 0, 4 or 8.
5
To test for divisibility by 5, double the units digit and subtract the result from the number formed by the rest of the digits. If the result is divisible by 5 then the given number is divisible by 5.
This rule comes from 21(5*5)
Examples: 13 rule => |1-2*3| = 5 which is divisible by 5. 2EX5 rule => |2EX-2*5| = 2E0(5*70) which is divisible by 5(or apply the rule on 2E0).
OR
To test for divisibility by 5, subtract the units digit and triple of the result to the number formed by the rest of the digits. If the result is divisible by 5 then the given number is divisible by 5.
This rule comes from 13(5*3)
Examples: 13 rule => |3-3*1| = 0 which is divisible by 5. 2EX5 rule => |5-3*2EX| = 8E1(5*195) which is divisible by 5(or apply the rule on 8E1).
OR
Form the alternating sum of blocks of two from right to left. If the result is divisible by 5 then the given number is divisible by 5.
This rule comes from 101, since 101 = 5*25, thus this rule can be also tested for the divisibility by 25.
Example:
97,374,627 => 27-46+37-97 = -7E which is divisible by 5.
6
If a number is divisible by 6 then the unit digit of that number will be 0 or 6.
7
To test for divisibility by 7, triple the units digit and add the result to the number formed by the rest of the digits. If the result is divisible by 7 then the given number is divisible by 7.
This rule comes from 2E(7*5)
Examples: 12 rule => |3*2+1| = 7 which is divisible by 7. 271E rule => |3*E+271| = 29X(7*4X) which is divisible by 7(or apply the rule on 29X).
OR
To test for divisibility by 7, subtract the units digit and double the result from the number formed by the rest of the digits. If the result is divisible by 7 then the given number is divisible by 7.
This rule comes from 12(7*2)
Examples: 12 rule => |2-2*1| = 0 which is divisible by 7. 271E rule => |E-2*271| = 513(7*89) which is divisible by 7(or apply the rule on 513).
OR
To test for divisibility by 7, 4 times the units digit and subtract the result from the number formed by the rest of the digits. If the result is divisible by 7 then the given number is divisible by 7.
This rule comes from 41(7*7)
Examples: 12 rule => |4*2-1| = 7 which is divisible by 7. 271E rule => |4*E-271| = 235(7*3E) which is divisible by 7(or apply the rule on 235).
OR
Form the alternating sum of blocks of three from right to left. If the result is divisible by 7 then the given number is divisible by 7.
This rule comes from 1001, since 1001 = 7*11*17, thus this rule can be also tested for the divisibility by 11 and 17.
Example:
386,967,443 => 443-967+386 = -168 which is divisible by 7.
8
If the 2-digit number formed by the last 2 digits of the given number is divisible by 8 then the given number is divisible by 8.
Example: 1E48, 4120
rule => since 48(8*7) divisible by 8, then 1E48 is divisible by 8.
rule => since 20(8*3) divisible by 8, then 4120 is divisible by 8.
9
If the 2-digit number formed by the last 2 digits of the given number is divisible by 9 then the given number is divisible by 9.
Example: 7423, 8330
rule => since 23(9*3) divisible by 9, then 7423 is divisible by 9.
rule => since 30(9*4) divisible by 9, then 8330 is divisible by 9.
X
If the number is divisible by 2 and 5 then the number is divisible by X.
E
If the sum of the digits of a number is divisible by E then the number is divisible by E (the equivalent of casting out nines in decimal).
Example: 29, 61E13
rule => 2+9 = E which is divisible by E, then 29 is divisible by E.
rule => 6+1+E+1+3 = 1X which is divisible by E, then 61E13 is divisible by E.
10
If a number is divisible by 10 then the unit digit of that number will be 0.
11
Sum the alternate digits and subtract the sums. If the result is divisible by 11 the number is divisible by 11 (the equivalent of divisibility by eleven in decimal).
Example: 66, 9427
rule => |6-6| = 0 which is divisible by 11, then 66 is divisible by 11.
rule => |(9+2)-(4+7)| = |X-X| = 0 which is divisible by 11, then 9427 is divisible by 11.
12
If the number is divisible by 2 and 7 then the number is divisible by 12.
13
If the number is divisible by 3 and 5 then the number is divisible by 13.
14
If the 2-digit number formed by the last 2 digits of the given number is divisible by 14 then the given number is divisible by 14.
Example: 1468, 7394
rule => since 68(14*5) divisible by 14, then 1468 is divisible by 14.
rule => since 94(14*7) divisible by 14, then 7394 is divisible by 14.
15
To test for divisibility by 15, 7 times the units digit and subtract the result from the number formed by the rest of the digits. If the result is divisible by 15 then the given number is divisible by 15.
16
If the 2-digit number formed by the last 2 digits of the given number is divisible by 16 then the given number is divisible by 16.
17
To test for divisibility by 17, 8 times the units digit and add the result to the number formed by the rest of the digits. If the result is divisible by 17 then the given number is divisible by 17.
OR
Form the alternating sum of blocks of three from right to left. If the result is divisible by 17 then the given number is divisible by 17.
18
If the number is divisible by 4 and 5 then the number is divisible by 18.
19
If the number is divisible by 3 and 7 then the number is divisible by 19.
1X
If the number is divisible by 2 and E then the number is divisible by 1X.
1E
To test for divisibility by 1E, double the units digit and add the result to the number formed by the rest of the digits. If the result is divisible by 1E then the given number is divisible by 1E.
20
If a number is divisible by 20 then the unit digit of that number will be 0 and the dozens digit of that number will be even number.
Groups of numbers[edit | edit source]
Numbers | Divisibility rule | Rarer using numbers (with bracket) |
1 | any number | |
2, 3, 4, 6, 10 | final digit | |
8, 9, 14, (16), (20), (30), (40), (60), (100) | final two digits | Not prime power |
5, 7, (17), (25) | alternating sum of blocks (two for 5 and 25, three for 7 and 17) | > 10 |
E, 11 | the base ±1, (alternating) sum of the digits | |
X, 12, 13, 18, 19, (24), (26), (36) | combined of {2, 3, 4, 6} and {5, 7} | > 20 |
1X, 22, (29), (33), (38), (44), (56), (66) | combined of {2, 3, 4, 6} and {E, 11} | For {3, 4, 6} and {E, 11} |
(34), (39), (48), (53) | combined of {8, 9} and {5, 7} | All |
(50), (70) | combined of 10 and {5, 7} | All |
(2E) | combined of 5 and 7 | 2E = 5 * 7 is rarer to use |
23, 28, (46), 54, (80), (90) | final three digits | Not prime power |
69, X8 | final four digits | |
1E | add twice the last digit to the rest | |
(21) | subtract twice the last digit from the rest | 21 = 5^{2} (not prime, but a square of a prime not dividing 10) and > 20, thus rarer than 1E (1E is prime) |
(15), (27) | harder numbers, no easy divisibility rule | No easy divisibility rule |
Finding remainder of a number[edit | edit source]
{2, 3, 4, 6, 10}: final digit
{8, 9, 14, 16, 20, 30, 40}: last two digits
{23, 28}: last three digits
5: [1, 2, 4, 3] or [1, 2, −1, −2]
7: [1, 5, 4, 6, 2, 3] or [1, −2, −3, −1, 2, 3]
E: sum of digits
11: alternating sum of digits
17: [1, −7, −8, −1, 7, 8]
25: [1, 10, −1, −10]
Theory[edit | edit source]
So far this has been largely a guide to the most useful divisibility tests in dozenal. Now the number theory behind the tests, in dozenal as well as in other bases, will be explained.
There are universal divisibility tests for a number, such that divisibility by 7 (for instance) can be tested in any base, even in one having no useful relationship to the number 7. The really handy tests, however, are the fortuitous divisibility tests, those based on the relationships a number base happens to have: the divisor and neighbour relationships. All the dozenal divisibility tests described above are fortuitous tests.
The fortuitous tests are of two main classes: modulo 0 tests and modulo ±1 tests. The modulo is the remainder after dividing by the number: the modulo 0 tests are those of numbers that leave no remainder when 10 or one of its powers is divided by them (example: 100/14 = 9 without a remainder, 1000/23 = 54 without a remainder, 1000/28 = 46 without a remainder), while the modulo ±1 tests leave a remainder of 1 or −1 (examples: 10/E = 1 with a remainder of 1; 100/5 = 25 with a remainder of −1, 1000/7 = 187 with a remainder of −1). The crucial difference for divisibility testing is that modulo 0 tests scale up until they are no longer practicable, while modulo ±1 tests scale down by inheritance.
So, in dozenal, the tests for binary powers go up until neither memorisation nor deriving a rule (range folding) is possible: 2 and 4 are divisors; the rule for 8 is range folded from the rule for 4; 14 has few enough two-digit multiples to be memorised; the rule for 28 is range folded from the rule for 14. With 54 we may already be reaching the point of diminishing returns, because there are 23 three-digit multiples to memorise; if we can handle that, we get a test for X8 through range folding. But the next binary power, 194, is out of reach, because there are clearly too many four-digit multiples to memorise (69 of them), and we cannot do range folding from X8, because its rule is already based on range folding. There ends the range of binary-power divisibility tests in dozenal.
The dozenal test for 5 is different. It is based on the fact that 101, one more than the square of the base, is divisible by 5: 101 is 5·25, therefore 5 benefits from the relationship (as does 25, but this is such a high prime number that we have no use for it). Similarly in decimal the digit-sum test for 3 (a number is divisible by 3 if the sum of all its digits is a multiple of 3) is possible because 3 is a divisor of 9, which is one less than the base. In tetradozenal (base 14), 3 and 5 both have the digit-sum test from 13 (0xF), which is one less than the base, while 9 does not have this test.
The relationships that can give usable divisibility tests, then, are:
- The divisor relationship: the number divides the base. Divisibility by it can be checked by looking at the last digit.
- The power-divisor (or non-divisor regular) relationship: the number divides a higher power (square, cube and so on) of the base. If either memorisation or range folding is possible, this relationship gives a divisibility test involving a checking of two or more final digits.
- The omega relationship, or one less than the base: testing for divisibility by the omega or one of its factors can be done by summing the digits of the tested number to see if the sum divides by the omega or its factor.
- The alpha relationship, or one more than the base: testing for divisibility by the alpha or one of its factors can be done by summing the digits of the tested number in even places, then in odd places, then subtracting the two sums to see if the difference divides by the alpha or its factor.
- The square-alpha relationship, or one more than the square of the base: if the table of multiples is not too large to be memorised, then one can test for divisibility by a factor of the square-alpha by using the SPD process.
There are a few other relationships, but they are rarely useful: the square-omega relationship (one less than the square of the base) gives the ability to test for one extra binary power in an odd base by summing pairs of digits, but odd bases are highly impractical; the cube-alpha relationship gives an SPD-like test for 7, but that test is more complex for mental application than SPD, and therefore not much more useful than applying a universal test for 7.
Outside these fortuitous relationships, the universal tests can be pressed into service when only mental calculation is at hand, although even the easiest of them are a far cry from the fortuitous tests. Examples of universal tests:
- Doing long division mentally. This is workable but taxing for most people.
- The trim-right test, which is a very general modulo ±1 test (all the others are, in fact, shortcuts of it). For example, for testing divisibility by 7 in dozenal:
- One can tear the last digit away, multiply it by 3 and add it to the other digits, successively until one gets a number known to divide by 7. This is possible because 2E, one less than 30, is a multiple of 7.
- One can tear the last digit away, multiply it by 4 and subtract it from the other digits, successively until one gets a number known to divide by 7. This is possible because 41, one more than 40, is a multiple of 7.
- The placeholder test, where the tested number is reformulated as the sum (or difference) of one known multiple and another number. For example, 492 is divisible by 7 because it is the sum of 480 and 12, both multiples of 7 (the former is 48·10, where 48 ought to be remembered from the basic dozenal multiplication table).
It is possible to test for divisibility by any number by some effort; how much effort is exactly the issue that determines whether it is practical. Dozenal has tests for divisibility by more numbers than the ones outlined in the first part of the article, but those are either too difficult to apply, or useless in practical situations, or both. Let us survey them now.
Other Tests[edit | edit source]
The dozenal divisibility tests that would probably be missed out in schools in a dozenal civilisation are those for 28, 54, X8, 23, 69, 16, 46, E, 11, 25 and 17 (the tests for 20, 30, 40, ..., 100 are "the numbers end with 0 and the numbers form by the preceding digits are divisible by 2, 3, 4, ..., 10"). Although all of them are within reach of mental application, they would rarely be considered worth the effort.
Here is a short survey of the additional regular tests and why they would be academic in a real dozenal setting:
- 28 and 54 requires memorizing the two-digit multiples of 14 (X8 requires memorizing the three-digit multiples of 54) and applying range folding to them. The requirements are not onerous, but when one considers that 14 itself is not particularly useful in divisibility testing, then this applies more so to 28, 54 and X8. The law of diminishing returns works against expending the effort required to be able to test for divisibility by the fifth, sixth and seventh binary powers; the first four are quite enough.
- A number is divisible by 28 if one of two conditions holds:
- The third-last digit is 0, 2, 4, 6, 8 or X and the last two digits are 00, 28, 54, 80 or X8 (that is, 14 multiplied by an even number).
- The third-last digit is 1, 3, 5, 7, 9 or E and the last two digits are 14, 40, 68 or 94 (that is, 14 multiplied by an odd number).
- A number is divisible by 54 if one of two conditions holds:
- The third-last digit is 0, 4 or 8 and the last two digits are 00, 54 or X8 (a multiple of 54).
- The third-last digit is 1, 5 or 9 and the last two digits are 40 or 94 (14 less than a multiple of 54).
- The third-last digit is 2, 6 or X and the last two digits are 28 or 80 (an odd multiple of 28).
- The third-last digit is 3, 7 or E and the last two digits are 14 or 68 (14 more than a multiple of 54).
- 23 requires memorizing the two-digit multiples of 9 (69 requires memorizing the three-digit multiples of 23) and applying range folding to them. The requirements are not onerous, but when one considers that 9 itself is not particularly useful in divisibility testing, then this applies more so to 23 and 69. Adding ternary powers does not have the same appeal as adding binary powers.
- A number is divisible by 23 if the third-last digit is 0, 3, 6 or 9 and the last two digits are 00, 23, 46, 69, 90 or E3 (a multiple of 23).
- Or if the third-last digit is 1, 4, 7 or X and the last two digits are 16, 39, 60, 83 or X6 (9 less than a multiple of 23).
- Or if the third-last digit is 2, 5, 8 or E and the last two digits are 09, 30, 53, 76 or 99 (9 more than a multiple of 23).
- 16 has a memory-based test, checking the last two digits as with 14. Unlike 14, however, there is little practical need to test for divisibility by 16 (for the same reason as 9). And so it is with 46, whose test is range folded from that of 16 much as the test for 23 is from the test for 9.
- A number is divisible by 16 if its last two digits are 00, 16, 30, 46, 60, 76, 90 or X6.
- A number is divisible by 46 if the third-last digit is 0, 3, 6 or 9 and the last two digit are 00, 46 or 90 (a multiple of 46).
- Or if the third-last digit is 1, 4, 7 or X and the last two digits are 16, 60 or X6 (16 more than a multiple of 46).
- Or if the third-last digit is 2, 5, 8 or E and the last two digits are 30 or 76 (16 less than a multiple of 46).
Then there are the base-neighbour tests, those for E and 11. The rule for the former is the same as that of 3 and 9 in decimal: sum the digits, check if the sum is a multiple (of E in this case). There, however, the similarity ends: where in decimal the digit-sum test for 3 is heavily used, because 3 is a highly practical number, in dozenal this test applies to the high, useless prime E; and because E is prime, no other number inherits the test from it. The same remarks on the lack of practical utility go for 11, another high prime, even though its test is the harder one of the two base-neighbour tests, where digits in alternate places are summed and the difference of the two sums is checked. This test is useful neither in dozenal nor in decimal, as it applies to a high prime in both; it would be useful in a base such as 8 (octal, where it is the rule of 3 and 9) and 12 (unbinal, where it applies to 3 and 5).
25 also has an SPD test for 5, inheriting it from 101 just as 5 does. The observation that this test is useless because such a high prime is useless is again made, in addition to remarking that the SPD test for 25 is more operationally complex than that of 5 because one often needs to add or subtract high numbers in order to promote the right-hand number to a multiple of 25 at each turn (with the SPD test for 5 you need never add or subtract more than 2, although at your discretion there is no problem doing so).
17 also has an SPD test for 7, inheriting it from 1001 just as 7 does. The observation that this test is useless because such a high prime is useless is again made, in addition to remarking that the SPD test for 17 is more operationally complex than that of 7 because one often needs to add or subtract high numbers in order to promote the right-hand number to a multiple of 17 at each turn (with the SPD test for 7 you need never add or subtract more than 3, although at your discretion there is no problem doing so).
Summary[edit | edit source]
Dozenal is chock-full of practical divisibility tests, nearly all of them relying on its modulo 0 relationships (divisor and non-divisor regular numbers); the test for 5 relies on its relationship to the gross. Coming from the decimal world, one has the unpleasant surprise of learning that the indispensible digit-sum test is useless, while having to get used to an unusual test for 5; but all this is more than compensated for by the other tests, which include an at-a-glance test for 3 and the ability to test for five binary powers (whereas in decimal even the third binary power, 8, comes at the extra cost of memorising all the two-digit multiples of 4, and that is the highest binary power testable).
The article is indebted to the work of Michael T DeVlieger, editor of the DSA Bulletin, whose number theory terminology is in extensive use on these topics. See also his DSA Dozenal FAQs for the case for dozenalism from the point of view of number theory.
Non-obvious composites[edit | edit source]
The "compositeness" of these numbers is not obvious right away or deducible by mere inspection, and hence these terms readily lend themselves to be (erroneously) suspected as primes to the casual glance.
Composite numbers ending in 1, 5, 7 or E, not perfect powers, with digital root not E and whose alternate digit sums do not differ by a multiple of 11, and with no common factor >1 (in fact, such common factor >1 can only be 5 or 7) of the digits of n.
These numbers are composite numbers that are neither (divisible by 2, 3, E or 11) (perfect power) (5-repdigit) (7-repdigit) (numbers using only digits 5 and X), such numbers are:
2E, 71, 7E, 97, 9E, E1, 101, 10E, 115, 127, 135, 14E, 151, 15E, 161, 177, 185, 197, 1X1, 1EE, 207, 211, 215, 22E, 235, 23E, 257, 265, 26E, 287, 28E, 2X5, 2X7, 2E5, 2E7, 305, 311, 331, 337, 345, 351, 355, 361, 367, 36E, 37E, 387, 395, 39E, 3X1, 3E1, 3EE, 405, 411, 417, 43E, 445, 44E, 467, 475, 477, 487, 491, 49E, 4X1, 4X7, 4XE, 4E5, 501, 50E, 521, 525, 52E, 537, 547, 54E, 55E, 567, 571, 57E, 581, 595, 597, 5XE, 601, 60E, 621, 625, 627, 62E, 631, 635, 645, 651, 657, 667, 677, 67E, 685, 691, 6X1, 6X5, 6XE, 6E7, 6EE, 715, 725, 72E, 73E, 741, 755, 757, 761, 765, 78E, 795, 79E, 7X7, 7XE, 7E1, 7E5, 7E7, 807, 811, 815, 81E, 831, 837, 845, 847, 84E, 857, 875, 87E, 885, 887, 897, 89E, 8X1, 8E1, 8EE, 917, 925, 931, 935, 93E, 941, 945, 947, 94E, 951, 957, 96E, 975, 977, 981, 98E, 991, 997, 99E, 9X5, 9E7, X15, X21, X2E, X31, X51, X61, X65, X67, X71, X7E, X81, X85, X97, XX1, XE5, E01, E05, E07, E17, E27, E3E, E41, E4E, E51, E55, E5E, E75, E77, E7E, E85, E87, E8E, EX7, EXE, EE1, ...
(I think you remember the squares of 1 to 20, and the cubes of 1 to 10, thus the list may be added with the numbers 21^{2}, 25^{2}, 27^{2}, 2E^{2}, 31^{2} and 35^{2})
(of course, if you remember the dozenal 10×10 multiplication table (i.e. 1×1, 1×2, 1×3, ..., through 10×10), then you can eliminate the number 2E=5×7)
Many of these numbers are multiples of 5 or 7, or both.
Non-examples:
All composites end with 0, 2, 3, 4, 6, 8, 9 or X are easily known to be composite.
All composites with digital root E are easily known to be composite.
All composites with alternate digit sums differ by a multiple of 11 are easily known to be composite.
21 = 5^{2}, thus you can easily to know that it is composite.
41 = 7^{2}, thus you can easily to know that it is composite.
441 = 5^{4}, thus you can easily to know that it is composite.
247 = 7^{3}, thus you can easily to know that it is composite.
1985 = 5^{5}, thus you can easily to know that it is composite.
1481 = 7^{4}, thus you can easily to know that it is composite.
201 = 15^{2}, thus you can easily to know that it is composite.
261 = 17^{2}, thus you can easily to know that it is composite.
381 = 1E^{2}, thus you can easily to know that it is composite.
555, 55555, 5555555 and 555555555 are easily to known that they are multiples of 5.
777, 77777, 7777777 and 777777777 are easily to known that they are multiples of 7.
XX5, 55X5, 5X55, X555 and XXX5 are also easily to known that they are multiples of 5.
Compare with the divisibility rules of 5 and 7 (the only two remaining single-digit primes), we can delete all composites ≤200, however we cannot delete the next number 201.
Table[edit | edit source]
Suppose you have a number n that you wish to check for divisibility by d.
Ending digits: the number of ending digits of n to check for divisibility by d.
Add blocks: take the digits of n in blocks of the given length, and add them (or add and subtract alternately) starting from the right. d | n iff d divides the result.
Right trim 1: remove the rightmost digit of n, multiply it by the number in the column, and add that to the remaining digits of n. d | n iff d divides the result.
Right trim 2: like above, but remove the two rightmost digits of n.
Left trim 1: remove the leftmost digit of n, multiply it by the given number, shift in two places to the right, and add to the remaining digits of n. d | niff d divides the result.
Use other tricks: apply divisibility tests for smaller divisors.
d | end digits | add blocks | right trim 1 | right trim 2 | left trim 1 | use other tricks |
---|---|---|---|---|---|---|
2 | 1 | |||||
3 | 1 | |||||
4 | 1 | |||||
5 | +-2, 4 | 3, -2 | 4, -1 | 4, -1 | ||
6 | 1 | 2, 3 | ||||
7 | +-3, 6 | 3, -4 | 2, -5 | 4, -3 | ||
8 | 2 | |||||
9 | 2 | |||||
X | 4, -6 | 2, 5 | ||||
E | 1 | 1, -X | 1, -X | 1, -X | ||
10 | 1 | 3, 4 | ||||
11 | +-1, 2 | 10, -1 | 1, -10 | 1, -10 | ||
12 | 4, -X | 2, 7 | ||||
13 | 9, -6 | 3, 5 | ||||
14 | 2 | |||||
15 | +-8 | X, -7 | -2 | 8, -9 | ||
16 | 2 | 2, 9 | ||||
17 | +-3, 6 | 8, -E | 7, -10 | E, -8 | ||
18 | 4 | 4, 5 | ||||
19 | -3 | 3, 7 | ||||
1X | 10, -X | 2, E | ||||
1E | E | 2, -19 | 4 | 6 | ||
20 | 2 | 3, 8 | ||||
21 | +-X | 1E, -2 | 4 | -6 | ||
22 | -10 | 2, 11 | ||||
23 | 3 | 9 | ||||
24 | 4 | 4, 7 | ||||
25 | +-2, 4 | 15, -10 | -1 | -1 | ||
26 | -6 | 5, 6 | ||||
27 | 11, -16 | -E | ||||
28 | 3 | |||||
29 | 10 | 3, E | ||||
2X | 8 | 2, 15 | ||||
2E | 10 | 3 | 9 | 4 | 5, 7 | |
30 | 2 | 4, 9 | ||||
31 | 9 | -3 | 9 | -4 | ||
32 | -8 | 2, 17 | ||||
33 | -10 | 3, 11 | ||||
34 | 5, 8 | |||||
35 | 20, -15 | 2 | ||||
36 | 6, 7 | |||||
37 | 16 | |||||
38 | 10 | 4, E | ||||
39 | 9 | 5, 9 | ||||
3X | 6 | 2, 1E | ||||
3E | 4 | 3 | ||||
40 | 2 | 3, 14 | ||||
41 | -4 | -3 | ||||
42 | -6 | 2, 21 | ||||
43 | -9 | 3, 15 | ||||
44 | -10 | 4, 11 | ||||
45 | -1X | 7 | ||||
46 | 3 | 2, 23 | ||||
47 | 4 | 1E | 5, E | |||
48 | 7, 8 | |||||
49 | 3, 17 | |||||
4X | 2, 25 | |||||
4E | 5 | |||||
50 | 5, 10 | |||||
51 | -5 | |||||
52 | 2, 27 | |||||
53 | 7, 9 | |||||
54 | 3 | |||||
55 | 5, 11 | |||||
56 | 10 | 6, E | ||||
57 | X | |||||
58 | 8 | 4, 15 | ||||
59 | 6 | 3, 1E | ||||
5X | 4 | 2, 5, 7 | ||||
5E | 6 | 2 | ||||
60 | 2 | 8, 9 | ||||
61 | -6 | -2 | ||||
62 | -4 | 2, 31 | ||||
63 | -6 | 3, 21 | ||||
64 | -8 | 4, 17 | ||||
65 | 6 | -X | 7, E | |||
66 | -10 | 6, 11 | ||||
67 | ||||||
68 | 5, 14 | |||||
69 | 4 | |||||
6X | 2, 35 | |||||
6E | 7 | |||||
70 | 7, 10 | |||||
71 | -7 | 5, 15 | ||||
72 | 2, 37 | |||||
73 | 3, 25 | |||||
74 | 8, E | |||||
75 | +-4, 8 | |||||
76 | 5, 16 | |||||
77 | +-3, 6 | -10 | 7, 11 | |||
78 | 4, 1E | |||||
79 | 3, 27 | |||||
7X | 2, 3E | |||||
7E | 10 | 8 | 5, 17 | |||
80 | 3 | 3, 28 | ||||
81 | +-8 | -8 | ||||
82 | 2, 41 | |||||
83 | 9, E | |||||
84 | 4, 21 | |||||
85 | ||||||
86 | 6, 15 | |||||
87 | -5 | |||||
88 | 8, 11 | |||||
89 | 3, 5, 7 | |||||
8X | 2, 45 | |||||
8E | 9 | |||||
90 | 3 | 4, 23 | ||||
91 | -9 | |||||
92 | 2, 5, E | |||||
93 | 3, 31 | |||||
94 | 7, 14 | |||||
95 | ||||||
96 | 6, 17 | |||||
97 | 4 | 5, 1E | ||||
98 | 4, 25 | |||||
99 | 9, 11 | |||||
9X | 2, 4E | |||||
9E | X | 7, 15 | ||||
X0 | 5, 20 | |||||
X1 | -X | |||||
X2 | 2, 51 | |||||
X3 | 3, 35 | |||||
X4 | 4, 27 | |||||
X5 | ||||||
X6 | 7, 16 | |||||
X7 | ||||||
X8 | 4 | |||||
X9 | 3, 37 | |||||
XX | 2, 5, 11 | |||||
XE | E | -X | ||||
E0 | 10 | E, 10 | ||||
E1 | +-3, 6 | -E | -10 | E | 7, 17 | |
E2 | X | 2, 57 | ||||
E3 | 9 | 5, 23 | ||||
E4 | 8 | 8, 15 | ||||
E5 | 7 | |||||
E6 | 6 | 6, 1E | ||||
E7 | 5 | |||||
E8 | 4 | 4, 5, 7 | ||||
E9 | 3 | 3, 3E | ||||
EX | 2 | 2, 5E | ||||
EE | 2 | 10 | 1 | 1 | E, 11 | |
100 | 2 | 9, 14 |