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.

 

Exercises for the Reader.

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
  • Your age.
  • Your birth-year.
  • The year it is now.
  • Your social security number.
  • Your credit card number.
  • The price (multiplied by 100) of the cost of your favorite coffee.
  • The ISBN of your favorite math book.
Advertisements

One Response to “Divisibility Rules.”

  1. Tom said

    I was taught these rules in high school but never the proofs, interesting stuff.

    By the way James this is Tom I sat next to you in linear algebra, hope your classes are going well. I finally hunted down this blog you mentioned a while ago. I’ll have to read through it.

    I think it’s pretty awesome you have the dedication for these posts which obviously take a lot more thought and knowledge than the average “mind diarrhea” most other blogs are comprised of.

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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: