Date: Thu, 13 Apr 95 10:22:19 CDT
From: rusin (Dave Rusin)
To: hsmollett@aol.com
Subject: Re: find the fifth root mentally?
Newsgroups: sci.math

In article <3mhpor$nue@newsbf02.news.aol.com> you write:
>repeat after at most 20 times.  Out of curiousity, does anyone knmow why
>the last digit repeats after at least 4 times and the last 2 after 20
>times (why not some other number?).  How often does it take before the
>last 3 digits repeat?

You are asking for the least values of  n  and  k  so that  a^(n+k) = a^n
mod 10 (or 100, or 1000, ...) for all integers  a.  Note that a congruence
holds mod 100 (say)  if and only if it holds mod  2^2  and mod  5^2, so
it's sufficient to know something about exponentiation modulo a prime power.
Well, a basic fact is that for any odd prime power  p^r  there is an integer
a  such that all the powers  a^n are different for  n=1,2, ..., p^(r-1)*(p-1);
when  p=2  the worst you'll see is an element for which the powers
a^n  are different for  n=1, 2, ..., 2^(r-2). For any other  a  not divisible
by  p  you'll return to  a^0=1 after a number of powers which divides
this worst case. Of course if you begin with a number  a  divisible by  p
then you get a few powers starting with  a^1 = a but by the time you get
to  a^r  you have something congruent to zero mod  p^r.

Combining these two cases, the best we can say is that for all integers  a,
	a^(n+r)=a^r  mod  p^r   (where  n = p^(r-1) * (p-1) )
and that these are the smallest  n  and  r  which work for all  a, except
if  p=2, in which case you can cut  n  in half.

As I said before, a congruence holds mod 10^r  precisely when it holds mod
2^r and mod 5^r, so we have
	for all integers  a,  a^(n+r)=a^r  mod  10^r
when  n=least common multiple of  4*5^(r-1) and  2^(r-2).  This LCM is,
for r=1, 2, 3, 4  equal to  4, 20, 100, 500  respectively; for  r>4 it's
5*10^(r-2).

You should look at a book on elementary number theory. Among the relevant
theorems are  Fermat's (little) theorem  and  Euler's theorem. The
reason I could say "divides" rather than "is less than" in a few spots is
because of Lagrange's theorem, which will be in a group theory book.
A book such as Beachy and Blair "Abstract Algebra" will serve.

dave