2
$\begingroup$

Find the last two digit of $3^{3^{100}}$.

I know how to calculate if I have $3^{100}$. That I will use euler's theorem. which gives me $3^{40}\equiv 1 \pmod{100}$. And so on... but if I have $3^{3^{100}}$ what should I do?

I Tried:

Infact, i need $3^{3^{100}}\equiv x\pmod{ 100}$

For this, I need $3^{100}\equiv y\pmod{\phi{(100)}}$

So i got $y=1$ by using eulers thorem for the abouve cogruence.

That is $(3,40)=1\implies 3^{16}\equiv 1\pmod{40}$

So, i got $(3^{16})^63^4\equiv 1\pmod{40}$

Using this in first congruence i got $3^1\equiv 3\pmod{100}$.

So, the answer is $03$. Is it correct?

I did't use chinese remainder theorem and all. Is there any mistake in my arguments?

$\endgroup$
2
2
$\begingroup$

you are right with Euler's theorem. $100=2^{2}5^{2}$ and $\phi{(100)}=40=(2^{2}-1)=(5^{2}-5)$, so by Euler's theorem you have : $3^{40k+1}\equiv3\pmod{100}$ then, you have $3^{100}\equiv1\pmod{40}$ this finally gives you : $3^{3^{100}}\equiv3\pmod{100}$ and so, the last two digits of your number are 3 and 0.

$\endgroup$
1
  • $\begingroup$ thank you this is what i want.@Aurelian $\endgroup$ – Rising Star Oct 2 '14 at 12:05
3
$\begingroup$

If we can find $3^{3^{100}}$ in mods 4 and 25 we're done by the Chinese Remainder Theorem.

Mod 4: Note that $3\equiv -1\pmod 4$, hence $3^{3^{100}}\equiv (-1)^{3^{100}}\equiv (-1)^{2k+1}\equiv -1\equiv 3\pmod 4$.

Mod 25: Since $\varphi(25)=20$ we have $3^{3^{100}}\equiv 3^{3^{100}\pmod {20}}\pmod {25}$. Similarly, $3^{100}\equiv 3^{100\pmod 8}\pmod {20}$, and $100\equiv 4\pmod 8$. Hence, working backwards we get:

$3^{100}\equiv 3^{100\pmod 8}\equiv 3^4\equiv 1\pmod {20}$,

$3^{3^{100}}\equiv 3^{3^{100}\pmod {20}}\equiv 3^1\equiv 3\pmod {25}$.

Thus, threading the congruences together we have:

$3^{3^{100}}=4a+3=25b+3$, or $4a=25b$. So since $\gcd(4,25)=1$ we need $a=25k$. Therefore $3^{3^{100}}=4(25k)+3=100k+3$, so the answer is $\boxed{03}$.

$\endgroup$
0
0
$\begingroup$

Any base to a power has a pattern. So if I consider powers of 3, $3,9,27,81,243$ you notice that the end digits follow the pattern $3,9,7,1$. You can generalize that any power mod 4 (the number of elements in the pattern) will "end" in the corresponding element in this pattern.

for two digits of the answer, you must take $3^{3^{100}} (mod 100)$, which follows a similar strategy, but the pattern (the last 2 digits of the power) will be a little bit longer.

$\endgroup$
1
  • $\begingroup$ i have already quoted that i know this.. but how is the question.@Stretch Maniac $\endgroup$ – Rising Star Oct 2 '14 at 11:44
-1
$\begingroup$

$3^{100}=1+40 k$ for some $k\in Z$, therefore the result is $3^{3^{100}}=...03$.

(It is easy to check: $3^{100}=1 \mod 5$ and $3^{100}=1 \mod 8$, from where we get $3^{100}=1 \mod 40$).

$\endgroup$
-1
$\begingroup$

Using a standard calculator, you find in twenty seconds that the first power of $3$ ending in $01$ is $20$, so the exponents can be taken $\bmod 20$ (and as $20$ divides $100$, only the last two digits matter).

Thus $3^{100}$ ends like $3^0=1$, and $3^{3^{100}}$ ends like $3^1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.