wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> general problem-solving / chatting / whatever >> Divisibility by 7
        
(Message started by: Christine on Feb 21^st, 2008, 3:08am)

Title: Divisibility by 7
Post by Christine on Feb 21^st, 2008, 3:08am

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?

Title: Re: Divisibility by 7
Post by towr on Feb 21^st, 2008, 4:44am

on 02/21/08 at 03:08:45, 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.

Title: Re: Divisibility by 7
Post by Icarus on Feb 21^st, 2008, 4:27pm

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.

Title: Re: Divisibility by 7
Post by Icarus on Feb 21^st, 2008, 6:00pm

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.