How to use well-ordering to form a "least counterexample derived contradiction" to prove rule for obtaining the remainder when dividing $3^n$ by 13?

Question

By the division with remainder theorem, we know that there exists $q \in \mathbb{Z}$ and $r \in \mathbb{Z}$, where $0 \leq r < 13$, such that: \begin{equation*} 3^n = 13q + r \end{equation*}

Simple rule for obtaining remainder when dividing $3^n$ by $13$: it can be shown then, that $r = 3^p$, where $p = \min R$, where $R = \{m \in \mathbb{Z}_{\geq 0}\ | n \equiv m(3)\}$. A remark to explain the modulo notation I am using:

\begin{equation*} a \equiv b (c) = \exists q \in \mathbb{Z} \text{ s.t. } a - b = qc \end{equation*}

I know I can use induction to prove the simple rule, but I'd like to draw upon another fact: subsets of the integers with a lower bound are well ordered. This well-ordering is equivalent to induction.

I am trying to practice proofs using this equivalence between well-ordering and induction, but am still having some trouble. Here is what I have so far:

1) We know that $R$ has a minimal element since it is bounded below since $R \subset \mathbb{Z}_{\geq 0}$. Let $p = \min R$.

2) Pick an assumption involving $p$ along with 1), which results in the conclusion that $p \neq \min R$, resulting in a contradiction. What should this assumption be? $r \neq 3^p$?

We know that $r \neq 3^p$ is equivalent to saying $r < 3^p \;\vee\; r > 3^p$. Consider the first case:

\begin{align*} r > 3^p \implies 3^n < 13q + 3^p... \end{align*}

This seems like a pretty big dead-end. What might I try instead, and more importantly, what is the moral of the story in terms of picking least counter-examples in the future?

Answer 1

HINT: The statement $P(n)$ (for $n\in\Bbb Z_{\ge 0}$) that you’re trying to prove is:

$P(n)$: If $r=\min\{m\in\Bbb Z_{\ge 0}:m\equiv n\pmod3\}$, then there is a $q\in\Bbb Z$ such that $3^n=13q+r$.

The set to which you want to apply the well ordering principle is therefore

$$B=\{n\in\Bbb Z_{\ge 0}:P(n)\text{ is false}\}\;,$$

the set of ‘bad’ $n$, not $\{m\in\Bbb Z_{\ge 0}:m\equiv n\pmod3\}$ for some particular $n\in\Bbb Z_{\ge 0}$.

The idea is to assume that $B\ne\varnothing$ and derive a contradiction, thereby showing that $B=\varnothing$ and hence that $P(n)$ holds for each $n\in\Bbb Z_{\ge 0}$.

If $B\ne\varnothing$, then there is a smallest $n\in B$. Now argue almost exactly as you would for the proof by induction.

• $n$ can’t be $0$; why?

Therefore $n-1\ge 0$, so $n-1\notin B$, and therefore $P(n-1)$ holds.

• Show that $P(n)$ holds, so that $n\notin B$, thereby getting the desired contradiction.