Congruences
Author
Marshal
License
Creative Commons CC BY 4.0
Abstract
Fast exponentiation
Fast exponentiation
\documentclass[14pt]{article}
\def\Z{\mathbb Z}
\def\N{\mathbb N}
\def\Q{\mathbb Q}
\def\R{\mathbb R}
\def\C{\mathbb C}
\begin{document}
Name: Marshal Thrasher
\vspace{.5in}
Congruence 1. Find an integer $x$ such that $4^{128} \equiv x$ $mod 9$ and $0 \leq x \leq 100$.
\vspace{.25in}
\hspace{.5in} If we begin with $4 \equiv 4$ $mod9$ and also, $4^2 \equiv 7$ $mod9$, then by Proposition 21, we can say:
\begin{center}
$4^3 \equiv 28$ $mod9$ (where $1$ also works for $28$)
\end{center}
If we repeat the original process with $4^3$ until we get to $4^{126}$, we can then utilize the $4$ and $4^2$ values respectively:
\begin{center}
$4^{127} \equiv 4$ $mod9$
\end{center}
and finally
\begin{center}
$4^{128} \equiv 7$ $mod9$.
\end{center}
\vspace{.5in}
Congruence 2. Find an integer $y$ such that $3^{128} \equiv y$ $mod 4$ and $0 \leq y \leq 3$.
\vspace{.25in}
\hspace{.5in} If we begin with \\
\begin{center}
$3 \equiv 3$ $mod4$, \\
$3^2 \equiv 1$ $mod4$, \\
$3^3 \equiv 3$ $mod4$, \\
$3^4 \equiv 1$ $mod4$, \\
\end{center}
then by Proposition 21, we can say:
\begin{center}
$3^6 \equiv 1$ $mod4$, \\
\end{center}
Considering $128$ is an even integer and $3^2 \equiv 1$ $mod4$, we can do this until we get to $3^{128} \equiv 1$ $mod4$.
\clearpage
Congruence 3. For each of the following congruence's, find integers $x_{i}$ such that $0 \leq x_{i} \leq 6$ that satisfy the congruence.
\vspace{.25in}
\hspace{.5in}
\end{document}