\input{preamble}
\begin{document}

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

\begin{problem}
  Use the Chinese Remainder Theorem and Hensel's Lemma to find all solutions of the following polynomial equations.
  \begin{enumerate}[a)]
  \item $x^2 + x + 34 = 0$ in $\bZ/{81}\bZ$
  \item $x^2 + x + 47 = 0$ in $\bZ/{2401}\bZ$
  \item $x^6 - 2x^5 - 35 = 0$ in $\bZ/{6125}\bZ$
  \end{enumerate}
\end{problem}

\begin{problem}
  Find all solutions $x \in \bZ$ of the following systems of congruences
  \begin{enumerate}[a)]
  \item\
    \vspace{-\baselineskip}
    \begin{align*}
      x \equiv 4 \quad (\mod\ 11) \\
      x \equiv 3 \quad (\mod\ 17) \\
    \end{align*}
    \vspace{-1cm}
  \item\
    \vspace{-\baselineskip}
    \begin{align*}
      2x \equiv 3 \quad (\mod\ 5) \\
      5x \equiv 2 \quad (\mod\ 6) \\
      3x \equiv 4 \quad (\mod\ 7) \\
      x \equiv 5 \quad (\mod\ 8) \\
    \end{align*}
    \vspace{-1.5cm}
  \end{enumerate}
\end{problem}

\begin{problem}
  Show that for any $n \in \bZ_+$ there are $n$ consecutive integers
  \[a, a+1, \dots, a+(n-1)\]
  such that each of them is divisible by a perfect square (an integer of the form $x^2$, where $x$ is an integer greater than 1).

  {\itshape Hint: Find an integer $a$ such that $a+(i-1)$ is divisible by $p_i^2$ where $p_i$ is the $i$-th prime number, for all $i \in \{1,\dots,n\}$. That is, $a$ is divisible by $4$, $a+1$ is divisible by $9$, $a+2$ is divisible by $25$, etc.}
\end{problem}

\begin{problem}
  Let $a, b \in \bZ$ be coprime. Show that for every $c \in \bZ$ there exists $n \in \bZ$ such that
  \[(an+b,c) = 1.\]

  {\itshape Hint: use the Chinese Remainder Theorem to find $n$ such that $(an+b) \mod p = 1 \mod p$ for every prime factor $p$ of $c$ that does not divide $a$.}
\end{problem}

\begin{problem}
  The goal of this problem is to prove a generalization of the Chinese Remainder Theorem for integers which are not pairwise coprime.

  \begin{enumerate}[a)]
  \item Let $m_1, m_2$ be any integers greater than $1$, and set $M = \lcm(m_1,m_2)$ and $m = \gcd(m_1,m_2)$. Show that the map
    \begin{align*}
      f \colon\quad \bZ/M\bZ &\to \bZ/m_1\bZ \times \bZ/m_2\bZ \\
      a \bmod M &\mapsto (a \bmod m_1, a \bmod m_2)
    \end{align*}
    is well--defined and injective. Show that its image is
    \[f(\bZ/M\bZ) = \{(x_1,x_2) \mid x_1 \bmod m = x_2 \bmod m\}.\]
  \item \emph{(optional)} Let $m_1,\dots,m_n$ be integers greater than $1$ and let $M$ be the least common multiple of all of them. Show that the map
    \begin{align*}
      \bZ/M\bZ &\to \bZ/m_1\bZ \times \cdots \times \bZ/m_n\bZ \\
      a \mod M &\mapsto (a \mod m_1, \dots, a \bmod m_n)
    \end{align*}
    is well--defined and injective, and that its image is
    \[\{(x_1,\dots,x_n) \mid x_i \bmod m_{ij} = x_j \bmod m_{ij}\ \text{for all $1 \leq i,j \leq n$}\},\]
    where $m_{ij} = \gcd(m_i,m_j)$.

    {\itshape Hint: use part a) and induction.}
\end{enumerate}
\end{problem}

\end{document}
