\documentclass[11pt,twoside]{article}
\usepackage{latex-macros/course}

\newcommand{\rem}{\text{ rem }}

\begin{document}
\inclassproblems{9, Mon.}

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

\begin{problem}
This problem let's you practice proving simple facts about
divisibility.

\bparts

\ppart Prove: If $a \mid b$, then $a \mid b c$ for all $c$.

\solution[\vspace{1.5in}]{If $a \mid b$, then there exists a $k$ such
that $a k = b$.  Multiplying both sides by $c$ gives $a (k c) = b c$,
which implies that $a \mid b c$.}

\ppart Prove: If $a \mid b$ and $a \mid c$, then $a \mid s b + t c$
for all $s, t$.

\solution[\vspace{1.5in}]{
Suppose that $a \mid b$ and $a \mid c$.  Then there exist
integers $k_1$ and $k_2$ such that $a k_1 = b$ and $a k_2 = c$.  Thus,
$s b + t c = s (a k_1) + t (a k_2) = a (s k_1 + t k_2)$, which implies
that $a \mid s b + t c$.
}

\ppart A number is {\em perfect} if it is equal to the sum of its
positive divisors, other than itself.  For example, 6 is perfect,
because $6 = 1 + 2 + 3$.  Similarly, 28 is perfect, because $28 = 1 +
2 + 4 + 7 + 14$.  Explain why $2^{k-1} (2^k - 1)$ is perfect if $2^k -
1$ is prime.

\solution[\newpage]{If $2^k - 1$ is prime, then the only divisors of
$2^{k-1} (2^k - 1)$ are:

\[
1,\quad 2,\quad 4,\quad \ldots,\quad 2^{k-1}
\]

which sum to $2^k-1$ and

\[
1 \cdot (2^k - 1),\quad 2 \cdot (2^k - 1),\quad 4 \cdot (2^k - 1),\quad \ldots,\quad 2^{k-2} \cdot (2^k - 1)
\]

which sum to $(2^{k-1} - 1) \cdot (2^k - 1)$.  Adding these two sums
gives $2^{k-1} (2^k - 1)$, so the number is perfect.}

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

\solution[\vspace{1.5in}]{For some $s$ and $t$, $\gcd(a, b) = s a + t
b$.  Let $c$ be a common divisor of $a$ and $b$.  Since $c \mid a$ and
$c \mid b$, we know that $c$ divides $s a + t b = \gcd(a, b)$ by part
(b) of this problem.}

\eparts

\end{problem}

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

\begin{problem}
And this problem gives you practice with modular arithmetic.  If you
wish to shout ``Woohoo!'', go ahead--- we understand.

\bparts

\ppart Prove: If $a \equiv b \pmod{n}$, then $a c \equiv b c
\pmod{n}$.

\solution[\vspace{1.5in}]{The condition $a \equiv b \pmod{n}$ is
equivalent to the assertion $n \mid (a - b)$.  This implies that $n
\mid (a - b)c$ by part (a) of Problem 1, and so $n \mid (ac - bc)$.
This is equivalent to $ac \equiv bc \pmod{n}$.}

\ppart Prove: $(a \rem n) \equiv a \pmod{n}$

\solution[\vspace{1.5in}]{The remainder $a \rem n$ is equal to $a - qn$
for some integer $q$.  However, for every integer $q$:

\[
\begin{array}{ll}
            & n \mid qn \\
\Rightarrow & n \mid (a - qn) - a \\
\Rightarrow & n \mid (a \rem n) - a
\end{array}
\]

The last statement is equivalent to $(a \rem n) \equiv a \pmod{n}$.}

\ppart Sketch an induction proof that $10^k \equiv 1 \pmod{9}$ for all
$k \geq 0$.  Why is a number written in decimal evenly divisible by 9
if and only if the sum of its digits is a multiple of 9?

\solution{The claim holds for $k = 0$, since $10^0 \equiv 1 \pmod{9}$.
Suppose the claim holds for some $k \geq 0$; that is, $10^k \equiv 1
\pmod{9}$.  Multiplying both sides by 10 gives $10^{k+1} \equiv 10
\equiv 1 \pmod{9}$.  So the claim holds for $k+1$ as well.

A number in decimal has the form:

\[
d_k \cdot 10^k + d_{k-1} \cdot 10^{k-1} + \ldots + d_1 \cdot 10 + d_0
\]

From the observation above, we know:

\begin{eqnarray*}
d_k \cdot 10^k + d_{k-1} \cdot 10^{k-1} + \ldots + d_1 \cdot 10 + d_0
    & \equiv & d_k + d_{k-1} + \ldots + d_1 + d_0 \pmod{9} \\
\end{eqnarray*}

This shows something stronger: the remainder when the original number
is divided by 9 is equal to the remainder when the sum of the digits
is divided by 9.  In particular, if one is zero, then so is the other.}

\eparts

\end{problem}

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

\end{document}