\documentclass[a4paper,12pt]{article}
\begin{document}
\parindent=0pt
QUESTION
Explain why $2^{p-3}$ is a root of $4x\equiv1$ mod $p$, for any
odd prime $p$. Hence find the smallest positive residue of
$2^{16}$ mod 19.
ANSWER
If $p$ is odd, then gcd$(2,p)=1$ so by Fermat's Little Theorem
(th.4.2), $2^{p-1}\equiv1$ mod $p$. Thus $2^2.2^{p-1}\equiv1$ mod
$p$, that is $4.2^{p-3}\equiv1$ mod $p$. Thus $2^{p-3}$ is a
solution of the congruence $4x\equiv1$ mod $p$.
Now we know, by cor.3.6, that this congruence has a unique
solution mod $p$. Thus if we discover that $x=a$ is a solution,
we'll know that $2^{p-3}\equiv a$ mod $p$.
For our case, $p=19$, so we solve $4x\equiv1$ mod 19. We have
$4x\equiv1\equiv20$ mod 19, so on division by 9, $x\equiv 5$ mod
19. (Other methods of solution are available-you may, for example,
have multiplied the congruence through by 5.)
Thus $2^{p-3}=2^16\equiv5$ mod 19.
\end{document}