In article <MPG.22865099b5c7cbd298b61d@[EMAIL PROTECTED]
>,
Stan Brown <the_stan_brown@[EMAIL PROTECTED]
> wrote:
> Fri, 02 May 2008 23:33:59 -0600 from Virgil <Virgil@[EMAIL PROTECTED]
>:
> > In article <030520080037307285%plsperry@[EMAIL PROTECTED]
>,
> > Paul Sperry <plsperry@[EMAIL PROTECTED]
> wrote:
> >
> > > --
> > > Paul Sperry
> > > Columbia, SC (USA)
> >
> > 4 == -1 (mod 5) so 4^n == (-1)^n (mod 5).
>
> I never really studied exponents in modular arithmetic, so thinking
> out loud I'll try to apply this to 3^n mod 5:
The exponent property is based on a result I'm sure you know: If a = b
(mod m) and c = d (mod m), then ac = bd (mod m). Proving a = b (mod
m) => a^n = b^n (mod m) for n = 1, 2, ... is then a two-line induction
argument.
> (-2)^n mod 5 could be anything but 0.
> Hmm: 3, 9, 27, 81, 243, 729, ...
> Seems to work.
>
> I'm guessing that this is a shorthand for binomial expansion. I could
> write out
>
> 3^n = (5-2)^n
> = 5^2 + n*(-2)*5^(n-1) + ... + n*(-2)^(n-1)*5 + (-2)^n
>
> Taking that modulo 5, every term drops out except the last. So
>
> 3^n mod 5 = (-2)^n mod 5.
>
> What can the values of (-2)^n mod 5 be? -2 becomes 3, 4, -8 becomes
> 2, 16 becomes 1, -32 becomes 3, 64 becomes 4, -128 becomes 2, 256
> becomes 1, -512 becomes 3, anything but 0.
>
> It seems that 3^n mod 5 or (-2)^n mod 5 cycles 3,4,2,1 endlessly. I
> guess an inductive proof would be necessary to show it rigorously.
|
