\input{preamble}
\begin{document}

\begin{center}
  Fall 2021 -- Math 328K -- 55385
\end{center}
\section*{Homework 5}
\begin{center}
  \itshape due Tuesday, October 5, 14:00
\end{center}

\begin{problem}
  Find all solutions in $\bZ/243\bZ$ to the following equations:
  \begin{enumerate}[a)]
  \item $18x = 27$,
  \item $3x = 3$,
  \item $5x = 17$,
  \item $6x = 19$.
  \end{enumerate}
  Is it a valid strategy to simplify such an equation by dividing both sides by the greatest common divisor, for example replacing $18x = 27$ by $2x = 3$? Why/why not?
\end{problem}

\begin{problem}
  Let $p$ be an odd prime and $a \in \bZ/p\bZ$ with $a \neq 0 \mod p$. A \emph{square root} of $a$ is a solution $x \in \bZ/p\bZ$ of the equation $x^2 = a$.

  \begin{enumerate}[a)]
  \item Show that every $a \in \bZ/p\bZ \setminus \{0 \mod p\}$ has either none or exactly two square roots.
  \item Conclude that $\bZ/p\bZ$ has exactly two elements which are their own inverses.
  \item Find the square roots of all elements of $\bZ/7\bZ$, if they exist.
  \item Is the statement of a) still true if $p$ is not prime?
  \end{enumerate}
\end{problem}

\begin{problem}
  Show that the equation $x^2 = 1$ has one solution in $\bZ/2\bZ$, two solutions in $\bZ/4\bZ$ and four solutions in $\bZ/{2^k}\bZ$ for all integers $k > 2$.
\end{problem}

\begin{problem}
  Let $a,b,c \in \bN$ with
  \[a \mod c = b \mod c.\]
  Show that
  \[(2^a - 1) \mod (2^c - 1) = (2^b - 1) \mod (2^c - 1).\]
\end{problem}

\begin{problem}
  Find inverses of $[1]$, $[2]$, $[3]$, $[4]$ and $[5]$ in $\bZ/{8512}\bZ$, if they exist.
\end{problem}

\end{document}
