How does this work, division by 7

getting worse

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

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

Thanks tim

Cheeble

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

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

MathsManiac

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

(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