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

\centerline{\textbf{Possible recitation problems}}

\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{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{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*}
}

\ppart Prove the converse of Wilson's Theorem: if $(p-1)! \equiv -1
\pmod{p}$, then $p$ is a prime.

\eparts

\end{problem}

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

\begin{problem}
Let $p$ be a prime.  Then $r$ is a \textit{square root} of $n$ modulo
$p$ if:
\[
r^2 \equiv n \pmod{p}
\]

\bparts

\ppart Find all square roots $r$ of 3 modulo 7 such that $0 \leq r <
7$.

\ppart Find all square roots $r$ of 4 modulo 7 such that $0 \leq r <
7$.

\ppart Show that if $n$ is not a multiple of $p$, then there exist
either 0 or 2 square roots $r$ of $n$ modulo $p$ such that $0 \leq r <
p$.

\eparts

\end{problem}


We'll walk you through the proof.

\bparts

\ppart Show that $m = s \cdot a + t \cdot b$ for some integers $a$ and
$b$.

\solution{Since $m$ is a multiple of $\gcd(a, b)$, there exists an
integer $k$ such that $m = k \gcd(a, b)$.  We know that $\gcd(a, b) =
s' \cdot a + t' \cdot b$ for some $s'$ and $t'$.  This means:
%
\[
m = (k s') \cdot a + (k t') \cdot b
\]
%
Let $s = k s'$ and $t = k t'$.
}

\ppart Explain why $s$ and $t$ can not both be negative, and explain
how to solve the problem if $s$ and $t$ are both positive.

\solution{ The coefficients $s$ and $t$ can not both be negative
because that would violate the constraint that $0 \leq m$.  If $s$ and
$t$ are both positive, then $s = t = 1$; otherwise, the constraint
that $m \leq a + b$ would be violated.  Thus, we simply fill both
buckets.}

\ppart The remaining posibility is that one coefficient is nonnegative
and the other is nonpositive.  In particular, suppose $s \geq 0$ and
$t \leq 0$.  (A symmetric argument applies when the roles of $s$ and
$t$ are reversed.)  If we define $x = s$ and $y = - t$, then both $x$
and $y$ are nonnegative and:
%
\[
m = x \cdot a - y \cdot b
\]
%
Now the overall plan is to increase the total amount of water in both
buckets by $a$ gallons $x$ times and to decrease the total amount of
water in both buckets by $b$ gallons $y$ times.  This will leave us
with exactly $m$ gallons.  The trick is to intertwine these increases
and decreases so that we never overflow the buckets or run a deficit.

Explain how to increase the total amount of water in both buckets by
$a$ if the total is currently no more than $b$.

\solution{Pour all the water into the $b$-gallon bucket and fill the
$a$-gallon bucket.}

\ppart Explain how to decrease the total amount of water in both
buckets by $b$ if the total is currently at least $b$.

\solution{Pour water until the $b$-gallon bucket until it is full.
Then empty it out.}

\ppart We'll need two variables to keep track of where we are in the
procedure.  Let $x'$ be the total number of times we've added $a$
gallons, and let $y'$ be the total number of times we've gotten rid of
$b$ gallons.  Initially, both buckets are empty and $x' = y' = 0$.

The procedure involves a sequence of steps.  Each step can be carried
out in either of two ways, subject to some conditions.

\begin{enumerate}

\item If the total water in both buckets is not more than $b$ and $x <
x'$, then add $a$ gallons.

\item If the total water in both buckets is more than $b$ and $y <
y'$, then get rid of $b$ gallons.

\end{enumerate}

Prove that either we are done ($x' = x$ and $y' = y$) or else one of
these rules applies.

\ppart Prove that after $



\eparts