Re: Dividing By Seven

"Dave" asks:
> > One of my students asked me a puzzle he had found somewhere...
> >
> > "What is the remainder when 5^100 (5 to the power of 100) is divided by
> > seven?"
> >
> > After doing several examples, 125/7, 625/7 3125/7, etc, there seemed to
> > be a pattern with the remainders, and 2 was the answer I came up with.

Correct.

> > Is there an easier way other than that?

In computing the powers, take the remainder mod (i.e. on division by) 7
after every multiplication, rather than at the end. Then you get the
first few powers of 5 are 5, times 5 is 25 -> 4, times 5 is 20 -> 6,
times 5 is 30 -> 2, 10 times 5 is -> 3, times 5 is 15 -> 1. (This is the
same repeating pattern you already found, just an easier way to compute
it.) The cycle repeats with a period of 6, so now take 100 mod 6 = 4,
and you have 5^100 -> 5^4 -> 2.

You can simplify the calculation still further by using balanced modular
arithmeric, i.e. working with numbers in the range -3 to +3 rather than
0 to 6. In place of 6 you use -1, in place of 5 is -2, and in place of
4 is -3. Now you compute the powers this way: 5 -> -2, times -2 is 4
-> -3, times -2 is 6 -> -1, times -2 is +2, times -2 is -4 -> +3, times
-2 is -6 -> +1. You have now discovered the period of 6 while working
entirely with 1-digit numbers.

"Mike":
> In the group Z(mod 7Z) since 7 is prime, 5^n repeats with periodicity 7

No, it doesn't. I suspect that the period is always one less than the
modulus, i.e. 6, in which case the calculations I just described can be
entirely skipped in the way that Mike got wrong. But I'm not certain of
that, and the modular-arithmetic tricks are worth posting anyway.

> thus take the remainder of 500/7 ...

No, we were doing 5^100, not 5^500. The amusing thing as these two errors
cancel out and happen to produce the right answer.

> Let me know if you need clarification, this was done very quickly...

(Grin)
--
Mark Brader, Toronto "Don't get clever at 5PM Friday."
msb@xxxxxxx -- Tom Van Vleck

My text in this article is in the public domain.
.

Relevant Pages

  • Re: Regular Expression
    ... Since the remainder of the string starts with "BEGIN", but but your pattern expects spaces or the beginning of the string, that occurance is skipped and the next " BEGIN " is matched. ...
    (microsoft.public.scripting.vbscript)
  • Re: Any quick way to find a remainder ?
    ... fw_ho@hotmail.com (Andrew) wrote: ... > What is the remainder if the following numver x is divided by 13. ... You will see a pattern. ...
    (sci.math)
  • Re: AD: Aged Pipe tobacco & Old Boy
    ... Tilbury is also sold. ... Offers considered on the remainder. ... Thx ... Mike ...
    (alt.smokers.pipes)
  • RE: grouping
    ... "Mike 6" wrote: ... common cell number, then taking the remainder of the data in that row and ... only looking at those rows for comparing data. ...
    (microsoft.public.excel.misc)
  • Re: Shuttle Launch
    ... D Peter Maus wrote: ... I'm sure the remainder of the population are fine, decent people. ...
    (rec.radio.shortwave)