Last Digit of 3^999: Solving the Puzzle

  • Thread starter murshid_islam
  • Start date
In summary, when trying to find the last two digits of 3^999, use mod 100. If you want to find the last digits of 3^9, use mod 10 and Phi(25)=20.
  • #1
murshid_islam
457
19
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?
 
Last edited:
Physics news on Phys.org
  • #2
Actually [itex]3^9 \equiv (3^3)^3 \equiv (7)^3 \equiv 7^2 \cdot 7 \equiv -1 \cdot 7 \equiv -7 \equiv 3 \mod 10 [/itex], not 7 as you mentioned. But you were right about [itex] 3^{999} \equiv 7 \mod 10 [/itex]. (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 [itex] 3^{999} \equiv (3^{20})^{49} \cdot 3^{19} \equiv 1^{49} \cdot 3^{19} \equiv 67 \mod 100 [/itex].
 
Last edited:
  • #3
vladb said:
As for the two last digits, simply use mod 100. One way I can see it as [itex] 3^{999} \equiv (3^{20})^{49} \cdot 3^{19} \equiv 1^{49} \cdot 3^{19} \equiv 67 \mod 100 [/itex].

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? :confused:
 
  • #4
murshid_islam said:
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? :confused:

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.
 
  • #5
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.
 
Last edited:
  • #6
shmoe said:
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.
 
  • #7
murshid_islam said:
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".

murshid_islam said:
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.
 
  • #8
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.
 
Last edited:
  • #9
shmoe said:
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. :smile:
 

What is the puzzle "Last Digit of 3^999"?

The puzzle "Last Digit of 3^999" involves finding the last digit of the number 3 raised to the power of 999. This is a common math puzzle that tests one's understanding of number patterns and powers.

What is the significance of finding the last digit of 3^999?

The significance of finding the last digit of 3^999 lies in its application to real-world problems, such as encryption and cryptography. It also helps in understanding the behavior of numbers and their patterns.

How can I solve the puzzle "Last Digit of 3^999"?

To solve the puzzle "Last Digit of 3^999", you can use the concept of cyclicity of numbers. The last digit of 3^999 will be the same as the last digit of 3^9, which is 7. This can be explained by the fact that the last digit of 3 follows a pattern of 3, 9, 7, 1, and then repeats. Therefore, the last digit of 3^999 will also be 7.

Can I use a calculator to solve the puzzle "Last Digit of 3^999"?

Yes, you can use a calculator to solve the puzzle "Last Digit of 3^999". However, it is recommended to use mental math and concepts of cyclicity to strengthen your mathematical skills.

What other puzzles can I solve using the concept of cyclicity?

The concept of cyclicity can be applied to various puzzles and problems, such as finding the last digit of any number raised to a power, determining the period of a repeating decimal, and solving certain types of equations. It is a useful tool in number theory and can be applied to many math problems.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
3
Views
2K
Replies
10
Views
3K
  • Beyond the Standard Models
Replies
7
Views
607
  • Linear and Abstract Algebra
Replies
3
Views
718
Replies
4
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
7
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
1K
Replies
10
Views
33K
  • Programming and Computer Science
Replies
1
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
Back
Top