You can determine the remainder even more simply by "casting out multiples
of 7": replace any string of numbers you see by their remainder upon
division by 7. Thus, the number 29376 below becomes:
29376 = (29)376-->(1)376 = 1376 = (13)76-->(6)76 = 676 = (67)6-->(4)6 = 46-->4
(there are clearly other ways of doing this).
There is a way of getting the quotient, but it doesn't work well with
numbers bigger than 100p, where p is the prime divisor, at least not with
ordinary people.
Geoff Hagopian said:
>Kevin,
>
>Nice explanation for this algorithm to compute the remainder. Is there an
>easy
>way of recovering the quotient while you're at it?
>
>Kevin : Broussard wrote:<snop>
>
>> Thus we need to determine the remainders, modulo 7, of various powers of 10.
>>
>> 10^0 = 1 (mod 7)
>> 10^1 = 1*10 = 10 = 3 (mod 7)
>> 10^2 = 3*10 = 30 = 2 (mod 7)
>> 10^3 = 2*10 = 20 = 6 = -1 (mod 7)
>> 10^4 = 6*10 = 60 = 4 = -3 (mod 7)
>> 10^5 = 4*10 = 40 = 5 = -2 (mod 7)
>> 10^6 = 5*10 = 50 = 1 (mod 7)
>>
>> and clearly this cycle will repeat.
>>
>> Then, to check if 29376=0 (mod 7), we work from right to left, and multiply
>> the 6 by 1,
>> the 7 by 3,
>> the 3 by 2,
>> the 9 by -1,
>> the 2 by -3,
>>
>> and add these products together. This sum of 18 will be equivalent, modulo
>> 7, to 29376. In fact, as when "casting out nines", this process may be
>> repeated on the number 18: working from right to left, we multiply
>> the 8 by 1,
>> the 1 by 3,
>>
>> and add these products together. This sum of 11 will be equivalent, modulo
>> 7, to both 18 and 29376. One more time, working from right to left,
>>multiply
>> the 1 by 1,
>> the 1 by 3,
>>
>> and add these products together. Now we see that
>>
>> 29376 = 18 = 11 = 4 (modulo 7)
>>
>> so that 29376 divided by 7 gives a remainder of 4.
>
><snop>
>
>****************************************************************************
>* To post to the list: email mathedcc@archives.math.utk.edu *
>* To unsubscribe, send mail to: majordomo@archives.math.utk.edu *
>* In the mail message, enter ONLY the words: unsubscribe mathedcc *
>* Words in the Subject: line are NOT processed! *
>* Archives at http://archives.math.utk.edu/hypermail/mathedcc/ *
>****************************************************************************
Ä
Mark A. Snyder Work: 978.665.3076
Dept. of Mathematics Home: 978.386.7158
Fitchburg State College email: msnyder@tiac.net,
Fitchburg, Mass. 01420 msnyder@fsc.edu
fax: 978.665.4031
****************************************************************************
* To post to the list: email mathedcc@archives.math.utk.edu *
* To unsubscribe, send mail to: majordomo@archives.math.utk.edu *
* In the mail message, enter ONLY the words: unsubscribe mathedcc *
* Words in the Subject: line are NOT processed! *
* Archives at http://archives.math.utk.edu/hypermail/mathedcc/ *
****************************************************************************