across
  • 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!
Mathematics
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
jamiebookeater
  • jamiebookeater
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
muhammadturawa
  • muhammadturawa
3
across
  • across
That's not it!
across
  • across
\[\text{Hint: }a^{\phi(n)}\equiv1\text{ }(\text{mod }n)\text{, where }\gcd(a,n)=1.\]

Looking for something else?

Not the answer you are looking for? Search for more explanations.

More answers

muhammadturawa
  • muhammadturawa
quite tricky...:)
myininaya
  • myininaya
Is that fermat's or euler's thingy...I can't remember
across
  • across
You are right. :) This is Euler's theorem, and ϕ is the totient function. Naturally, it is an augmentation of Fermat's little theorem.
anonymous
  • anonymous
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\]
anonymous
  • anonymous
glad you are back!
myininaya
  • myininaya
I think @jamesj and @zarkon would love this question (maybe-lol) I will keep thinking on it though Great question @across
TuringTest
  • TuringTest
the last digit is 9, no?
across
  • across
Yes it is. :) Did you use Euler's theorem?
TuringTest
  • TuringTest
no I used a little logic no idea what that theorem is
TuringTest
  • TuringTest
\[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...
TuringTest
  • TuringTest
1,3,9,7,1,3,... so 1234567890/4=308641927+2/4 and 3^2=9
TuringTest
  • TuringTest
I'm sure that's got a professional way of writing it with mod this and that, but that's beyond me lol
Zarkon
  • Zarkon
29
TuringTest
  • TuringTest
how you got the other digit is what I want to know
across
  • across
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. :)
across
  • across
I am pretty sure you can figure out what those two digits are by having told you that up there. ;)
across
  • across
@Zarkon, that is not it!
TuringTest
  • TuringTest
thank you for the compliment across, it means so much knowing who it's coming from :D
Zarkon
  • Zarkon
49
across
  • across
^.^ And @Zarkon, you are right. Let us in in thy arcane ways!
across
  • across
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. :)
myininaya
  • myininaya
Very nice across :)
KingGeorge
  • KingGeorge
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.
across
  • across
That is correct. :)
anonymous
  • anonymous
It's good to mention Carmichael theorem in this context. http://en.wikipedia.org/wiki/Carmichael_function#Carmichael.27s_theorem
anonymous
  • anonymous
And if you are in a hurry, just a one liner in python: http://ideone.com/47UX7
ParthKohli
  • ParthKohli
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.

Looking for something else?

Not the answer you are looking for? Search for more explanations.