Divisibility Rules

When you were younger, you probably learned to skip count by 2, 5, and 10.  Skip counting by 2 leads to the sequence 2, 4, 6, 8, 10, 12, 14, (and so on); skip counting by 5 leads to 5, 10, 15, 20, 25, 30, (and so on); and skip counting by 10 leads to 10, 20, 30, 40, 50, (and so on).  If you were an observant student, you may have noticed that all the numbers in the skip counting sequence for 10 ended in a 0, all the numbers in the skip counting sequence for 5 ended in either a 0 or 5, and all the numbers in the skip counting sequence for 2 ended in either a 0, 2, 4, 6, or 8. 

2, 5, and 10

In effect, you observed divisibility rules for 2, 5, and 10: if a number ends in 0, 2, 4, 6, or 8, then that number is divisible by 2 (or even); if a number ends in a 0 or 5, then that number is divisible by 5; and if a number ends in 0, then that number is divisible by 10. 

The reason for these simple divisibility rules for 2, 5, and 10 is because our numbering system is in base 10, which itself is divisible by 2, 5, and 10.  Mathematically, we know that 625 is divisible by 5 because 625 = 62 x 10 + 5 = 5 x (62 x 2 + 1).  In general, the number comprised of all the digits before the last one must be divisible by 10 (and also 5 and 2) because of our base 10 numbering system, which means only the last digit needs to be tested for divisibility.

4

There are also divisibility rules for other numbers that are not so obvious.  Since 4 divides into 100, if the last two digits of a number are divisible by 4, then the entire number is divisible by 4.  For example, 714,036 is divisible by 4 because the last two numbers (36) are divisible by 4.  Mathematically, 714,036 = 7140 x 100 + 36 = 7140 x 25 x 4 + 9 x 4 = 4 x (7140 x 25 + 9). 

8

Since 8 divides into 1000, if the last three digits of a number are divisible by 8, then the entire number is divisible by 8.  For example, 714,032 is divisible by 8 because the last three numbers (032) is divisible by 8.  Mathematically, 714032 = 714 x 1000 + 32 = 714 x 125 x 8 + 4 x 8 = 8 x (714 x 125 + 4).

3

Although the number 3 does not divide into any multiple of 10 like the other numbers we have looked at (2, 4, 5, 8, and 10), it does, however, divide into 9, and 99, and 999 (and so on), which are all exactly one less than a multiple of 10.  This property allows us to make the following divisibility rule for 3: if the digits of a number add up to a multiple of 3, then that number is divisible by 3.  For example, the number 531 is divisible by 3 because the digits add up to 5 + 3 + 1 = 9 which is a multiple of 3.  Mathematically, 531 = 5 x 100 + 3 x 10 + 1 = 5 x (99 + 1) + 3 x (9 + 1) + 1 = 5 x 99 + 5 x 1 + 3 x 9 + 3 x 1 + 1 = 5 x 99 + 3 x 9 + 5 + 3 + 1 = 5 x 33 x 3 + 3 x 3 x 3 + 5 + 3 + 1 = 3 x (5 x 33 + 3 x 3) + 5 + 3 + 1.  Therefore, if the digits 5 + 3 + 1 add up to a multiple of 3, the entire number must be a multiple of 3.

9

A similar divisibility rule for 3 can be made for the number 9, since 9 also divides into 9, 99, 999, (and so on).  If the digits of a number add up to a multiple of 9, then that number is divisible by 9.    For example, 648 is divisible by 9 because 6 + 4 + 8 = 18 which a multiple of 9.  (In fact, the rule can be applied a second time to 18, because its digits add up to 1 + 8 = 9.)  Mathematically, 648 = 6 x 100 + 4 x 10 + 8 = 6 x (99 + 1) + 4 x (9 + 1) + 8 = 6 x 99 + 6 x 1 + 4 x 9 + 4 x 1 + 8 =  6 x 99 + 4 x 9 + 6 + 4 + 8 = 6 x 11 x 9 + 4 x 9 + 6 + 4 + 8 = 9 x (6 x 11 + 4) + 6 + 4 + 8.  Therefore, if the digits 6 + 4 + 8 add up to a multiple of 9, the entire number must be a multiple of 9.  (This divisibility rule is also discussed in a previous blog.)

