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/ *
****************************************************************************