Everyone knows how to test for evenness: just check the last digit. If it’s in then the number is even, no matter what other digits it has. This rule works in base 10 but not in base 3. In fact, this rule works in all even bases and fails in all odd bases. Why? And how do we test for evenness in odd bases?

Before we go into the details I want to ask two favors. First, if you are a math person, please forgive my sloppy use of terminology and typesetting; I have read very little math and written less. Second, for those who don’t already know the trick in odd bases: please don’t try to get the answer by inspection and intuition. Many people will find it easy to spot the pattern in a series of numbers. The treasure in this post is not the simple trick we learn for testing evenness, but the journey following the reasoning that proves that the trick works. So don’t even think about pondering a series of odd numbers because you’ll miss the journey of the proof.

Okay, let’s get the terminology and notation down before we start. Base 10 means we represent all numbers using only ten digits: 0-9. (Another word for base is radix.) Normally we write and read numbers in the decimal system which uses base 10 but any whole number can be used as a base: 2, 3, 10, 60, etc. When we represent numbers in different bases we place the number in parentheses followed by the base in subscript.

When we omit the subscript, the base is assumed to be 10. It’s important to have this notation because similar numbers have different values in different bases. For example, the three-digit number 100 represents one hundred in base 10.

In base 2 those digits represent a value of four.

In base 3 the same three digits represent nine.

That covers all of the technical lingo we need for this journey so let’s start.

First, let’s see why the evenness test is so easy in even bases. Evenness is just divisibility by 2. So let’s review how numbers and bases work. A number is the sum of its parts, which are its digits multiplied by their place values. We add 100 and 20 and 3 to get 123.

Whatever is in the tens place, its value will be a multiple of ten. Two is a factor of ten. Two is therefore a factor of any whole multiple of ten. Adding an even number (a multiple of two) to any number X can not change the evenness of X. So it makes no difference how many tens or hundreds or thousands we add; the units place alone determines whether the number is divisible by 2. This is true in all even bases, not just 10. We can illustrate this by writing 123 in bases 8, 6, 4 and 2.

In each of the above representations of 123, the digit in the units place is an odd number. That’s enough information to settle the question of evenness. It doesn’t matter that we don’t immediately recognize the that ; we can tell that it’s even just by checking the last digit.

Now let’s see what happens when we rewrite 123 in a few odd bases.

The last digit can be even or odd but we know these numbers are all odd. Clearly the units place is not a reliable indicator of evenness. Why not? Because the radix is odd, multiples of the radix can be odd or even. Therefore the digits in the other places are capable of holding odd or even values. So our evenness test must consider all of the digits of the number.

Let’s remember how digits work together to make a number: they are added together. How does addition affect evenness? Adding an even number has no effect, but adding an odd number to X reverses the evenness of X. Adding two odds makes an even. Extending this, adding an even number of odds makes an even.

How does this help us? Well, every product of two odd numbers is itself odd. This is true because odd numbers are defined by the lack of 2 in its prime factorization. It also applies to powers of odd numbers. No matter how many times you multiply 3 by itself, the result is odd. So we know that each and every place value in an odd base is odd because it is a power of an odd number. This gives us the last clue we need for our trick: every even digit adds an even number, while every odd digit adds an odd number to the total.

The trick, then, finally, is to count the number of odd digits in the number, ignoring any evens. If the number of odd digits is even, all of the oddness cancels out and the number is even. If the number of odd digits is odd, the number is odd.

While the odd-based evenness test may lose to the even-based test on the grounds of speed (inspecting every digit instead of just one) and on the grounds of usefulness (does anyone use odd bases for anything, ever?) I find it much more satisfying because I can derive it myself.

If you found this little journey interesting, others divisibility tricks also have parallels in other bases. Take the trick for 9: if the digits sum to 9, the number is divisible by 9. This works in base 10 because . The same trick works in base 8: if the digits sum to 7, the number is divisible by 7. In general terms, if the digits sum to , the number is divisible by . I haven’t derived the proof for that one yet.

Let me know if you would like this kind of thing better as a vihart-style video.

Credit goes to Zoe Skelton for helpful feedback prior to publication.

Hi,

Nice blog post!

The radix – 1 ‘trick’ works in a very similar way: in the same way that the product of odd numbers is odd, if the radix, say b, is 1 more than a multiple of k, then b^n is one more than a multiple of k. (This is slightly more general: this gives you the test for any number which divides radix – 1. Hence this trick always works for 2 in odd bases, because radix – 1 will always be even if radix is odd.)

If you’re familiar with modular arithmetic, that’s a good language to talk about these sorts of questions in. (If you’re not, I think you would find it interesting!)

RE: does anybody use odd bases? I haven’t come across anything in that vein. One of the properties you want in a base typically is that it has a lot of factors relative to the size of the base (so you can do the ‘look at the last digit’ trick for more division tests): this is why people root for base 12 so much, because 12 is the smallest number with six factors.

Thus having factors of two is typically good, because 2 is the smallest prime so you can have a lot of factors of two and still be relatively small. (In fact, if your base isn’t even, you can get a smaller base with the same number of factors by writing out the prime factorisation of your base, and then changing each prime to the one before it.)

Numbers which have more factors than any number smaller are called highly composite numbers, and are considered to be the best numbers for bases. This is why, for example, base 60 is so good, and having 60 minutes to an hour is nice: half an hour, a third of an hour, a quarter of an hour, a fifth of an hour are all whole numbers of minutes. If there were 100 minutes to an hour, then it would be much harder to work out how long a third of an hour was.

One of the problems 12 has, then, is that 12 – 1 (i.e. 11) is prime. So the only number that this trick works for in base 12 is 11 (and 1, I guess, if we’re being pedantic). Base 10 wins in this regard, as 10 – 1 = 9 is composite, so the trick works for both 3 and 9 (and you can glue the evenness test on to get it to work for 6, too.)

In some sense, 6 is one of the best bases: for all the numbers below six, we have really nice divisibility tests:

2 – last digit

3 – last digit

4 – last two digits

5 – add digits

However there are few advocates for base six. I think the main reason for this is numbers written in base 6 are roughly 30% longer than if they were written in base 10, which makes elementary operations (addition, multiplication, etc.) take a lot longer (assuming we’ve memorised all of these operations on one digit numbers).

This ended up being a lot longer than I thought it would be. I hope this was interesting (and readable!)

Thanks for the rich reply! A commenter on Reddit also helped out with a proof of the radix – 1 rule. https://www.reddit.com/r/math/comments/4puppw/comment/d4o4hrz