## Wednesday, September 21, 2016

### Divisibility Rule For 7

I learned something today.

Today my pre-calculus students were studying all sorts of things about polynomials.  They looked at the Fundamental Theorem of Algebra and it's far more interesting lemma about the number of roots, they learned about about the nature of roots--specifically, if the polynomial has real coefficients, then any imaginary roots will always occur in complex conjugate pairs--they learned to how find a polynomial that had specific roots, and they learned the rational root theorem.  All in 2 hours.

In 6th period, something prompted me to mention divisibility rules.  I said there were rules for 2, 3, 4, 5, 6, 8, 9, and 10; I'm not concerned about divisibility rules for numbers above 10.  One student asked if there was a rule for 7 and I said no, I'd never heard of one.  He showed me one he learned somewhere, and I told him I wanted to check it.  I brought it home and just proved it.  His rule is this:
Separate the n-digit number into n-1 digit number and a 1-digit number by removing the ones digit.  Subtract twice the ones digit from the n-1 digit rump number.  If the difference is divisible by 7, the entire number is divisible by 7.  If the difference is still large, continue the process on this difference.

Prior to proving it, though, I needed to review a little number theory.  I've never had a class in number theory, I've just encountered it in a Problem Solving Throughout History course.  I came home and reviewed what little number theory I've studied, practiced it by proving the divisibility rule for 9 (at least for a 3 digit number), and tackled 7.

It works.

Before I show my work to you, let's review some algebra problems that only old-timers will have encountered.  Remember these?
Start with a 2-digit number.  Reverse the digits.  The new number is 27 more than the old number.  The digits add up to 11.  What was the original number?
If t is the tens digit of the original number, and u is the units digit of the original number, then the system of equations that is created is
10t+u=(10u+t)-27
t+u=11
Remember those?  Well, that's where I started.

The first problem I worked, just to get my juices flowing, was proving the divisibility rule for 9 for a 3-digit number.  To say that a number is divisible by 9 means that it is equal to 9 times some integer, which I called p or q.  And of course, the digits in the number have to be integers.

Here's my work for proving the divisibility rule for 9 on a 3-digit number.
click image to enlarge

Looking at this proof, it wouldn't be difficult at all to extend it to an n-digit number.

Feeling all warmed up, I tried this student's proposed divisibility rule for 7 for both 2 and 3 digit numbers.  It worked.

By this time I was fully ready to tackle an n-digit number.  Turns out it was pretty straight-forward:

I don't know who discovered this rule, or how, or what they were smoking when they figured it out, but I like that I learned it today.

Update:  minor error in my last proof.  The given integer has n+1 digits, not n.  No aspect of the proof is affected by this mistake.