Multiples Rule For 3, 9, and 27

I’m sorry I started writing this post. The point was to talk about some simple number theory, but I decided to “build into it” with a pointless anecdote about my pointless childhood. This anecdote happened to involve the TV show “Square One”. Thanks to my simian brain’s stupid ability to make connections between various stores of knowledge, I realized that although I haven’t seen an episode of the show since 1993, now we have YouTube, and therefore I can go watch people roller skating while tied to pickup trucks.  Also I can find that show. It’s probably the greatest thing since Spirograph.

And there’s plenty more where that came from.

But the actual impetus for this story was that I was tutoring some intelligent algebra students (x of them), in the prime factorization of numbers. I was surprised they hadn’t heard the following rules to check whether a number is divisible by three or nine without doing the division problem.

  • A number is divisible by three if and only if the sum of its digits is divisible by three.
  • Likewise for nine.

The reason I couldn’t imagine someone not familiar with this oh-so-basic fact is that I learned it at age six from a singing cowboy.

But these aren’t theorems about the numbers, exactly.  They’re theorems about numbers and the numbers’ digits.  The distinction is important because numbers themselves are pretty fundamental, while the digits are a consequence of the base of the numeral system you’re using.  We use base ten, which is where these theorems hold.  They clearly fail in base three, for example, where we can write three = 10.  Consequently, this quick-factoring trick is one little gem of knowledge unknown to the ancient Pythagoreans or modern Canadians.

Note that three goes into 9, to 99, to 999, etc.  So take a number with some digits in it, say 5832.  (The great thing about being a math dabbler rather than a math student is that proofs by example, which are totally easy, don’t bother you one bit).

\frac{5832}{3} = \frac{5*1000}{3} + \frac{8*100}{3} + \frac{3*10}{3} + \frac{2}{3}

Now we’ll write 1000 as 999+1, and pull the same trick for the other powers of ten.  Then break up the fractions using \frac{a+b}{c} = \frac{a}{c} + \frac{b}{c}.

\frac{5832}{3} = \frac{5*999}{3} + \frac{5*1}{3} + \frac{8*99}{3} + \frac{8}{3} + \frac{3*9}{3} + \frac{3}{3} + \frac{2}{3}

Since we only care whether this gives an integer, we can drop all those ones with the 9, 99, 999 etc. in the numerator.  They cleary do give integers.  This leaves us to evaluate whether

\frac{5}{3} + \frac{8}{3} + \frac{3}{3} + \frac{2}{3} = \frac{5+8+3+2}{3}

is an integer.   So to test whether a number is divisible by three, add its digits.  Likewise for nine, since nine also divides 9, 99, 999…

What got me looking at this was that my student, curious young mathematician that he is, asked if the same holds true for 27.  We can say right off the bat that because every multiple of 27 is also a multiple of nine, the digits of a multiple of 27 must sum to a multple of nine.  However, there is no requirement that the multiple of nine they sum to is 27.  For example, 54 is a multiple of 27, but its digits sum to 9.  2727 is a multiple of 27 (27*101), but its digits sum to 18.

But does a one-way version of the theorem still hold?  If the digits of a number sum to 27, is that number divisible by 27?  The first such number you’ll run into is 999 = 27 * 37.  I tried six or seven other examples.  They all worked.  So I set out to prove it and was running into trouble.  But the nice thing was that although I couldn’t prove it, my attempt to find a proof showed me an easy way to find a counterexample.  I won’t go into the details, but you can go searching for yourself.  Here’s a hint: \frac{818172}{27} = 30302 \frac{2}{3}.

Higher powers of three are an obvious generalization.

If you followed the proof closely, then two things:

  • wtf?  it’s not like it’s your homework or something.  or like i know what i’m talking about
  • you can find similar properties in base n

In base 7, for example. a number’s digits will sum to a multiple of six if and only if the number is itself a multiple of six.  For example, in base 7

213 = 2*7^2 + 1*7 + 3 = 2*(7^2 - 1) + 1*(7-1) + 2 + 1 + 3

So all the same stuff will work as long as 6 goes evenly into 7-1, 7^2-1, 7^3-1,...  It does, because \frac{7^5 - 1}{6} = \frac{66666}{6} = 11111 in base 7.  So if you want to see whether p divides q evenly, you could always just convert q to base p+1 and add the digits.  However this is quite a bit more work than just doing the straight up division problem.

Also note that the reason the theorem works for three is that it goes evenly into nine. In base 13 the trick works for 12, 6, 4, 3, and 2. And on a practical note, in hexadecimal it works for f (which is what you use for 15), 5, and 3. Hexadecimal is actually quite nice for factoring, because in addition to easy rules for those numbers, you also have easy rules for 2, 4, and 8 – you can just check the last digit of the number the same way you can to see if something is a multiple of 2 or 5 in base 10.

Tags: , , , , , , ,

3 Responses to “Multiples Rule For 3, 9, and 27”

  1. Multiples Rule for 7 « Arcsecond Says:

    […] Rule for 7 Last month I posted a bit about the rule to tell if a number is divisible by three or nine. With these rules in place, here are the rules we have to tell whether a number is divisible by any […]

  2. erikpan Says:

    I remember proving on a napkin in Bangkok that this property of digit addition holds true in base delta, such that if there is a number k with delta mod k = 1, then numbers which were multiples of k had digits in the base that summed to k. Involved modulo arithmetic and possibly induction on powers of delta (or maybe just infinite sums).

  3. erikpan Says:

    PS – note this holds true for 10 mod 3 = 1, so for 3 in base 10, and 7 mod 6 = 1, so your example in base 7 there again holds true.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: