\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{amsfonts}
\usepackage{amsmath, amsthm, amssymb, etoolbox}
\usepackage{paralist}
%\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}

\parskip=\medskipamount
\DeclareMathOperator{\GCD}{GCD}

\newbool{solutions}
\booltrue{solutions}
%\boolfalse{solutions}

\newcommand{\vs}[1]{\vspace{#1in}}

\newcommand{\solbox}[2]{\ifbool{solutions}{\vs{.1}\textbf{Solution}:  #1 \qed\vs{.1} }{#2}}
\newcommand{\solution}[1]{\solbox{#1}{\null}}




\begin{document}

\thispagestyle{empty}

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



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

\begin{enumerate}
\item Use the Euclidean Algorithm to compute the gcd of 12345 and
  67890.


 \item Use your work above to find an integer solution to the equation
  $12345 x + 67890 y = 45.$

\item
  \begin{enumerate}
  

  \item Let $n \ge 2$ be an integer, and let
    $E_n = \{ m \in \Z \mid \gcd(m,n) = 1\}.$ Show that $E_n$ is
    closed under multiplication, that is given $m, m' \in E_n$, show
    that $mm' \in E_n$.
  
  \item Suppose that $a,b,c,d \in \Z$.  Determine \textbf{necessary
      and sufficient conditions} on $a,b,c,d$ so that the linear
    Diophantine equation $ax+by+cz = d$ is solvable for $x,y,z\in \Z$.
    \textit{Hint:} There are a couple of cases to consider.

    \end{enumerate}

\item The following is an alternate (and more robust) definition for a
  greatest common divisor.  Let $a,b \in \Z$, not both zero.  We
  define a greatest common divisor of $a,b$ (not necessarily unique)
  to be any integer $d$ so that\newline
  \begin{center}
    (i)\ $d \mid a$, $d\mid b$, and (ii)\ if $c \mid a$ and
    $c \mid b$, then $c \mid d$.
  \end{center}
  
   Notice that the difference between the two definitions is
  that we have replaced $\le$ in the book's definition with $\mid$
  (divides).  Show that if $d$ and $d'$ are two greatest common
  divisors (as defined above), then $d' = \pm d$.  As a consequence,
  there is a unique positive greatest common divisor which we call
  $\GCD(a,b)$.

  
\item Let $a,b \in \Z$, not both zero, and $\gcd(a,b)$ as defined in
  the book.

  \begin{enumerate}
  \item Show that $\gcd(a,b) = \GCD(a,b)$, so for elements in $\Z$,
    the two definitions coincide.

   
  \item Show that if $c \in \Z$, then $c\mid a$ and $c\mid b$ if and
    only if $c \mid \gcd(a,b)$.

  
  \end{enumerate}

\item In calculus, you learn that the partial sums of the harmonic
  series\newline $\ds S_n := 1 + \frac12+\frac13+\cdots + \frac1n$
  grow without bound as $n \to \infty$.  The goal of this exercise is
  to show that $S_n \in \Z$ if and only if $n=1$.

  
  \begin{enumerate}
  \item As a lemma, show that if $a,b,c,d \in \Z$ with
    $\gcd(a,b) = \gcd(c,d) = 1$, then
    \[\frac{a}{b} + \frac{c}{d} \in \Z \mbox{ implies that } b = \pm
      d.\]

  \item Now show that $S_n \in \Z$ if and only if $n=1$.
    \textit{Hint:} Let $t$ be the largest integer with $2^t \le n$,
    and show that for $n \ge 2$, the product $2^{t-1}S_n$ can be
    written as $a/b + 1/2$ where $a,b \in \Z$ and $b$ is odd.  You
    probably want to look at some examples to see how this comes
    about, and what exactly you need to prove.

   
  \end{enumerate}

\end{enumerate}
\end{document}


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