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