6

Divisibility rules for composite numbers can be made by combining rules of its (relatively prime) factors.  Since 2 x 3 = 6, the divisibility rule for 6 is the divisibility rule for 2 and 3 combined.  If the digits of a number add up to a multiple of 3, and if the number ends in 0, 2, 4, 6, or 8, then that number is divisible by 6. 

12

Similarly, since 3 x 4 = 12, the divisibility rule for 12 is divisibility rule for 3 and 4 combined.  If the digits of a number add up to a multiple of 3, and if the last two digits of the number are divisible by 4, then the entire number is divisible by 12.

11

Now we have found divisibility rules for the first 12 numbers other than 7 and 11.  There are divisibility rules for 7 and 11, but they are a little trickier.  First let us examine the divisibility rule for 11, which is less tricky than 7.  Powers of ten are alternately one less and one more than a multiples of 11.  In other words, 10 = 11 – 1, 10² = 100 = 99 + 1 = 11 x 9 + 1, 10³ = 1000 = 1001 – 1 = 11 x 91 – 1, 10⁴ = 10000 = 9999 + 1 = 11 x 909 + 1, and so on.  This unique property allows us to make the following divisibility rule for 11: if the digits of a number alternately add and subtract to a multiple of 11, then that number is divisible by 11. For example, 363 is divisible by 11 because 3 – 6 + 3 = 0 which is a multiple of 11.  Mathematically, 363 = 3 x 100 + 6 x 10 + 3 = 3 x (99 + 1) + 6 x (11 – 1) + 3 = 3 x 99 + 3 x 1 + 6 x 11 – 6 x 1 + 3 = 3 x 99 + 6 x 11 + 3 – 6 + 3 = 3 x 9 x 11 + 6 x 11 + 3 – 6 + 3 = 11 x (3 x 9 + 6) + 3 – 6 + 3.  Therefore, if the digits alternately add and subtract to a multiple of 11, the entire number must be a multiple of 11.

7

There are two divisibility rules for 7 that can either be used or combined depending on convenience.  Fortunately, 7 is divides into 1,001, which is 10³ + 1.  That also means that it divides into (10³ + 1)(10³ – 1) = 10⁶ – 1 = 999,999.  It also divides into (10³ + 1)(10⁶ – 10³ + 1) = 10⁹ + 1 = 1,000,000,001.  Carrying on in this fashion, we can show that 7 divides into 10^{6n – 3} + 1 and 10⁶ⁿ – 1 for any positive integer n.  Much like 11 (which divides into 10^{2n – 1} + 1 and 10²ⁿ – 1 for any positive integer n), if every three digits of a number alternately add or subtract to a multiple of 7, then that number is divisible by 7.  For example, 127,311,212 is divisible by 7 because 127 – 311 + 212 = 28 which is a multiple of 7.  Mathematically, 127,311,212 = 127 x 1,000,000 + 311 x 1,000 + 212 = 127 x (999,999 + 1) + 311 x (1,001 – 1) + 212 = 127 x 999,999 + 127 x 1 + 311 x 1,001 – 311 x 1 + 212 = 127 x 999,999 + 311 x 1,001 + 127 – 311 + 212 = 127 x 142857 x 7 + 311 x 143 x 7 + 127 – 311 + 212 = 7 x (127 x 142857 + 311 x 143) + 127 – 311 + 212.  Therefore, if every three digits alternately add and subtract to a multiple of 7, the entire number must be a multiple of 7.  (The number 142857 found in the above calculations is a cyclic number related to repeating powers and repeating decimals, which is discussed in a previous blog.)

This trick of alternately adding and subtracting three digits can be used multiple times in succession, but it can sometimes lead to three-digit numbers that are not obviously multiples of 7 at first glance, and so another trick is needed to test these three-digit numbers.  We can use the fact that 21 is a multiple of 7 for a second divisibility rule for 7 that will help with these three-digit numbers: if 2 times the last digit subtracted from the remaining digits is a multiple of 7, then that number is divisible by 7.  For example, 231 is divisible by 7 because 23 – 2 x 1 = 21 which is a multiple of 7.  Mathematically, 231 = 23 x 10 + 1 = 23 x 10 + 1 – 21 + 21 = 23 x 10 – 20 + 21 = 10 x (23 – 2 x 1) + 21 = 10 x (23 – 2 x 1) + 3 x 7.  Therefore, if 23 – 2 x 1 is a multiple of 7, the entire number must be a multiple of 7.  Both of these divisibility rules for 7 can be combined more than one way if needed.

