\input{preamble}
\begin{document}

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

\begin{problem}
  How many integer solutions $x,y \in \bZ$ do the following equations have? If there is at least one solution, find an example.
  \begin{enumerate}[a)]
  \item $60x + 18y = 97$
  \item $37x + 1000010000100001y = 0$
  \item $14541 x + 1367631 y = 13566531$
  \end{enumerate}
\end{problem}

\begin{problem}
  Let $a, b$ be positive integers such that $a^2 \mid b^2$. Show that $a \mid b$.
\end{problem}

\begin{problem}
  Denote by $p_n$ be the $n$--th prime ($p_1 =2, p_2 = 3, p_3 = 5, \dots$). Show that $p_n \leq 2^{2^{n-1}}$ for every $n \in \bN$. Conclude that there are at least $n+1$ primes less than $2^{2^n}$ for every $n \in \bN$.

  {\itshape Hint: Look at Euclid's proof of the infinitude of primes.}
\end{problem}

\begin{problem}
  Let $p \neq q$ be prime numbers and $a$ be an integer such that $p \mid a$ and $q \mid a$. Show that $pq \mid a$. Find a counterexample if either $p$ or $q$ is not prime.
\end{problem}

\begin{problem}
  Let $a,b,c \in \bZ$ and write $d = (a,b)$. We proved in class that the equation $ax + by = c$ has an integer solution if and only if $d \mid c$.

  Now assume that $d \mid c$, and let $s, t$ be a pair of Bezout coefficients for $a$ and $b$, so that $as + bt = d$. Show that the set of all solutions $(x,y)$ of $ax + by = c$ is
  \[\left\{\left(\frac{cs - nb}{d}, \frac{ct + na}{d}\right) \mid n \in \bZ\right\}.\]
\end{problem}

\end{document}
