## Divisibility Rules.

### January 31, 2011

Sometimes when I’m at a restaurant with friends and the check comes, we need to evenly split the bill.  If you’re a math major, then you’re already assumed to be able to calculate this in your head; nonetheless, no one wants to hear that they owe  $3.53333333333… because very few people have fractions of pennies lying around. It suffices, sometimes, to round up or down a penny or two to make things come out nice. But this means you should have a good understanding of when numbers divide into other numbers. Here’s an example (which motivated me to post this): every month, the bill for the internet is around$65.  I have two other roommates (and a freeloading daschund) so we split it up into three even parts.  Now, I know that 3 does not divide into $65, so I just "round up" to$66 and then use the excess as credit, since that’s easy to divide by 3.  But what happens if you lived with 10 other people and you needed to divide up a $2033 bill. Does this work? What about$2035?  Did you have to use a calculator?

## Divisibility Rules for 2, 5,10.

Let’s get the few easy ones out of the way.

A number is divisible by 2 if it is an even number; that is, if its last digit is 0,2,4,6, or 8.

A number is divisible by 5 if its last digit is a 0 or a 5.

A number is divisible by 10 if its last digit is a 0.

These cases are trivial, and can be proved easily.  I use these as example problems when I’m teaching a student how to prove statements, as a matter of fact.

## Divisibility Rules for 3, 9, and 11.

I’ve grouped these together, since these digits are ones where we need to "sum up all of the values" and their proofs are pretty much the same.

A number is divisible by 3 if the sum of its digits is.

A number is divisible by 9 if the sum of its digits is.

A number is divisible by 11 if the alternating sum of its digits is; in other words, make the first digit positive, the second negative, the third positive, and so on.

These proofs are a bit trickier.  We’ll do the one for 3, and leave the others as exercises.  In particular, the one for 11 is a bit tricky, but it is useful for the reader to go over it.

Proof (for divisibility by 3).  Given some number $n$ we can expand $n$ out in the following way:

$\displaystyle n = \sum_{i=0}^{m} a_{i}10^{i}$.

This is how we define numbers in base 10.  So $341 = 300 + 40 + 1 = 3*10^{2} + 4*10^{1} + 1*10^{0}$.  Now, here’s the trick.  This is the same as writing:

$\displaystyle n = \sum_{i=0}^{m} a_{i}(10^{i}-1) + a_{i}$.

And so, for example, $341 = 3*(99) + 4(9) + 1(0) + (3 + 4 + 1)$.  Note that $10^{i} - 1$ is just a sequence of $i-1$ 9’s, so it is divisible by 3.  Thus, since 3 divides the $10^{i} - 1$ part of the summands, we need only that 3 divides

$\displaystyle \sum_{i=0}^{m} a_{i}$

which is exactly what our criteria was.  $\Box$.

Notice that this definition for divisibility by 3, 9, and 11 are able to be done over and over until you have a nice small number.  For example, is

$11123456789987654321123456789987654321\\ 11123456789987654321123456789987654321\\ 11123456789987654321123456789987654321\\ 11123456789987654321123456789987654321\\ 11123456789987654321123456789987654321\\ 11123456789987654321123456789987654321$

divisible by 3?  I’ve only broken it up by lines for display purposes: I mean this number which is made up of these 6 repeating pieces.  Pretend you have no calculator for some reason.  Adding this up (which would take a load of time, but probably a lot less time and paper than attempting to divide by 3 with long division) we obtain the slightly less huge number $1092$.  Is this number divisible by 3?  Well, $1 + 0 + 9 + 2 = 12$, and if you’re REALLY lazy, $1 + 2 = 3$, and so the original (long!) number must also.  Amusingly, this number has a prime factorization where the lowest two prime factors are 3 and 203969.

## Divisibility Rule for 4.

This rule can be generalized for any number which evenly divides $10^{i}$ for every $i > N$ for some $N\in {\mathbb N}$.  You’ll see what I mean in a second.

A number is divisible by 4 if the last two digits (not summed up) are divisible by 4.

The proof for this (and the related numbers) is surprisingly easy.

Proof (the divisibility rule for 4).  Note that given a number $n$, we can write $n$ in the following way:

$\displaystyle n = \sum_{i=0}^{m} a_{i}10^{i}$.

Note that $10^{i}$ is divisible by 4 for $i \geq 2$; ie, 4 divides 100, 1000, 10000, and so on.  You can prove this as a lemma if you’d like.  Thus, 4 divides each of these summands except for possibly

$a_{1}10^{1} + a_{0}10^{0} = 10a_{1} + a_{0}$.

but this is exactly how we represent the last two digits of a number.  $\Box$.

For each of the following numbers, be sure to be able to (quickly) tell without a calculator if they’re divisible by 2, 3, 5, 8, 9, and 11.

• 121
• 244
• 156
• 777
• 770
• 889
• 2222
• 11111
• 333333
• 33333321
• 33333312
• 998877665544332211998877665544332211
• The year it is now.