Difference between revisions of "Mock AIME 4 2006-2007 Problems/Problem 7"
(Please check for rigor, improve if necessary,) |
|||
Line 1: | Line 1: | ||
==Problem== | ==Problem== | ||
Find the remainder when <math>3^{3^{3^3}}</math> is divided by 1000. | Find the remainder when <math>3^{3^{3^3}}</math> is divided by 1000. | ||
+ | |||
==Solution== | ==Solution== | ||
+ | <math>\phi (1000)=400</math>, so <math>3^{400}=1\bmod 1000</math>. | ||
− | + | Therefore, we want <math>3^{27} \bmod 400</math>. | |
− | |||
− | <math>3^{ | ||
− | + | Since <math>400=2^4*5^2</math>, we want <math>3^{27}\bmod 16</math> and <math>3^{27} \bmod 25</math>. | |
− | <math>3^{ | + | <math>3^{4} \equiv 1\bmod 16</math>, so <math>3^{27}\equiv 11\bmod 16</math>. |
− | + | Since <math>3^{\phi(25)}=3^{20}\equiv 1\bmod 20</math>, <math>3^{27}\equiv 3^7\equiv 18\bmod 25</math>. | |
− | <math> | + | The only number <math>\bmod 400</math> that is <math>11\bmod 16</math> and <math>18\bmod 25</math> is <math>43\bmod 400</math>. Therefore, |
− | <math> | + | <math>3^{3^{3^3}}\equiv 3^{43} \bmod 1000</math>. |
− | <math> | + | Since <math>1000=8*125</math>, we want to find <math>3^{43}\bmod 8</math> and <math>3^{43}\bmod 125</math>. |
− | <math> | + | Since <math>3^4\equiv 1\bmod 8</math>, <math>3^{43}\equiv 27\equiv 3\bmod 8</math>. |
+ | And since <math>3^5\equiv -7\bmod 125</math>, <math>3^{10}\equiv 49\bmod 125</math>, <math>3^{20}\equiv 26\bmod 125</math>, <math>3^{40}\equiv 1\bmod 125</math>. | ||
− | + | We have gotten somewhere. | |
− | <math>3^{ | + | <math>3^{43}\equiv 27\bmod 125</math> |
− | { | + | The only number <math>\bmod 1000</math> that satisfies <math>3\bmod 8</math> and <math>27\bmod 125</math> is <math>\boxed{027}\bmod 1000</math>. |
− | + | == See also== | |
*[[Mock AIME 4 2006-2007 Problems/Problem 8| Next Problem]] | *[[Mock AIME 4 2006-2007 Problems/Problem 8| Next Problem]] | ||
*[[Mock AIME 4 2006-2007 Problems/Problem 6| Previous Problem]] | *[[Mock AIME 4 2006-2007 Problems/Problem 6| Previous Problem]] | ||
*[[Mock AIME 4 2006-2007 Problems]] | *[[Mock AIME 4 2006-2007 Problems]] |
Revision as of 14:17, 13 February 2008
Problem
Find the remainder when is divided by 1000.
Solution
, so
.
Therefore, we want .
Since , we want
and
.
, so
.
Since ,
.
The only number that is
and
is
. Therefore,
.
Since , we want to find
and
.
Since ,
.
And since ,
,
,
.
We have gotten somewhere.
The only number that satisfies
and
is
.