\documentclass[a4paper,12pt]{article}

\begin{document}

\parindent=0pt

QUESTION

Find the least positive residue of $3^{67}$ mod 31.



ANSWER

As 31 is prime, and gcd(3,31)=1, Fermat's little theorem (Th.4.2)
gives $3^{30}\equiv1$ mod 31.

Thus $3^67=3^30.3^30.3^7\equiv1.1.3^7$ mod 31. But
$3^3=27\equiv-4$ mod 31, and so $3^7\equiv
(-4).(-4).3\equiv48\equiv17$ mod 31. Thus $3^{67}\equiv 17$ mod
31.




\end{document}