\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{amsfonts}
\usepackage{amsmath, amsthm, amssymb}
\usepackage{enumitem}
%\pagestyle{headings}

\usepackage{mathtools}

\newcommand{\0}{\mathbf 0}
\newcommand{\C}{{\mathbb C}}
\newcommand{\R}{{\mathbb R}}
\newcommand{\Q}{{\mathbb Q}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\diag}{\textrm{diag}}
\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}
\newcommand{\normal}{\trianglelefteq}
\newcommand{\bmid}{\,\Big|\,}
\newcommand{\ds}{\displaystyle}

\DeclareMathOperator{\GCD}{GCD}

\begin{document}

\thispagestyle{empty}

\begin{flushright}
  Your Name Goes Here
\end{flushright}


\begin{center}
  \textbf{Math 25}\\ Homework 3
\end{center}

\begin{enumerate}
\item
  \begin{enumerate}
  \item Find the general solution to the congruence
    $35x \equiv 15\pmod{120}$.
  \item What does your work in the first part tell you about the
    solutions to \newline $35x \equiv 15\pmod{60}$?
  \end{enumerate}
 

\item Find the general solution to the congruence
  $35 x \equiv 15 \pmod {121}$. Show all work including the steps to
  find a particular solution.

\item Find the least non-negative residue of $17^{208}\pmod{93}$.

\item Find all solutions to the system of congruences:
  \[ x \equiv 3 \pmod {17},\qquad x \equiv 10 \pmod{16},\qquad x \equiv
    0 \pmod {15}.
  \]

\item A rafter of 17 turkeys have 12 nests, eleven of which contain
  the same number $m > 1$ of eggs, and the twelfth with 6 eggs.
  Dividing all the eggs into 17 piles produces piles each with the
  same number of eggs.  What is the minimum number of eggs possible?





\item In this problem we show that the set of lattice points in the
  plane which are visible from the origin contain arbitrarily large
  square gaps.  That is, we show that given any integer $k > 0$, there
  exists a lattice point $(a,b)$ so that none of the lattice points
  \[(a + r, b+s), 0 < r\le k, 0 < s \le k,
  \]
  are visible from the origin.

  \textbf{Suggested approach:} Let $p_1, p_2, \dots$ be the sequence
  of primes.  Given $k > 0$, consider the $k\times k$ matrix whose
  first row is the first $k$ primes, the second row is the next $k$
  primes, and so on.  Let $m_i$ be the product of the primes in the
  $i$th row, and $M_j$ the product of the primes in the $j$th column.

  \begin{enumerate}
  \item Show that there are unique solutions modulo
    $M = m_1 m_2 \cdots m_k = M_1 M_2 \cdots M_k$ to the two systems
    of congruences:
    \begin{alignat*}{2}
      x&\equiv -1\mod{m_1} &\qquad y &\equiv -1\pmod{M_1}\\
      x&\equiv -2\mod{m_2} &\qquad y &\equiv -2\pmod{M_2}\\
      &\vdots&&\vdots\\
      x&\equiv -k\mod{m_k} &\qquad y &\equiv -k\pmod{M_k}\\
    \end{alignat*}
    Let $a$ be the unique solution modulo $M$ of the system with the
    $m_i$s and $b$ the solution to the system with the $M_j$s.
  \item Show that no lattice point of the form $(a+r, b+s)$ with
    $0 < r \le k$ and $0 < s \le k$ is visible from the origin.
  \end{enumerate}
\end{enumerate}


\end{document}


%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End:
