\documentclass[twoside,12pt]{article}
\usepackage{light}

\showsolutions
%\hidesolutions

\begin{document}

\problemset{3}{September 21, 2004}{Monday, September 27 at 9pm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\stamp

\begin{problem}[25 points]
Prove the following assertions:

\bparts

\ppart For all $c \neq 0$, $a \mid b$ if and only if $c a \mid
c b$.

\solution{The assertion $a \mid b$ holds if and only if there exists
an integer $k$ such that $ak = b$.  For $c \neq 0$, this is true if
and only if there exists and integer $k$ such that $cak = cb$.  And
this is holds if and only if $c a \mid c b$.}

\ppart Every common divisor of $a$ and $b$ divides $\gcd(a,
b)$.

\solution{In lecture, we showed that $\gcd(a,b) = sa + tb$ for some
integers $s$ and $t$.  Let $m$ be any other common divisor of $a$ and
$b$.  Then $mx=a$ and $my=b$ for some integers $x$ and $y$.  Thus
$\gcd(a,b) = s(mx) + t(my) = m(sx+ty)$, proving that $m \mid
\gcd(a,b)$.}

\ppart $\gcd(ka, kb) = k \cdot \gcd(a, b)$ for all integers $k > 0$.

\solution{In lecture, we showed that $\gcd(a, b)$ is the minimum
positive value of $s \cdot a + t \cdot b$ over all $s, t \in
\mathbb{Z}$.  Thus, $k \cdot \gcd(a, b)$ is the minimum positive value
of $k (s \cdot a + t \cdot b) = s \cdot ka + t \cdot kb$, which is
equal to $\gcd(ka, kb)$.  }

\ppart $\gcd(a \rem b, b) = \gcd(a, b)$ (Hint: Prove the more general
fact that $\gcd(a - q \cdot b, b) = \gcd(a, b)$ for all integers $q$.)

\solution{Recall that $a \rem b = a - q b$ for some integer $q$.
We'll show more generally that $\gcd(a - q b, b) = \gcd(a, b)$ for all
integers $q$.  On one hand, $\gcd(a, b)$ is the smallest positive
value of:
%
\[
s \cdot a + t \cdot b
\]
%
On the other hand, $\gcd(a - q b, b)$ is the smallest positive value
of:
%
\[
x \cdot (a - q b) + y \cdot b = x \cdot a + (y - q x) \cdot b
\]
%
These two expressions take on exactly the same set of values, since we
can let $s = x$ and $t = y - q x$.  Thus, in particular, the
expressions have the same smallest positive value, and so $\gcd(a - q
b, b) = \gcd(a, b)$ as claimed.}

\ppart $nx \rem dx = (n \rem d) \cdot x$ when $x \in \mathbb{N}^+$.

\solution{By the definition of $\rem$ and the Division Algorithm, $n
\rem d$ is the unique integer $r$ satisfying $n = q d + r$ and $0 \leq
r < d$.  Now if we set $q' = q$ and $r' = rx$, then $nx = q' (dx) +
r'$ and $0 \leq r' < dx$.  Thus, $r' = rx = (n \rem d) \cdot x$ is $nx
\rem dx$.}

\eparts

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}[20 points]
Use induction to prove the following statements, which were left
unproved in lecture.

\bparts

\ppart $(a_1 \rem n) \cdot (a_2 \rem n) \cdots (a_k \rem n) \equiv a_1
\cdot a_2 \cdots a_k \pmod{n}$

You may use the following two facts, which were proved in lecture:

\begin{enumerate}

\item If $a_1 \equiv b_1 \pmod{n}$ and $a_2 \equiv b_2 \pmod{n}$, then
$a_1 a_2 \equiv b_1 b_2 \pmod{n}$.

\item $(a \rem n) \equiv a \pmod{n}$

\end{enumerate}

\solution{We proceed by induction on $k$ with the claim itself as the
induction hypothesis.

\noindent \textit{Base case:} The claim holds for $k = 1$ by the second
fact provided above.

\noindent \textit{Inductive step:} Now we assume that the claim holds
for some $k \geq 1$ and prove that the claim holds for $k + 1$.
Consider the expression:
%
\[
(a_1 \rem n) \cdot (a_2 \rem n) \cdots (a_k \rem n) \cdot (a_{k+1} \rem n)
\]
%
By the induction assumption, the first $n$ terms are congruent to $a_1
\cdot a_2 \cdots a_k$ modulo $n$.  By the second fact from above,
$(a_{k+1} \rem n)$ is congruent to $a_{k+1}$ modulo n.  Thus, by the
first fact above, the whole product is congruent to
%
\[
a_1 \cdot a_2 \cdots a_k \cdot a_{k+1}
\]
%
modulo $n$.  Thus, the claim holds for $k + 1$.

By the principle of induction, the claim holds for all $k \geq 1$.
}

\ppart Let $p$ be a prime.  If $p \mid a_1 \cdot a_2 \cdots a_n$, then
$p$ divides some $a_i$.

