\input{preamble}
\begin{document}

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

\begin{problem}
  What are the last four decimal digits of the number $11^{15999}$?
\end{problem}

\begin{problem}
  Show the following facts about Euler's $\phi$--function:
  \begin{enumerate}[a)]
  \item $\phi(n)$ is even for every $n \geq 3$,
  \item $\phi(n^k) = n^{k-1}\phi(n)$ for all $n,k \in \bN$,
  \item $\phi(n) \geq \sqrt{n}$ for all $n \in \bN \setminus \{2,6\}$,
  \item If $m \mid n$, then $\phi(m) \mid \phi(n)$.
  \end{enumerate}
\end{problem}

\begin{problem}
  Let $n = p_1 \cdots p_k$ be a product of distinct odd primes and let $x \in \bZ/n\bZ$. Show that
  \[x^{\phi(n)+1} = x.\]
\end{problem}

\begin{problem}
  Let $m \in \bN$. The goal of this problem is to find all integers which are congruent modulo $m$ to their own square. In other words, we want to find all solutions of the equation $x^2 - x = 0$ in $\bZ/m\bZ$.
  \begin{enumerate}[a)]
  \item Show that, if $m$ is prime, then the only solutions are $[0]$ and $[1]$.
  \item Show that, if $m$ is a prime power, then the only solutions are still $[0]$ and $[1]$.
  \item For general $m$, let $m = p_1^{i_1} \cdots p_k^{i_k}$ be the prime--power decomposition of $m$ with $p_1 < \cdots < p_k$ prime and $i_1,\dots,i_k \in \bN$. Show there are $2^k$ different solutions of the equation $x^2 - x = 0$ in $\bZ/m\bZ$, and that these are given by
    \[\sum_{j=1}^k \delta_j \left(\frac{m}{p_j^{i_j}}\right)^{p_j^{i_j} - p_j^{i_j - 1}} \mod m\]
    for every tuple $(\delta_1, \dots, \delta_k) \in \{0,1\}^k$.
  \end{enumerate}
  {\itshape Hint: For the last part, use Euler's theorem and the Chinese remainder theorem.}
\end{problem}

\end{document}
