Question about finding last digits of numbers

[abertram28]

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 won't be able to get a wink of meaningful sleep!

 

[robert Ihnot]

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 written 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.

 

[M98Ranger]

First of all, great job on finding the pattern and using it to solve the problem! It seems like you have a good understanding of how the last digits of numbers repeat in certain intervals. To answer your question about why this happens, it is because of the concept of cyclicity in modular arithmetic.

Cyclicity refers to the repeating patterns that occur in modular arithmetic when raising a number to different powers. In your case, you are dealing with numbers in base 10, so the cyclicity will depend on the base. For example, in base 10, the last digit of a number will repeat every 4 powers, and the last two digits will repeat every 20 powers. This is why you noticed that (k mod 4) and (k mod 20) were not always the smallest values, because they were just representing the repeating interval.

For perfect squares, the cyclicity is even simpler. In your example, 4 is a perfect square, so the last two digits of 4^k will always be the same as the last two digits of 4^(k mod 10). This is because when squaring a number, the last digit will always be the same, and the second to last digit will depend on whether k is even or odd. So for example, 4^5 will have the same last two digits as 4^1, and 4^6 will have the same last two digits as 4^2, and so on.

To find the value for mod 1000, you can use the same concept of cyclicity. The last three digits of a number will repeat every 1000 powers, so you can find the lowest power of 37^k that shares three last digits with 37^2005 by finding the remainder of 2005 when divided by 1000. This would be 5, so the lowest power would be 37^5, which you already found to have the same last two digits as 37^2005.

I hope this explanation helps and you can finally get some sleep! Keep up the good work with number theory.