Difference between revisions of "Mock AIME 4 2006-2007 Problems/Problem 7"

Revision as of 11:49, 8 October 2007

Find the remainder when $3^{3^{3^3}}$ is divided by 1000.

Fermat's little theorem comes in handy here:

$3^{400}\equiv 1 \pmod {1000}$

So we are looking for $3^{27} \pmod {400}$

$3^{27}=(3^9)^3=(27^3)^3$

We brute force it:

$27^3=729*27=19683$

$19683 \equiv 83 \pmod {400}$

$83^2=6889$

$83^3 \equiv 187 \pmod {400}$

$3^{27} \equiv 187 \pmod {400}$

$3^{3^{3^3}} \equiv 3^{187} \pmod {1000}$

This problem needs a solution. If you have a solution for it, please help us out by adding it.

@@ Line 2: / Line 2: @@
 Find the remainder when <math>3^{3^{3^3}}</math> is divided by 1000.
 ==Solution==
+Fermat's little theorem comes in handy here:
+<math>3^{400}\equiv 1 \pmod {1000}</math>
+So we are looking for <math>3^{27} \pmod {400}</math>
+<math>3^{27}=(3^9)^3=(27^3)^3</math>
+We brute force it:
+<math>27^3=729*27=19683</math>
+<math>19683 \equiv 83 \pmod {400}</math>
+<math>83^2=6889</math>
+<math>83^3 \equiv 187 \pmod {400}</math>
+<math>3^{27} \equiv 187 \pmod {400}</math>
+<math>3^{3^{3^3}} \equiv 3^{187} \pmod {1000}</math>
 {{solution}}
 ----