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

%\hidesolutions
\showsolutions

\begin{document}

\recitation{4}{September 22, 2004}

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

%\insolutions{\stamp}

\begin{problem}
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$.  Prove that $2^{k-1} (2^k - 1)$ is perfect when $2^k - 1$ is
prime.

All \textit{even} perfect numbers are known to have this form.
Whether or not there exists an \textit{odd} perfect number has been an
open question for more than two thousand years.

\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.}

\end{problem}

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

\begin{problem} Many divisibility tests are rooted in modular arithmetic.

\bparts

\ppart Use induction to prove that $10^k \equiv 1 \pmod{9}$ for all $k
\geq 0$.

\solution[\vspace{4.5in}]{We use induction.  Let $P(k)$ be the
proposition that $10^k \equiv 1 \pmod{9}$.

\noindent \textit{Base case:} $P(0)$ is true because $10^0 = 1$, which
is congruent to 1.

\noindent \textit{Inductive step:} Assume that $P(k)$ is true, where
$k \geq 0$.  Then $P(k+1)$ is also true by the following reasonsing:
%
\begin{align*}
10^{k+1} & \equiv 10 \cdot 10^k \pmod{9} \\
         & \equiv 10 \cdot 1 \pmod{9} \\
         & \equiv 1 \pmod{9}
\end{align*}
%
The first step uses the induction hypothesis and the second is
simplification.

The claim follows by the induction principle.}

\ppart Prove that a number written in decimal is divisible by 9 if and
only if the sum of its digits is a multiple of 9.

\solution[\newpage]{
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:
%
\[
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} \\
\]
%
This shows that 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}  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{3in}]{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!  Stand up, if you like, and try
cancelling terms of $(p-1)!$ in pairs.

\solution[\newpage]{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}

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

\begin{problem} We've noted that many assertions about the real numbers
have analogues in the integers modulo a prime.  Here is an another
example.  Two nonparallel lines in the real plane intersect at a
point.  Algebraically, this means that the equations
%
\begin{align*}
y & = m_1 x + b_1 \\
y & = m_2 x + b_2
\end{align*}
%
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:

\begin{center}
\resizebox{!}{1in}{\includegraphics{integerlines}}
\end{center}

However, an analogous statement holds if we work over the integers
{\em modulo a prime $p$}.  Find a solution to the congruences
%
\begin{align*}
y & \equiv m_1 x + b_1 \pmod{p} \\
y & \equiv m_2 x + b_2 \pmod{p}
\end{align*}
%
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{Subtracting the second congruence from the first, we have:
%
\begin{align*}
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{align*}
%
Substituting this value of $x$ into the first congruence, we have
%
\[
y \equiv m_1 \cdot (m_1 - m_2)^{-1} \cdot (b_2 - b_1) + b_1 \pmod{p}
\]
}

\end{problem}

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

\end{document}