You may use the fact, proved in lecture, that if $p$ is a prime and $p
\mid ab$, then $p \mid a$ or $p \mid b$.

\solution{We proceed by induction on $n$ with the claim itself as the
induction hypothesis.

\noindent \textit{Base case:} When $n = 1$, the claim asserts that if
$p \mid a_1$, then $p \mid a_1$, which is trivially true.

\noindent \textit{Inductive step:} Now we assume that the claim holds
for some $n \geq 1$ and prove that it holds for $n + 1$.  Suppose that
%
\[
p \mid a_1 \cdot a_2 \cdots a_n \cdot a_{n+1}
\]
%
By grouping the first $n$ terms on the right and using the fact cited
above from lecture, we know that either $p \mid (a_1 \cdot a_2 \cdots
a_n)$ or $p \mid a_{n+1}$.  If the former case, the induction
assumption implies that $p$ divides some some $a_i$ with $1 \leq i
\leq n$.  Thus, in both cases, $p$ divides some $a_i$ as claimed.

By induction, the claim holds for all $n \geq 1$.}

\eparts

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}[15 points]
Prove that the greatest common divisor of three integers $a$, $b$, and
$c$ is equal to their smallest positive linear combination; that is,
the smallest positive value of $sa + tb + uc$, where $s$, $t$, and
$u$ are integers.
\end{problem}

\solution{This is nearly a verbatim repetition of the proof for two
integers, which appears in the notes.

Let $m$ be the smallest positive linear combination of $a$, $b$, and
$c$.  We'll prove that $m = \gcd(a, b, c)$ by showing both $\gcd(a, b,
c) \leq m$ and $m \leq \gcd(a, b, c)$.

First, we show that $\gcd(a, b, c) \leq m$.  By the definition of
common divisor, $\gcd(a, b, c)$ divides $a$, $b$, and $c$.  Therefore,
for every triple of integers $s$, $t$, and $u$:
%
\[
\gcd(a, b) \mid s a + t b + u c
\]
%
Thus, in particular, $\gcd(a, b, c)$ divides $m$, and so $\gcd(a, b,
c) \leq m$.

Now we show that $m \leq \gcd(a, b, c)$.  We do this by showing that
$m \mid a$.  Symmetric arguments shows that $m \mid b$ and $m \mid c$,
which means that $m$ is a common divisor of $a$, $b$, and $c$.  Thus,
$m$ must be less than or equal to the \textit{greatest} common divisor
of $a$, $b$, and $c$.

All that remains is to show that $m \mid a$.  By the division
algorithm, there exists a quotient $q$ and remainder $r$ such that:
%
\[
a = q \cdot m + r \hspace{1in} \text{(where $0 \leq r < m$)}
\]
%
Now $m = s a + t b + u c$ for some integers $s$ and $t$.  Subtituting
in for $m$ and rearranging terms gives:
%
\begin{align*}
a & = q \cdot (s a + t b + u c) + r \\
r & = (1 - qs) a + (-qt) b + (-qu) c
\end{align*}
%
We've just expressed $r$ as a linear combination of $a$, $b$, and $c$.
However, $m$ is the \textit{smallest positive} linear combination and $0
\leq r < m$.  The only possibility is that the remainder $r$ is not
positive; that is, $r = 0$.  This implies $m \mid a$.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}[10 points]
Let $S_k = 1^k + 2^k + \ldots + (p-1)^k$, where $p$ is an odd prime
and $k$ is a positive multiple of $p - 1$.  Use Fermat's theorem to
prove that $S_k \equiv -1 \pmod{p}$.
\end{problem}

