Author |
Topic: Divisibility by 7 (Read 601 times) |
|
Christine
Full Member
Posts: 159
|
 |
Divisibility by 7
« on: Feb 21st, 2008, 3:08am » |
 Quote  Modify
|
If we write the sequence 1, 10, 100, 1000, 10000, and so on, and writedown the remainder of each number modulo 7, we get
1/7 = 0 r 1
10/7 = 1 r 3
100/7 = 14 r 2
1000/7 = 142 r 6
10000/7 = 1428 r 4
100000/7 = 14285 r 5
1000000/7 = 142857 r 1
10000000/7 = 1428571 r 3
In other words, instead of working with big numbers, it's sufficient to take the previous remainder, multiply it by 10, divide by 7.The 'next' remainder can be calculated solely based on the previous one.
Can anyone tell why why it (necessarily) becomes periodic with the exception of a few first terms?
In the problem i posted N=7, but can we generalize here, for any N?
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Divisibility by 7
« Reply #1 on: Feb 21st, 2008, 4:44am » |
Quote Modify
|
on Feb 21st, 2008, 3:08am, Christine wrote:In other words, instead of working with big numbers, it's sufficient to take the previous remainder, multiply it by 10, divide by 7.The 'next' remainder can be calculated solely based on the previous one.
Can anyone tell why why it (necessarily) becomes periodic with the exception of a few first terms?
In the problem i posted N=7, but can we generalize here, for any N? |
|
Well, the short answer is that, since the next remainder is determined by the previous one, and the number of remainders is limited (they must by definition be smaller than the absolute value of the divider and greater than or equal to 0), they must end up being periodic.
At some point you must get a remainder you had before, and everything that came after it then will come after it now, because each next remainder is determined by the previous one.
This holds for any N.
|
| « Last Edit: Feb 21st, 2008, 4:46am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Divisibility by 7
« Reply #2 on: Feb 21st, 2008, 4:27pm » |
Quote Modify
|
A (relatively) nice divisibility test for 7:
(A) If the number has more than 6 digits, break off the last 6 digits and add it to the rest. Continue until a number of 6 digits or less remains.
(B) Take the difference between the first 3 and last 3 digits. (It doesn't matter which way you go, so just choose the positive answer.)
(C) subtract twice the last digit from the first two digits. Repeat until divisibility is obvious.
For example,
870531186 --> 531186 + 870 = 532056 --> 532 - 56 = 476 --> 47 - 2*6 = 35 which is divisible by 7.
And, in fact, 870531186 = 7*124361598.
Wikipedia calls this the "Pohlman-Mass Method", though their explanation is harder to follow.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Divisibility by 7
« Reply #3 on: Feb 21st, 2008, 6:00pm » |
Quote Modify
|
Another nice test: http://www.sciencenews.org/articles/20050521/mathtrek.asp
A somewhat easier way (in my opinion) of approaching it is available in one of the links:
(1) Divide your number up in blocks of 2 digits:
27 31 55 52 87 23
(2) Starting on the right and moving left, divide the numbers by 7 and keep the remainders. Write your answers in reverse order (the rightmost pair of digits yields the left most remainder):
2 3 3 6 3 6
(3) Starting with the 2nd digit, replace every other digit with 7 - the digit (if a digit is 0, it can be left alone):
2 4 3 1 3 1.
The result is divisible by 7 if and only if the original was. Of course, you may have to apply the procedure a few more times to get to a number you can recognize:
24 31 31 --> 3 3 3 --> 3 43 --> 1 3 --> 14.
So 273155528723 is divisible by 7.
|
| « Last Edit: Feb 21st, 2008, 7:06pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print