\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}