Summary

A summary of all the divisibility rules discussed in this article can be found in the following table:

#	Divisibility Rule
2	If a number ends in 0, 2, 4, 6, or 8, then that number is divisible by 2.
3	If the digits of a number add up to a multiple of 3, then that number is divisible by 3.
4	If the last two digits of a number are divisible by 4, then the entire number is divisible by 4.
5	If a number ends in a 0 or 5, then that number is divisible by 5.
6	If the digits of a number add up to a multiple of 3, and if the number ends in 0, 2, 4, 6, or 8, then that number is divisible by 6.
7	If every three digits of a number alternately add or subtract to a multiple of 7, then that number is divisible by 7. If 2 times the last digit subtracted from the remaining digits is a multiple of 7, then that number is divisible by 7.
8	If the last three digits of a number are divisible by 8, then the entire number is divisible by 8.
9	If the digits of a number add up to a multiple of 9, then that number is divisible by 9.
10	If a number ends in 0, then that number is divisible by 10.
11	If the digits of a number alternately add and subtract to a multiple of 11, then that number is divisible by 11.
12	If the digits of a number add up to a multiple of 3, and if the last two digits of the number are divisible by 4, then the entire number is divisible by 12.

These rules have several applications, which include testing a number to be prime, as well as providing a convenient way to mentally check mathematical solutions.

Finger Multiplication

Tobias Dantzig makes mention of the lost art of finger multiplication in his book Number: The Language of Science, first published in 1930.  "Finger counting is a lost art among modern civilized people ... only a few hundred years ago finger counting was such a widespread custom in Western Europe that no manual of arithmetic was complete unless it gave full instructions in the method."  Using the method of finger multiplication, you can find the product of the numbers 6, 7, 8, and 9 with just your own ten fingers and a knowledge of the addition and multiplication tables up to five.

To use finger multiplication, hold out your hands palm down, label your thumbs 6, your index fingers 7, your middle fingers 8, your ring fingers 9, and your pinky fingers 10, and touch the tips of the two fingers that correspond with the two numbers you are multiplying together.  Then count all the fingers including and below the two fingers touching together and multiply that number by ten, and add to it the product of the left fingers above the two fingers touching together and the right fingers above the two fingers touching together. 

For example, let’s say you wanted to multiply 8 x 9.  You would hold your hands out palm down, and touch the tip of your left middle finger (which corresponds with 8) with the tip of your right ring finger (which corresponds with 9).  Including and below these two fingers there are a total of 7 fingers, and 7 x 10 = 70.  There are 2 fingers above the two fingers touching together on the left hand and 1 finger above the two fingers touching together on the right hand, and 2 x 1 = 2.  Adding these two numbers together gives 70 + 2 = 72.  So 8 x 9 = 72.

Or let’s say you wanted to multiply 6 x 7.  You would hold your hands out palm down, and touch the tip of your left thumb (which corresponds with 6) with the tip of your right index finger (which corresponds with 7).  Including and below these two fingers there are a total of 3 fingers, and 3 x 10 = 30.  There are 4 fingers above the two fingers touching together on the left hand and 3 fingers above the two fingers touching together on the right hand, and 4 x 3 = 12.  Adding these two numbers together gives 30 + 12 = 42.  So 6 x 7 = 42.

In general, if we want to multiply a x b using finger multiplication, then there are a – 5 fingers and b – 5 fingers including and below the two fingers touching together and 10 – a fingers and 10 – b fingers above the two fingers touching together.  The sum of all the fingers including and below the two fingers touching together and multiplying by ten can be represented as 10(a – 5 + b – 5), and the product of the left fingers above and the right fingers above can be represented as (10 – a)(10 – b).  Adding these together and simplifying would give 10(a – 5 + b – 5) + (10 – a)(10 – b) = (10a – 50 + 10b – 50) + (100 – 10a – 10b + ab) = ab, which is why finger multiplication works.

