\input{preamble}
\begin{document}

\begin{center}
  Fall 2021 -- Math 328K -- 55385
\end{center}
\section*{Homework 10}
\begin{center}
  \itshape due Thursday, November 11, 14:00
\end{center}

\begin{problem}
  Let $m,k \in \bZ_+$ and $a \in (\bZ/m\bZ)^\times$. Show that
  \[\ord(a^k) = \frac{\ord(a)}{(\ord(a),k)}.\]
\end{problem}

\begin{problem}
  Let $m \in \bZ_+$ be a positive integer such that $\bZ/m\bZ$ has a primitive root. Show the following generalization of Wilson's Theorem:
  \[\prod_{x \in (\bZ/m\bZ)^\times} x = -1.\]
\end{problem}

\begin{problem}\
  \begin{enumerate}[a)]
  \item Let $p$ be an odd prime. Show that the equation $x^4 = -1$ has a solution in $\bZ/p\bZ$ if and only if
    \[p \bmod 8 = 1 \bmod 8,\]
    and has exactly $4$ solutions in that case.
  \item Let $m \in \bZ_+$ and write $m = 2^{i_0}p_1^{i_1} \cdots p_k^{i_k}$ for distinct odd primes $p_1,\dots,p_k$, $i_0 \geq 0$, and $i_1, \dots, i_k \geq 1$. Show the equation $x^4 = -1$ has a solution in $\bZ/m\bZ$ if and only if
    \[i_0 \in \{0,1\} \quad \text{and} \quad p_j \mod 8 = 1 \mod 8 \quad \text{for all $j \in \{1,\dots,k\}$},\]
    and has exactly $4^k$ solutions in that case.
  \end{enumerate}

\end{problem}

\begin{problem}
  The $n$--th \emph{Fermat number} is $F_n = 2^{2^n}+1$ (the exponent is $2^n$).
  \begin{enumerate}[a)]
  \item Show that $\ord_{F_n}2 \leq 2^{n+1}$.

    {\itshape A remark on notation: for coprime $a \in \bZ$ and $m \in \bZ_+$, the expressions $\ord_ma$, $\ord_m[a]_m$, and $\ord{[a]_m}$ all mean the same thing, the order of $[a]_m$ in $(\bZ/m\bZ)^\times$.}
  \item Suppose $p$ is a prime divisor of $F_n$, show that $\ord_p2 = 2^{n+1}$.

    {\itshape Hint: first show that $\ord_p2 \mid 2^{n+1}$ to deduce that $\ord_p 2$ is a power of $2$ and must divide $2^n$ if $\ord_p 2 < 2^{n+1}$.}
  \item Use the previous part to show that $p = 2^{n+1}k + 1$ for some $k \in \bZ_+$.
  \end{enumerate}
\end{problem}

\end{document}
