        \problemdata       % Takes 5 *mandatory* arguments
        {modular-induction}             % latex-friendly label for the prob.
        {induction, modular}  % The topic(s) of the problem content.
        {}               % Source (if known)
        {F01 tut2-3, S99 tut2} % Usage (list ones you are aware of).
        {}        % Last revision info (author, date).

\begin{problem}
The next example of an ordinary induction proof makes use of modular
arithmethic.  Related notation is reviewed below.  In these definitions,
$a$ and $b$ are integers, and $m$ is a positive integer.

\begin{itemize}
\item $a$ \emph{divides} $b$, written $a \divides b$, means that $b$ is a
multiple of $a$; that is, $b = a k$ for some integer $k$.  For example, $7
\divides 21$, since $21 = 7 \cdot k$ where $k = 3$.

\item $a \equiv b \pmod{m}$, read as ``$a$ is congruent to $b$ modulo
$m$,'' means that $a$ and $b$ leave the same remainder when divided by
$m$.  For example, $15 \equiv 9 \pmod{6}$ because 15 and 9 both leave a
remainder of 3 when divided by 6.  Equivalently, $a \equiv b \pmod{m}$
means that $m \mid (a - b)$.

\item $a \bmod m$ (read ``$a$ mod $m$'') is the remainder when $a$ is
divided by $m$.  For example, $15 \bmod 6$ is equal to 3, because 15 divided
by 6 leaves a remainder of 3.  More precisely, $a \bmod m$ is the
unique number $r$ such that $a = mk + r$ where $k$ is an integer and
$0 \leq r < m$.
\end{itemize}

Note that $a \divides b$ and $a \equiv b \pmod{m}$ are propositions, but
that $a \bmod b$ is an integer quantity.  These two different notions
of ``$\bmod$'' are related in the following way:

\begin{equation*}
a \equiv b \pmod{m}  \iff (a \bmod m) = (b \bmod m)
\end{equation*}

Prove by induction:

\begin{theorem*}
If $n$ is an odd positive integer, then $n^2 \equiv 1 \pmod{8}$.
\end{theorem*}

\solution{This theorem is a little different in that we are not required to
prove a result for all positive $n$, but rather just for odd positive
$n$.

There are two ways to handle this complication.  One approach is to
reformulate the theorem as follows: if $k$ is a non-negative integer,
then $(2k+1)^2 \equiv 1 \pmod 8$.  This is equivalent to the original
theorem, since the expression $2k+1$ takes on all odd positive values
as $k$ takes on all non-negative values.  Now a proof by ordinary
induction on $k$ works.

A second approach is to use a variant of induction.  Suppose that we
prove proposition $P(1)$ and prove that $P(n)$ implies $P(n+2)$ for
all odd positive integers $n$.  Then we should believe that $P(1),
P(3), P(5), \ldots$ are all true for the same reason that we believe
ordinary induction works.  In effect, we introduce a new axiom just as
credible as the original induction axiom.  We will use this second
approach in the proof.

Introducing new induction-like axioms all the time might not seem like
a good idea.  But all of these little variants on induction can be
proven from the simple, original axiom.  So there is no great harm.
The key point is that there must be a chain of implications extending
from each predicate back to the base case (or cases).

\begin{proof}
The proof is by induction on $n$.  Let $P(n)$ be the proposition that
$n^2 \equiv 1 \pmod{8}$.  In the base case, $P(1)$ is true because
$1^2 \equiv 1 \pmod{8}$.

In the inductive step, for odd $n \geq 1$ assume that $n^2 \equiv 1
\pmod{8}$ to show that $(n+2)^2 \equiv 1 \pmod{8}$.  Since $n$ is an
odd integer, $4n + 4 = 4(n+1) = 8(\frac{n+1}{2}) \equiv 0 \pmod{8}$.
Adding this to the induction hypothesis implies that $n^2 + 4n + 4
\equiv 1 + 0 \pmod{8}$.  Simplifying this congruence gives $(n+2)^2
\equiv 1 \pmod{8}$.  Therefore, $P(n)$ implies $P(n+2)$, and the claim
is proved by induction.
\end{proof}

This proof contains a mystery.  Where did the magic term $4n + 4$ come
from?  Here is the reasoning that one might follow to discover the
inductive step in this proof.  We want to prove that $(n+2)^2 \equiv 1
\pmod{8}$, and we can assume that $n^2 \equiv 1 \pmod{8}$.  To go from
the assumption to the desired result, we need to add a little bit to
the left side, changing $n^2$ to $(n+2)^2$.  The value of this little
bit is $(n+2)^2 - n^2 = 4n + 4$.  We lucked out because, it is not
hard to see that this is always a multiple of 8 when $n$ is odd.
Arranging these observations into a straight line of reasoning gives
the proof.
}

\end{problem}