There is an easier method of finger multiplication, but it only works if one of the factors is 9.  Hold your hands out, count off the other factor you want to multiply by 9, and put that finger down.  Then the product will be the number of fingers to the left times ten plus the number of fingers to the right.

For example, let’s say you wanted to multiply 3 x 9.  You would hold your hands out and put down the third finger from the left (the left hand middle finger).  There are 2 fingers to the left and 7 fingers to the right, and 2 x 10 + 7 = 27.  So 3 x 9 = 27.

Or let’s say you wanted to multiply 8 x 9.  You would hold your hands out and put down the eighth finger from the left (the right hand middle finger).  There are 7 fingers to the left and 2 fingers to the right, and 7 x 10 + 2 = 72.  So 8 x 9 = 72.

In general, if we want to multiply a x 9 using finger multiplication for nines, then there are a – 1 fingers to the left of the finger that is down and 10 – a fingers to the right of the finger that is down.  The number of fingers to the left times ten plus the number of fingers to the right can be represented as 10(a – 1) + (10 – a).  Simplifying would give 10a – 10 + 10 – a = 9a, which is why this method of finger multiplication for nines also works.

As observed by Dantzig, finger multiplication is a dying art.  Few people know how to use finger multiplication for nines, and even fewer know how to use finger multiplication for the numbers six through nine.  It is likely that finger multiplication is no longer taught in schools anymore because for most people it takes just as much effort to memorize the multiplication table up to ten than to remember all the steps involved for finger multiplication.

Repeating Decimals

In our monetary system, different coins represent different fractions of a dollar, and most of us have memorized a few basic fraction to decimal conversions.  For example, one quarter is worth ¼ of a dollar or $0.25, so we know that ¼ = 0.25.  Similarly, one dime is worth ¹/₁₀ of a dollar or $0.10, one nickel is worth ¹/₂₀ of a dollar or $0.05, and one penny is worth ¹/₁₀₀ of a dollar or $0.01.  Therefore, we know that ¼ = 0.25, ¹/₁₀ = 0.1, ¹/₂₀ = 0.05, and ¹/₁₀₀ = 0.01.

One of the reasons these particular values were picked for coins was because the decimals for these fractions terminate, despite the fact that most fractions do not.  For example, a quarter can be represented with long division as the following:

	0.	2	5
4	1.	0	0
	–	8	↓
		2	0
	–	2	0
			0

The remainder reaches zero and so the decimal terminates, which makes for easier calculations for adding and subtracting amounts in cents.  But imagine a coin that was worth ¹/₃ of a dollar.  Using long division, we would get:

	0.	3	3	3	…
3	1.	0	0	0	…
	–	9	↓
		1	0
		–	9	↓
			1	0
			–	9
				1

The remainder never reaches zero, and so the threes carry on infinitely, which is why we don’t have a coin worth ¹/₃ of a dollar.  In mathematical terms, the three is repeated and the decimal can be expressed as 1/3 = 0.333…

The following table shows the decimal notation of the first twenty integers as denominators with a numerator of one:

Fraction	Decimal	Repeated Part	Period
1/1	1	(terminates)	0
1/2	0.5	(terminates)	0
1/3	0.333…	3	1
1/4	0.25	(terminates)	0
1/5	0.2	(terminates)	0
1/6	0.1666…	6	1
1/7	0.142857…	142857	6
1/8	0.125	(terminates)	0
1/9	0.111…	1	1
1/10	0.1	(terminates)	0
1/11	0.090909…	09	2
1/12	0.08333…	3	1
1/13	0.076923…	076923	6
1/14	0.0714285…	714285	6
1/15	0.0666…	6	1
1/16	0.0625	(terminates)	0
1/17	0.0588235294117647…	0588235294117647	16
1/18	0.0555…	5	1
1/19	0.052631578947368421…	052631578947368421	18
1/20	0.05	(terminates)	0

There does not seem to be any pattern to the length of the repeated part of the decimal, and as we will see later that is because there is a relationship between it and prime numbers, which has no known pattern.  However, there are certain rules that can be applied.

