Exercise 3.2.23 (Last two digits of $3^{3^{100}}$)

Question

Determinate the last two digits of $3^{3^{100}}$. [Determine $3^{100} \mod \varphi(100)$ and use the previous exercise.]

Richard Ganaye · Accepted Answer

\begin{proof} 
First 
$$\varphi(100) = \varphi(2^2 \cdot 5^2) =  \varphi(2^2) \varphi(5^2) = (2^2 - 2)(5^2 - 5) = 40 = 8\cdot 5.$$
Since $3^{4} \equiv 1 \pmod 5$, then $3^{100} = (3^4)^{25} \equiv 1 \pmod {40}$, and since $3^2 \equiv 1 \pmod 8$, $3^{100} = (3^2)^{50} \equiv 1 \pmod 8,$
So
$$3^{100} \equiv 1 \pmod 5,\qquad 3^{100} \equiv 1 \pmod 8.$$
Since $5$ and $8$ are relatively prime, $3^{100} \equiv 1 \pmod {40}$, so
$$3^{100} \equiv 1 \pmod{\varphi(100)}.$$
There is some positive integer $k$ such that $3^{100} = k \varphi(100) + 1$. By Euler's Theorem (Exercise 22), $3^{\varphi(100)} \equiv 1 \pmod {100}$, therefore
$$3^{3^{100}} = (3^{\varphi(100)})^k \cdot  3^1 \equiv 3 \pmod{100}.$$
Hence the two last digits of $3^{3^{100}}$ are $03$.
\end{proof}
Verification with Sagemath:
\begin{verbatim}
sage: a = mod(3,100)
sage: a^(3^100)
3
\end{verbatim}

Exercise 3.2.23 (Last two digits of $3^{3^{100}}$)

Answers

Comments

Exercise 3.2.23 (Last two digits of $3^{3^{100}}$)

Answers

Comments

Add answer