\solution{Fermat's theorem says that $x^{p-1} \equiv 1 \pmod{p}$
when $1 \leq x \leq p - 1$.  Since $k$ is a multiple of $p-1$,
raising each side to a suitable power proves that $x^k \equiv 1
\pmod{p}$.  Thus:
%
\begin{align*}
1^k + 2^k + \ldots + (p-1)^k
    & \equiv \underbrace{1 + 1 + \ldots + 1}_{\text{$p-1$ terms}} \pmod{p} \\
    & \equiv p - 1 \pmod{p} \\
    & \equiv - 1 \pmod{p}
\end{align*}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{problem}[10 points]
Let $N$ be a number whose decimal expansion consists of $3^n$
identical digits.  Show by induction that $3^n \mid N$.  For example:
%
\[
3^2 \mid \underbrace{777777777}_{\text{$3^2 = 9$ digits}}
\]
\end{problem}

\solution{We proceed by induction on $n$.  Let $P(n)$ be the
proposition that $3^n \mid N$, where the decimal expansion of $N$
consists of $3^n$ identical digits.

\noindent \textit{Base case.}  $P(0)$ is true because $3^0 = 1$ divides
every number.

\noindent \textit{Inductive step.}  Now assume $P(n)$ for $n \geq 0$
in order to prove $P(n+1)$.  Consider a number whose decimal expansion
consists of $3^{n+1}$ copies of the digit $a$:
%
\begin{align*}
\underbrace{aaaaaa \ldots aaaaaa}_{\text{$3^{n+1}$ digits}}
    & = \underbrace{aaa \ldots aaa}_{\text{$3^n$ digits}}
        \underbrace{aaa \ldots aaa}_{\text{$3^n$ digits}}
        \underbrace{aaa \ldots aaa}_{\text{$3^n$ digits}} \\
    & = \underbrace{aaa \ldots aaa}_{\text{$3^n$ digits}}
        \quad \cdot \quad
        1
        \underbrace{000 \ldots 001}_{\text{$3^n$ digits}}
        \underbrace{000 \ldots 001}_{\text{$3^n$ digits}} \\
\end{align*}
%
Now $3^n$ divides the first term by the assumption $P(n)$, and 3
divides the second term since the digits sum to 3.  Therefore, the
whole expression is divisible by $3^{n+1}$.  This proves $P(n+1)$.

By the principle of induction $P(n)$ is true for all $n \geq 0$.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}[20 points]
Suppose that you have an $a$-gallon bucket and a $b$-gallon bucket
where $a \leq b$.  You also have access to a fountain.  In lecture, we
proved that you can measure out \textit{only} multiples of $\gcd(a,
b)$ gallons.  The goal of this problem is to prove the converse: you
\textit{can} measure out exactly $n$ gallons in one bucket provided
$n$ is a multiple of $\gcd(a, b)$ and $0 \leq n \leq b$.

Getting exactly $b$ gallons is easy: fill the $b$-gallon bucket.  For
all other quantities, consider the following procedure:

\begin{enumerate}

\item Fill the $a$-gallon bucket.

\item Pour the entire contents of the $a$-gallon bucket into the
$b$-gallon bucket, dumping out the $b$-gallon bucket whenever it
becomes full.

\end{enumerate}

\bparts

\ppart Give a concise expression for the amount of water in the
$b$-gallon bucket after $k$ repetitions of this procedure.

\solution{$ka \rem b$}

\ppart Suppose that $a$ and $b$ are relatively prime.  Show that this
expression never takes on the same value twice as $k$ ranges over the
set $\set{0, 1, 2, \ldots, b - 1}$.

\solution{Assume for the purpose of contradiction that $k_1 a \rem b =
k_2 a \rem b$ for some $k_1 \neq k_2$ in the range $0 \leq k_1, k_2 <
b$.  This means $k_1 a \equiv k_2 a \pmod{b}$, which implies that $k_1
\equiv k_2 \pmod{b}$ since $a$ and $b$ are relatively prime.  Since no
two values in $\set{0, 1, 2, \ldots, b-1}$ are congruent modulo $b$,
we must have $k_1 = k_2$, which is a contradiction.}

\ppart Show that the expression in part (a) takes on \textit{all}
values in $\set{0, 1, 2, \ldots, b - 1}$ as $k$ ranges over the set
$\set{0, 1, 2, \ldots, b - 1}$.  In other words, every number of
gallons between 0 and $b - 1$ is obtained within $b - 1$ repetitions
of the procedure.

\solution{The expression takes on $b$ values in the range $\set{0, 1,
2, \ldots, b - 1}$ by the definition of remainder, and these values
are all distinct by the preceding problem part.  Thus, it must take on
\textit{every} value in the range exactly once.}

\ppart Now suppose $a$ and $b$ are not relatively prime.  Prove that
the values this expression takes on are exactly the nonnegative
multiples of $\gcd(a, b)$ less than $b$.

You may find it helpful to isolate the common and relatively prime
parts of $a$ and $b$.  Specifically, define $a'$ and $b'$ so that $a =
a' \gcd(a, b)$ and $b = b' \gcd(a, b)$.  Note that $a'$ and $b'$ are
relatively prime; otherwise, $a$ and $b$ would have a greater common
divisor.

\solution{Consider the sequence:
%
\[
0 a \rem b, \qquad 1 a \rem b, \qquad 2 a \rem b, \qquad \ldots,
\qquad (b'-1) a \rem b
\]
%
We can rewrite each term as follows:
%
\begin{align*}
k a \rem b
    & = k [a' \gcd(a, b)] \rem [b' \gcd(a, b)] \\
    & = \gcd(a, b) \cdot (k a' \rem b')
\end{align*}
%
The first step is substitution and the second uses part (e) of problem
1.  Thus, each term in the sequence above is $\gcd(a, b)$ times the
corresponding term in the sequence below:
%
\[
0 a' \rem b', \qquad
1 a' \rem b', \qquad
2 a' \rem b', \qquad
\ldots, \qquad
(b'-1) a' \rem b'
\]
%
By the preceding problem part, this is a permutation of 0, 1, 2,
\ldots $b' - 1$.  Thus, the original sequence is a permutation of:
%
\[
0 \cdot \gcd(a, b), \qquad
1 \cdot \gcd(a, b), \qquad
2 \cdot \gcd(a, b), \qquad
\ldots, \qquad
(b' - 1) \cdot \gcd(a, b)
\]
%
And these are the nonnegative multiple of $\gcd(a, b)$ less than $b$.
}

\eparts

\end{problem}

\end{document}
