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 ( 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 . 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).
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 .
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
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: .
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
So all the same stuff will work as long as 6 goes evenly into It does, because in base 7. So if you want to see whether divides evenly, you could always just convert to base 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.