Exercise 0.3.4 ($37^{100} \mod 29$)

Question

Compute the remainder when $37^{100}$ is divided by $29$.

Richard Ganaye · Accepted Answer

\begin{proof} 
Since $29$ is a prime number, by Fermat's Theorem,
$$37^{28} \equiv 1 \pmod {29}.$$
Therefore
$$37^{100} = 37^{3\cdot 28 + 16} = (37^{28})^3 \cdot 37^{16} \equiv 37^{16}\pmod{29}.$$
Moreover, modulo $29$,
\begin{align*}
37 &\equiv 8 \
37^2 &\equiv 8^2 = 64 \equiv 6\
37^4 & \equiv 6^2 = 36 \equiv 7\
37^8 & \equiv 7^2 = 49 \equiv 20,\
37^{16} & \equiv 20^2 \equiv (-9)^2 = 81 \equiv 23 \pmod{29}.
\end{align*}
So
$$37^{100} \equiv 23 \pmod {29},$$
where $0 \leq 23 < 29$. Therefore the remainder when $37^{100}$ is divided by $29$ is $23$.
\end{proof}
With Sagemath:
\begin{verbatim}
sage: a = Mod(37, 29)
sage: a^100
23
\end{verbatim}

Exercise 0.3.4 ($37^{100} \mod 29$)

Answers

Comments

Exercise 0.3.4 ($37^{100} \mod 29$)

Answers

Comments

Add answer