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