Last Digit of 3^999: Solving the Puzzle

[murshid_islam]

hi
that day, a friends of mine asked me to find out the last digit of 3^999. i knew that i have to find out 3^999 mod 10. but i saw that
3^3 mod 10
= 3^7 mod 10
= 3^11 mod 10 =7
= 3^15 mod 10 =7
.
.
.
=3^999 mod 10 = 7

but i was wondering what if i want to find the last two digits of 3^999. how can i do that?

 

[vladb]

Actually 3^9 \equiv (3^3)^3 \equiv (7)^3 \equiv 7^2 \cdot 7 \equiv -1 \cdot 7 \equiv -7 \equiv 3 \mod 10, not 7 as you mentioned. But you were right about 3^{999} \equiv 7 \mod 10. (OK, you've edited your post so that's not relevant anymore)

As for the two last digits, simply use mod 100. One way I can see it as 3^{999} \equiv (3^{20})^{49} \cdot 3^{19} \equiv 1^{49} \cdot 3^{19} \equiv 67 \mod 100.

 

[murshid_islam]

As for the two last digits, simply use mod 100. One way I can see it as 3^{999} \equiv (3^{20})^{49} \cdot 3^{19} \equiv 1^{49} \cdot 3^{19} \equiv 67 \mod 100.

yeah, i knew i had to use mod 100. but how do i know that 3^20 mod 100 = 1? of course i can use a calculator and check 3^n mod 100 for n = 1, 2, ..., 20. but how can i do it without using a calculator?

 

[shmoe]

yeah, i knew i had to use mod 100. but how do i know that 3^20 mod 100 = 1? of course i can use a calculator and check 3^n mod 100 for n = 1, 2, ..., 20. but how can i do it without using a calculator?

You can consider 3^t mod 25 and mod 4 separately. Since phi(25)=20, you know 3^20=1 mod 25. 3^20=(3^2)^10=1^10=1 mod 4. Hence 3^20=1 mod 100.

 

[robert Ihnot]

FIRST IDEA: I know this isn't exactly the right way...but I thought this problem had come up before. It turns out, using my Pari computer program that 3^100=1 Mod 1000. So that if we want to know the next digit, consider 1/3 Mod 1000. Pari will solve that one too, it is 1/3=667 Mod 1000. This can be seen since 667x3=2001 congruent to 1 Mod 1000.

SECOND IDEA: We can solve this pretty much without a calculator. Phi(1000) =1000*(1-1/2)(1-1/5) =1000x2/5 =400. So 3^400 ==1 Mod 1000. Thus 3^200 ==+/-1 Mod 1000. (We don't need to know the value for 3^100 Mod 1000.) Thus 1/3 ==+/-1 mod 1000. So either we have to solve 3X==1 Mod 1000, or 3X==-1 Mod 1000.

The first case gives 1/3==667 Mod 1000 and the second -1/3 ==333 Mod 1000. The second case is not consistent with the result for two decimals already found. So the answer is 3^999 ==667 Mod 1000.

 

[murshid_islam]

Since phi(25)=20, you know 3^20=1 mod 25

how? can you please elaborate a little? is there a relationship between the phi function and "mod"?

i am quite new in number theory and modular arithmetic. so i might sound quite dumb. sorry for that.

 

[shmoe]

how? can you please elaborate a little? is there a relationship between the phi function and "mod"?

Yes, Euler's theoerm. If a and m are relatively prime the a^phi(m)=1 mod m. This is a direct generalisation of Fermat's little theorem as phi(p)=p-1 when p is a prime. You can find more detail on these in any introductory number theory text, Euler's theorem is sometimes "Euler's Totient Theorem".

i am quite new in number theory and modular arithmetic. so i might sound quite dumb. sorry for that.

No need to apologize for not knowing something! You're willing to learn, and that's all that matters here.

 

[robert Ihnot]

For 10 as a modulus, we have two primes involved 2 and 5. Any power of 2 or 5 will never be congruent to 1 Mod 10. But if we removed such numbers and consider 1,3,7,9, these 4 numbers are relatively prime to 10. Consider X from that set of 1,3,7,9; if we consider X, X^2, X^3, X^4...since we have a group, sooner or later we get X^a==X^b Mod 10. So there is a value such that X^(a-b)==1 mod 10. Since the group has only 4 members, that exponent can not exceed 4, which is the number of elements in the group. (For example take 3, 3^1==3, 3^2==9==-1, 3^3==-3, 3^4==-9==1 Mod 10.)

Now let the modulus be 1000, how many integers less than 1000 are relatively prime to 1000? Well, we must toss out all the even numbers=500, and all the multiples of 5=200, but we have counted the multiples of 10 twice, so we add them back:

1000(1-1/2)(1-1/5)= 1000(1-1/2-1/5+1/10) = 1000-500-200+100 = 400.

So there are 400 integers less than 1000 that are relatively prime and form a group. Then for any element of the group it can not generate more than 400 values witout cycling back for X^1, X^2, X^3...X^400.

So that what is needed now is Lagrange's Theorem: The order of any subgroup divides the order of the group. In this case the powers of X cycle through a subgroup and so the order of that subgroup must divide the order of the group, which is the number of elements = 400. This says for X^a==1 Mod 1000, a is a divisor of 400, so that at most a=400.

 

[murshid_islam]

No need to apologize for not knowing something! You're willing to learn, and that's all that matters here.

thanks. that was a nice thing to say.


and thanks to others (who have helped), too.