First of all, all denominators comprised of only factors of 2 or 5 terminate.  For example, 2, 4 (2²), 5, 8 (2³), 10 (2∙5), 16 (2⁴), 20 (2²5), and so on all terminate.  This is due to our numbering system being in base 10, which is 2 times 5.

Secondly, if the denominator is a prime number (other than 2 or 5), then the period is a factor of one less than the denominator.  For example, 7 is a prime number, and the period for ¹/₇ is 6, which is a factor of 7 – 1 = 6.  Also, 11 is a prime number, and the period for ¹/₁₁ is 2, which is a factor of 11 – 1 = 10.  The reasoning behind this is somewhat involved.  You may recall from your high school math class that the sum of an infinite geometric series is ^t1/_{1 – r} (when |r| < 1), where t₁ is the first term and r is the ratio.  This means that any repeating decimal (such as 0.090909…) can be expressed as a fraction by first rewriting it as an infinite geometric series (0.090909… = 0.09 + 0.0009 + 0.000009 + …) and then using the infinite geometric sum formula (^t1/_{1 – r} = ^0.09/_{1 – 0.01} = ^0.09/_0.99 = ⁹/₉₉ = ¹/₁₁).  In general, the numerator is the repeated part of the decimal and the denominator must contain a string of nines as long as the period of the decimal (before simplifying).  Since 7 has a period of 6, 7 must divide evenly into a string of 6 nines (999999 / 7 = 142857).  Since 11 has a period of 2, 11 must divide evenly into a string of 2 nines (99 / 11 = 9).  Mathematically, the string of nines n digits long can be represented as 10ⁿ – 1.  Now, Fermat’s Little Theorem states that “if p is prime and a is coprime to p, then p divides a^p−1 – 1.”  So if a = 10 and p is a prime number (other than 2 or 5 so that a and p are coprime) and n = p – 1, then p must divide into 10ⁿ – 1, which matches the string of nines needed in the denominator for a repeating decimal, meaning that all prime numbers must have a period that repeats itself every p – 1 digits.  That is why the prime number 7 has a period of 6.  So why doesn’t the prime number 11 have a period of 10 instead of 2?  Technically, it does have a period of 10, but only if you include five sets of two (¹/₁₁ = 0.0909090909…).  Because of the repetition of numbers in the period of 10 itself, the final period is short-circuited to a factor of 10, in this case 2.

Third, if the denominator d has a period of one less than itself, then d is prime.  Such prime numbers are called long primes.  For example, 7 must be a long prime because it has a period of 7 – 1 = 6, 17 must be a long prime because it has a period of 17 – 1 = 16, and 19 must be a long prime because it has a period of 19 – 1 = 18.  The reason behind this is due to Lehmer’s Theorem, which states that “if there exists an a where p divides into a^{p - 1} – 1, but p does not divide into a^{p – 1/q} – 1 for all primes q dividing p – 1, then p is prime.”  Because of our argument in the second point dealing with infinite geometric sums, since 7 has a period of 6, 7 cannot evenly divide into 9, 99, 999, 9999, or 99999, but finally must evenly divide into 999999.  In other words, if p = 7 and a = 10, p divides into a^{p - 1} – 1, but p does not divide into a^{p – 1/q} – 1 for all primes q dividing p – 1, so by Lehmer’s Theorem p = 7 must be prime.  With the help of a computer, other long primes include 7, 17, 19, 23, 29, 47, 59, 61, 97, 109, 113, 131, 149, 167, 179, 181, 193, 223, 229, 233, 257, 263, 269, 313, 337, 367, 379, 383, 389, 419, 433, 461, 487, 491, 499, 503, 509, 541, 571, 577, 593, 619, 647, 659, 701, 709, 727, 743, 811, 821, 823, 857, 863, 887, 937, 941, 953, 971, 977, 983, and so on. 

It’s pretty amazing that long primes even exist, especially with larger numbers.  If you think about it, using long division on a long prime must result in every single remainder between one and the period before being repeated (otherwise the period would be too short to be a long prime).  For example, using long division on the long prime 7 into 1 looks like the following:

	0.	1	4	2	8	5	7	…
7	1.	0	0	0	0	0	0	…
	–	7	↓
		3	0
	–	2	8	↓
			2	0
		–	1	4	↓
				6	0
			–	5	6	↓
					4	0
				–	3	5	↓
						5	0
					–	4	9
							1

