Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

across

This question is just for fun: Tell me what the last digit of \(3^{1234567890}\) is. :) Then tell me what the last two digits are. And if you feel up to the challenge, then tell me what the last three digits are!

  • 2 years ago
  • 2 years ago

  • This Question is Closed
  1. muhammadturawa
    Best Response
    You've already chosen the best response.
    Medals 0

    3

    • 2 years ago
  2. across
    Best Response
    You've already chosen the best response.
    Medals 7

    That's not it!

    • 2 years ago
  3. across
    Best Response
    You've already chosen the best response.
    Medals 7

    \[\text{Hint: }a^{\phi(n)}\equiv1\text{ }(\text{mod }n)\text{, where }\gcd(a,n)=1.\]

    • 2 years ago
  4. muhammadturawa
    Best Response
    You've already chosen the best response.
    Medals 0

    quite tricky...:)

    • 2 years ago
  5. myininaya
    Best Response
    You've already chosen the best response.
    Medals 0

    Is that fermat's or euler's thingy...I can't remember

    • 2 years ago
  6. across
    Best Response
    You've already chosen the best response.
    Medals 7

    You are right. :) This is Euler's theorem, and ϕ is the totient function. Naturally, it is an augmentation of Fermat's little theorem.

    • 2 years ago
  7. satellite73
    Best Response
    You've already chosen the best response.
    Medals 1

    fermat's little theorem \[a^{p-1}\equiv 1( \text{ mod } p)\] euler phi totient function \[a^{\phi(n)}\equiv 1 (\text{ mod } n)\] if \[(a,n)=1\]

    • 2 years ago
  8. satellite73
    Best Response
    You've already chosen the best response.
    Medals 1

    glad you are back!

    • 2 years ago
  9. myininaya
    Best Response
    You've already chosen the best response.
    Medals 0

    I think @jamesj and @zarkon would love this question (maybe-lol) I will keep thinking on it though Great question @across

    • 2 years ago
  10. TuringTest
    Best Response
    You've already chosen the best response.
    Medals 1

    the last digit is 9, no?

    • 2 years ago
  11. across
    Best Response
    You've already chosen the best response.
    Medals 7

    Yes it is. :) Did you use Euler's theorem?

    • 2 years ago
  12. TuringTest
    Best Response
    You've already chosen the best response.
    Medals 1

    no I used a little logic no idea what that theorem is

    • 2 years ago
  13. TuringTest
    Best Response
    You've already chosen the best response.
    Medals 1

    \[3^0=1\]\[3^1=3\]\[3^2=9\]last digit is nine is the important point here\[3^3=27\]\[3^4=81\]and so the last digit repeats every four powers...

    • 2 years ago
  14. TuringTest
    Best Response
    You've already chosen the best response.
    Medals 1

    1,3,9,7,1,3,... so 1234567890/4=308641927+2/4 and 3^2=9

    • 2 years ago
  15. TuringTest
    Best Response
    You've already chosen the best response.
    Medals 1

    I'm sure that's got a professional way of writing it with mod this and that, but that's beyond me lol

    • 2 years ago
  16. Zarkon
    Best Response
    You've already chosen the best response.
    Medals 0

    29

    • 2 years ago
  17. TuringTest
    Best Response
    You've already chosen the best response.
    Medals 1

    how you got the other digit is what I want to know

    • 2 years ago
  18. across
    Best Response
    You've already chosen the best response.
    Medals 7

    That is genius. :) Do you know that you are intuitively deriving the above theorem? From it, it follows that to find out what the last two digits of that number are, you first need to observe that the sequence of two digits repeats every 40 powers. I will elaborate more on it a bit later. :)

    • 2 years ago
  19. across
    Best Response
    You've already chosen the best response.
    Medals 7

    I am pretty sure you can figure out what those two digits are by having told you that up there. ;)

    • 2 years ago
  20. across
    Best Response
    You've already chosen the best response.
    Medals 7

    @Zarkon, that is not it!

    • 2 years ago
  21. TuringTest
    Best Response
    You've already chosen the best response.
    Medals 1

    thank you for the compliment across, it means so much knowing who it's coming from :D

    • 2 years ago
  22. Zarkon
    Best Response
    You've already chosen the best response.
    Medals 0

    49

    • 2 years ago
  23. across
    Best Response
    You've already chosen the best response.
    Medals 7

    ^.^ And @Zarkon, you are right. Let us in in thy arcane ways!

    • 2 years ago
  24. across
    Best Response
    You've already chosen the best response.
    Medals 7

    Anyway, :) to re-state Euler's theorem:\[a^{\phi(n)}\equiv1\text{ }(\text{mod }n)\text{, where }\gcd(a,n)=1.\]And to define Euler's phi-function:\[\phi(n)=\text{number of positive integers relatively prime to }n.\]By the way, I will now say that what I am about to explain is a huge over-simplification of the number theory behind it all, and that I have boiled the entire process down to a series of mechanical steps stemming from said theory. Since we are trying to find out what the last few digits of \(a=3^{1234567890}\) are, all that we have to do is compute \(a\text{ }(\text{mod }10)\) for the last digit, \(a\text{ }(\text{mod }100)\) for the last two digits, and so on. Notice that \(\gcd(3,10)=\gcd(3,100)=\cdots=1\), so we can indeed make use of the above theorem. Because it really does not pertain to the problem at hand, I will just say that \(\phi(10)=4\), \(\phi(100)=40\), and so on. Therefore, we have that \(3^{\phi(10)}\equiv3^4\equiv1\text{ }(\text{mod }10)\) (check this to convince yourself that it is true), and it follows that, for the last digit, \[3^{1234567890}\equiv3^2\cdot(3^4)^{308641972}\equiv3^2\cdot(1)^{308641972}\equiv9\text{ }(\text{mod }10).\]Which is indeed our last digit. You can do the same thing for two digits:\[3^{1234567890}\equiv3^{10}\cdot(3^{40})^{30864197}\equiv3^{10}\cdot(1)^{30864197}\equiv49\text{ }(\text{mod }100).\]This can go on and on. For three digits, you will have to compute \(3^{290}\), which is doable by Windows' calculator. But there are better methods for bigger and bigger numbers. :)

    • 2 years ago
  25. myininaya
    Best Response
    You've already chosen the best response.
    Medals 0

    Very nice across :)

    • 2 years ago
  26. KingGeorge
    Best Response
    You've already chosen the best response.
    Medals 0

    Can I do the last 3 digits? Using Euler's theorem, we know that \(\phi(1000)=400\) so \(3^{400} \equiv 1 \mod 1000\). Now we calculate \(1234567890 \mod 400\). As it turns out, this is 290. Thus, we only have to calculate \(3^{290} \mod 1000\). Using successive squaring/fast powering, this is easy, and we get that the last three digits are 449.

    • 2 years ago
  27. across
    Best Response
    You've already chosen the best response.
    Medals 7

    That is correct. :)

    • 2 years ago
  28. FoolForMath
    Best Response
    You've already chosen the best response.
    Medals 0

    It's good to mention Carmichael theorem in this context. http://en.wikipedia.org/wiki/Carmichael_function#Carmichael.27s_theorem

    • 2 years ago
  29. FoolForMath
    Best Response
    You've already chosen the best response.
    Medals 0

    And if you are in a hurry, just a one liner in python: http://ideone.com/47UX7

    • 2 years ago
  30. ParthKohli
    Best Response
    You've already chosen the best response.
    Medals 0

    Woot, solution number two!\[3^n \equiv 3^{n-4} \times 3^4 \equiv 3^{n -4}\pmod{10} \]Suffice to say that \(3^{n} \equiv 3^{n - 4k} \pmod {10}\) for all integer \(k\). Well, that's just the solution @TuringTest posted.

    • one year ago
    • Attachments:

See more questions >>>

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.