How does this work, division by 7

getting worse · 08-04-2009 05:16PM #1

Can any one help me?
I have an algorithm which shows if a number is divisible by 7. It works like this:

To determine if a number is divisible by 7, take the last digit off the number, double it and subtract the doubled number from the remaining number. If the result is evenly divisible by 7 (e.g. 14, 7, 0, -7, etc.), then the number is divisible by seven. This may need to be repeated several times.

Is 3101 evenly divisible by 7?

Take off the last digit = 310
double and subtract -2
308
Take off the last digit = 30
double and subtract -16
answer 14 divisible by 7 so so is 3101

And it works, at least I can’t find a counter example, but I can’t figure out why it works, does anyone know.

timbrophy · 08-04-2009 08:24PM

It works because the sequence of operations preserves divisibility by 7. Suppose you have the number represented by the string of digits "abcde". Call this number n. Then
n = a*10^4 + b*10^3 + c*10^2 + d*10 + e
Take off the last digit to get a*10^3 + b*10^2 + c*10 + d
Subtract 2e to get a*10^3 + b*10^2 + (c*10 + d - 2e)
If this is divisible by 7 we have
a*10^3 + b*10^2 + c*10 + d -2e = 0 mod 7
so multiplying by 10 we get
a*10^4 + b*10^3 + c*10^2 + d*10 - 20e = 0 mod 7
add 21e to both sides to get
a*10^4 + b*10^3 + c*10^2 + d*10 + e = 21e mod 7
which is just
n = 0 mod 7 since 21 is a multiple of 7

As you can see, the only digits that matter are c, d and e so this method will always work.

getting worse · 09-04-2009 11:59AM

Thanks tim

Cheeble · 09-04-2009 08:38PM

What's the property of 7 that causes this:

1/7=0.142857 all 6 digits recurring i.e. 1/7=0.142857142857142.....
2/7=0.285714 ditto
3/7=0.428571 ditto
4/7=0.571428 ditto
5/7=0.714285 ditto
6/7=0.857142 ditto

i.e. if you can remember the six digit sequence (it's the same in each case), you can divide by 7 just by starting with the right digit.

Cheeble-eers

overmantle · 10-04-2009 01:05AM

Nothing like a post like this to get the old brain out of neutral! Well done.

MathsManiac · 10-04-2009 01:26AM

Cheeble wrote: »

What's the property of 7 that causes this:

The fact that 10 is a primitive root modulo 7.

(This also works, for example, for 17, 19, 23, 29, 47, and many more.)

Here's an interesting and related question: for any whole number n, what is the length of the repeating cycle in the recurring decimal expansion of 1/n?

(Hint: try prime n first. And looking it up in Wikipedia is cheating!)

timbrophy · 10-04-2009 02:35PM

(Hint: try prime n first. And looking it up in Wikipedia is cheating!)

After you try for a while look at
http://mathworld.wolfram.com/DecimalExpansion.html
which is fascinating.

Tim

How does this work, division by 7

Comments