The remainders are 3, 2, 6, 4, 5, and 1, which are all the numbers between 1 and 6 exactly once, before cycling through again.  That means that dividing a larger long prime number such as 983 would result in every single number between 1 and 983 appearing as a remainder exactly once before the cycle is repeated again!

The repeated part of the quotient of long primes, called cyclic numbers, also have fascinating properties.  First of all, multiplying a cyclic number by any integer less than its long prime number results in a number with the same digits in the same order.  For example, the cyclic number of the long prime 7 is 142857.  Multiplying 142857 by any integer less than 7 results in a number with the same digits in the same order:

142857 x 3 = 428571

142857 x 2 = 285714

142857 x 6 = 857142

142857 x 4 = 571428

142857 x 5 = 714285

142857 x 1 = 142857

Note that to make the diagonal number pattern, the multipliers are in the same order as the remainders of dividing ¹/₇ by long division.  Changing the numerator shifts the numbers of the remainders and the digits in the quotient.  So if you divide ³/₇ by long division, your first remainder is 2, then 6, then 4, then 5, then 1, then 3, which is the same order of the remainders in ¹/₇, therefore resulting in the same order of digits in the quotient in ¹/₇.

	0.	4	2	8	5	7	1	…
7	3.	0	0	0	0	0	0	…
–	2.	8	↓
		2	0
	–	1	4	↓
			6	0
		–	5	6	↓
				4	0
			–	3	5	↓
					5	0
				–	4	9	↓
						1	0
						–	7
							3

Since ¹/₇ x 3 = ³/₇, 0.142857… x 3 = 0.428571… which means 142857 x 3 = 428571. 

A second fascinating property is that the first half of the digits of a cyclic number added to the second half of the digits results in a string of nines.  For example, for the cyclic number 142857, the first half of this number is 142 and the second half is 857.  Adding these two numbers results in:

142

+ 857

999

For another example, the cyclic number of the long prime 17 is 0588235294117647 and

05882352

+ 94117647

99999999

The reason for this also quite involved.  From our rules of repeating decimals, ¹/₇ = ¹⁴²⁸⁵⁷/₉₉₉₉₉₉, and since 999999 = 10⁶ – 1 = (10³ – 1)(10³ + 1) = (999)(1001), ¹/₇ = ¹⁴²⁸⁵⁷/₉₉₉₉₉₉ can be rearranged to ¹⁰⁰¹/₇ = ¹⁴²⁸⁵⁷/₉₉₉.  As mentioned above, since 7 has a period of 6, 7 cannot evenly divide into 9, 99, 999, 9999, or 99999, but finally must evenly divide into 999999.  Applying the difference of squares, 999999 = 10⁶ – 1 = (10³ – 1)(10³ + 1), so 7 must evenly divide into (10³ – 1)(10³ + 1).  However, we already said that 7 cannot evenly divide into 999 or 10³ – 1, so 7 must divide into 10³ + 1, which means that 1001 divided 7 must be an integer.  Therefore, since ¹⁰⁰¹/₇ = ¹⁴²⁸⁵⁷/₉₉₉, ¹⁴²⁸⁵⁷/₉₉₉ must be an integer.  Now, ¹⁴²⁸⁵⁷/₉₉₉ = ¹⁴²⁰⁰⁰/₉₉₉ + ⁸⁵⁷/₉₉₉ or 142.142142142… + 0.857857857…  Since this sum must be an integer, each digit after the decimal must be 9, because 0.999… = 1, meaning the first half of the digits of this cyclic number added to the second half of the digits of this cyclic number must result in a string of nines.  (A quick proof that 0.999… = 1 is that 0.999… = (0.333…)3 = (¹/₃)3 = 1.)   A similar argument can be made for any cyclic number, since the period will always be even, which means the difference of squares can always be applied.

Therefore, using long division to turn fractions into decimals leads to finding fascinating properties of terminating and repeating decimals.  The period of repeating decimals do not seem to follow any sort of pattern, but certain rules can be applied, especially concerning prime numbers.  Investigating a little deeper leads to the discovery of long primes and cyclic numbers, which also have some amazing properties.