Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Question about finding last digits of numbers

  1. Mar 10, 2005 #1
    I know that any number p-prime, p^k (mod 10) = [p^(k mod 4)] (mod 10)
    and I also know p^k (mod 100) = [p^(k mod 20)] (mod 100)

    this means that the number 37^2005 has the same final two digits as 37^5, which is what I used as my answer for the problem. Through some playing around, I found this statement above to satisfy all numbers, but for some numbers the (k mod 4) and (k mod 20) were not the smallest, meanning, the final two digits repeat much more often. take 10, 10^2 mod 100 = 00, and so squaring both sides of the congurency 10^2k congruent to 00 again. i know its also true for p^(2k+1) (its obvious) but I suck at showing why. also, for perfect squares, like 4, since its 2^2, p^k (mod 100) is congruent to p^(k (mod 10)) (mod 100)....

    I am having trouble finding number theoretic functions to define why this p^k repeats in 4 times for mod 10 and 20 times for mod 100, and id like to know what the value is for mod 1000, so that i could find the lowest power of 37^k that shares three last digits with 37^2005, and that was the extra credit part of the question. i already handed it in, but i NEED to know before spring break is over or i wont be able to get a wink of meaningful sleep!
     
  2. jcsd
  3. Mar 11, 2005 #2
    Consider the Euler Totient function (http://primes.utm.edu/glossary/page.php?sort=EulersPhi) which finds the number of relatively prime numbers less than a given N. F(10) = F(2)xF(5) = 1x4=4. F(100) = 25(1-1/5)(4)(1-1/2) = 40. For F(1000), we can use the formula, or since this are all very simple cases to figure out, we also look at it this way:

    2 and 5 are the only primes involved, of the 1000 numbers 500 are even, 200 are divisible by 5 and 1/10 has been counted twice. So we have for relatively prime numbers: 1000-1000/2-1000/5 + 1000/10 = 400.

    The relatively prime integers involved form a group, who's order is the number of its totient function. Thus the order of any element divides F(n). This is to say, X^F(n) ==1 Mod n. So F(n) presents an upper bound. CAUTION: Do not confuse this set with numbers containing 2 or 5 as a factor, since it is impossible for 2 or 5 raised to any power to be congruent to 1 modulo 100.

    Thus if x is relatively prime to 100, x^40 ==1 Mod 100. But, as you realize here there may be a lower number that will also work for all such x.

    You have to get a little creative here and look beyond the totient function, examine its divisors. Now take the case for N=10, what are the relatively prime numbers less than 10? Answer: 1, 3, 7, 9, which can be also writen as u = +/-1, +/-3, (plus or minus 1, plus or minus 3). Now suppose we look beyond this to case for 100? What are the numbers sought?

    Answer is the previously defined u and the form u+10x for x=0 to 9. Checking this out for the exponent 20 we get:

    (u+10x)^20 ==u^20 Mod 100. In fact we could have even tried it for 10, (u+10x)^10 ==u^10 Mod 100.

    Since the exponent e=10 or 20 is even in both cases, we know result is u^e==1 Mod 100 for u =+/-1, and the case for -3 is the same as for +3. Thus we examine two cases 3^10 Mod 100 and 3^20 Mod 100.

    3^5 ==243==43 Mod 100; 3^10 ==49 Mod 100; 3^20==49^2==1 Mod 100. Since if also consider the case without the divisor 5, 3^4==81 Mod 100, we can conclude that 20 is the smallest exponent that will work in all cases.

    Of course, for the case of 37^2005, we could have used the 40 in any case, arriving at 37^5 ==69343957==57 Mod 100.

    The case for 1000 proceeds similarly.
     
    Last edited: Mar 11, 2005
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?