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

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

\begin{document}
\inclassproblems{6, Fri.}

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

\vspace{-0.25in} % trying to leave more space for student work



\begin{problem}
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}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{problem} Two nonparallel lines in the real plane intersect at a point.
Algebraically, this means that the equations

\vspace{-0.3in}
\begin{eqnarray*}
y & = & m_1 x + b_1 \\
y & = & m_2 x + b_2
\end{eqnarray*}
\vspace{-0.3in}

\noindent have a unique solution $(x, y)$, provided $m_1 \neq m_2$.
This statement would be false if we restricted $x$ and $y$ to the
integers, since the two lines could cross at a noninteger point:

\centerline{\resizebox{!}{1in}{\includegraphics{figures/integerlines}}}

However, an analogous statement holds if we work over the integers
{\em modulo a prime $p$}.  Find a solution to the congruences

\vspace{-0.3in}
\begin{eqnarray*}
y & \equiv & m_1 x + b_1 \pmod{p} \\
y & \equiv & m_2 x + b_2 \pmod{p}
\end{eqnarray*}
\vspace{-0.3in}

\noindent of the form $x \equiv ? \pmod{p}$ and $y \equiv ? \pmod{p}$
where the ?'s denote expressions involving $m_1$, $m_2$, $b_1$, and
$b_2$.  You may find it helpful to solve the original equations over
the reals first.

\solution[\newpage]{Subtracting the second congruence from the first,
we have:

\begin{eqnarray*}
0 & \equiv & m_1 x+b_1 - (m_2 x + b_2)  \pmod{p} \\
(m_1 - m_2)x & \equiv & b_2 - b_1 \pmod{p} \\
x & \equiv & (m_1 - m_2)^{-1} \cdot (b_2 - b_1) \pmod{p}
\end{eqnarray*}

Substituting this value of $x$ into the first congruence, we have

\begin{eqnarray*}
y & \equiv & m_1 \cdot (m_1 - m_2)^{-1} \cdot (b_2 - b_1) + b_1 \pmod{p}
\end{eqnarray*}
}

\end{problem}

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

\begin{problem} Suppose that $p$ is a prime.

\bparts

\ppart An integer $k$ is {\em self-inverse} if $k \cdot k \equiv 1
\pmod{p}$.  Find all integers that are self-inverse mod $p$.

\solution[\vspace{2in}]{The congruence holds if and only if $p \mid
k^2 - 1$ which is equivalent to $p \mid (k + 1) (k - 1)$.  This holds
if and only if either $p \mid k + 1$ or $p \mid k - 1$.  Thus, $k
\equiv \pm 1 \pmod{p}$.}

\ppart {\em Wilson's Theorem} says that $(p-1)! \equiv -1 \pmod{p}$.
The English mathematician Edward Waring said that this statement would
probably be extremely difficult to prove because no one had even
devised an adequate notation for dealing with primes.  (Gauss proved
it while standing.)  Your turn!  Try cancelling terms of $(p-1)!$ in
pairs.  See if you can do it while standing on one leg.

\solution{If $p = 2$, then the theorem holds, because $1! \equiv -1
\pmod{2}$.  If $p > 2$, then $p - 1$ and $1$ are distinct terms in the
product $1 \cdot 2 \cdot \cdots (p - 1)$, and these are the only
self-inverses.  Consequently, we can pair each of the remaining terms
with its multiplicative inverse.  Since the product of a number and
its inverse is congruent to 1, all of these remaining terms cancel.
Therefore, we have:

\begin{eqnarray*}
(p-1)!
        & \equiv & 1 \cdot (p - 1) \pmod{p} \\
        & \equiv & -1 \pmod{p}
\end{eqnarray*}
}

\eparts

\end{problem}

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

\end{document}
