last digits of 3^999

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 [latex]3^9 \equiv (3^3)^3 \equiv (7)^3 \equiv 7^2 \cdot 7 \equiv -1 \cdot 7 \equiv -7 \equiv 3 \mod 10 [/latex], not 7 as you mentioned. But you were right about [latex] 3^{999} \equiv 7 \mod 10 [/latex]. (OK, you've edited your post so thats not relevant anymore)

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

murshid_islam

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

You can consider 3^t mod 25 and mod 4 seperately. 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 consistant with the result for two decimals already found. So the answer is 3^999 ==667 Mod 1000.

murshid_islam

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

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

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

thanks. that was a nice thing to say.


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