In my previous post I mentioned that I did not know a simple proof that the period of $$3 \pmod{2^m}$$ was exactly $$2^{m-2}$$ (For $$m \ge 3$$). This morning, Pascal Michel explained a proof to me. Let me expand on it here:

## Background

First let’s remember that the period (also called the order) of an element $$a \pmod{b}$$ is the smallest positive value $$d$$ such that $$a^d \equiv 1 \pmod{b}$$.

Lemma 1: If $$a^n \equiv 1 \pmod{b}$$ then $$n$$ is divisible by the period $$d$$ of $$a \pmod{b}$$

Proof: Let $$n = t d + r$$ (where $$0 \le r < d$$), then $$1 \equiv a^n = (a^d)^t \cdot a^r \equiv 1^t \cdot a^r = a^r \pmod{b}$$. So $$a^r \equiv 1 \pmod{b}$$ and $$r < d$$. But $$d$$ is (by definition) the smallest postive value such that $$a^d \equiv 1 \pmod{b}$$, so the only option is that $$r = 0$$ (is not positive). And thus $$n = t d$$ is divisible by the period $$d$$. QED

Note: This also makes intuitive sense given that we are calling this a period, it should only reach 1 at multiples of that period. Otherwise there would be something aperiodic happening.

Lemma 2: If $$a^{p^k} \equiv 1 \pmod{p^m}$$ and $$a^{p^{k-1}} \not \equiv 1 \pmod{p^m}$$ then the period of $$a \pmod{p^m}$$ is exactly $$p^k$$

Proof: Let $$d$$ be the period of $$a \pmod{p^m}$$. Then $$d$$ divides $$p^k$$ by Lemma 1. But $$d$$ does not divide $$p^{k-1}$$ (if it did, then $$a^{p^{k-1}} \equiv 1 \pmod{p^m}$$). But the only $$d$$ that divides $$p^k$$, but not $$p^{k-1}$$ is $$d = p^k$$. QED

## Period of 3

OK, applying this to our case of $$3 \pmod{2^m}$$: we know from Euler’s totient theorem that:

$3^{\phi(2^m)} = 3^{2^{m-1}} \equiv 1 \pmod{2^m}$

Therefore the period $$d$$ of $$3 \pmod{2^m}$$ must divide $$2^{m-1}$$. Thus $$d = 2^k$$ for $$k < m$$. And by Lemma 2, we can see that to prove it we must simply find a $$k$$ such that $$3^{2^k} \equiv 1 \pmod{2^m}$$ and $$3^{2^{k-1}} \not \equiv 1 \pmod{2^m}$$.

We will need a key fact here … and sadly, it is a bit unmotivated … sorry, I don’t know what to say. This is the fact that Pascal emailed to me. And once you prove it everything falls into place:

Lemma 3: For all $$n \ge 1$$, $$3^{2^n} \equiv 2^{n+2} + 1 \pmod{2^{n+3}}$$

Proof: We prove this via induction on $$n$$:

• Base Case ($$n = 1$$): $$3^{2^1} = 9 = 2^3 + 1$$. QED
• Inductive Step: Assuming $$3^{2^n} \equiv 2^{n+2} + 1 \pmod{2^{n+3}}$$: Thus there exists some $$t$$ such that $$3^{2^n} = 2^{n+2} + 1 + t \cdot 2^{n+3} = (1 + 2t) 2^{n+2} + 1$$, so:
$3^{2^{n+1}} = (3^{2^n})^2 = ((1 + 2t) 2^{n+2} + 1)^2 = (1 + 2t)^2 (2^{n+2})^2 + 2 (1 + 2t) 2^{n+2} + 1 \equiv 2^{n+3} + 1 \pmod{2^{n+4}}$

QED

Corollary 4: For all $$m \ge 4$$, the period of $$3 \pmod{2^m}$$ is $$2^{m-2}$$

Proof:

• By Lemma 3: $$3^{2^{m-2}} \equiv 2^m + 1 \pmod{2^{m+1}} \equiv 1 \pmod{2^m}$$
• By Lemma 3: $$3^{2^{m-3}} \equiv 2^{m-1} + 1 \pmod{2^m} \not \equiv 1 \pmod{2^m}$$
• By Lemma 2: $$2^{m-2}$$ is the period of $$3 \pmod{2^m}$$

QED

## Small Cases

Note: Corollary 4 only applies when $$m \ge 4$$. So let’s consider $$m < 4$$ individually:

• $$m = 1$$: $$3^1 = 3 \equiv 1 \pmod{2^1}$$ so the period is 1.
• $$m = 2$$: $$3^2 = 9 \equiv 1 \pmod{2^2}$$ and $$3^1 = 3 \not \equiv 1 \pmod{2^2}$$ so the period is 2.
• $$m = 3$$: $$3^2 = 9 \equiv 1 \pmod{2^3}$$ and $$3^1 = 3 \not \equiv 1 \pmod{2^3}$$ so the period is 2.

Thus we can actually expand Corollary 4 to:

Theorem 5: The period of $$3 \pmod{2^m}$$ is:

• $$2^{m-2}$$ for all $$m \ge 3$$
• $$2^{m-1}$$ for all $$m = 1, 2$$

## Motivation for Lemma 3

Lemma 3 turned out to be the crux of this proof. Without knowing it, I don’t know how we’d prove this result. But how could we have guessed the statement in Lemma 3? Here’s one idea I have. It’s not the most elegant, but it seems to work:

Let’s break down 3 into base 2: $$3^{2^n} = (1 + 2)^{2^n}$$ and calculate these out using binomial expansion (assuming sufficiently large $$n$$):

$(1 + 2)^{2^n} = \begin{cases} & & 1 \\ &+& 2^1 \cdot 2^n \\ &+& 2^2 \cdot \frac{2^n (2^n - 1)}{2} \\ &+& 2^3 \cdot \frac{2^n (2^n - 1) (2^n - 2)}{2 \cdot 3} \\ &+& 2^4 \cdot \frac{2^n (2^n - 1) (2^n - 2) (2^n - 3)}{2 \cdot 3 \cdot 4} \\ &+& 2^5 \cdot \frac{2^n (2^n - 1) (2^n - 2) (2^n - 3) (2^n - 4)}{2 \cdot 3 \cdot 4 \cdot 5} \\ &+& 2^6 \cdot \frac{2^n (2^n - 1) (2^n - 2) (2^n - 3) (2^n - 4) (2^n - 5)}{2 \cdot 3 \cdot 4 \cdot 5 \cdot 6} \\ &+& 2^7 \cdot \frac{2^n (2^n - 1) (2^n - 2) (2^n - 3) (2^n - 4) (2^n - 5) (2^n - 6)}{2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7} \\ &+& 2^8 \cdot \frac{2^n (2^n - 1) (2^n - 2) (2^n - 3) (2^n - 4) (2^n - 5) (2^n - 6) (2^n - 7)}{2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8} \\ &+& 2^9 \cdot \frac{2^n (2^n - 1) (2^n - 2) (2^n - 3) (2^n - 4) (2^n - 5) (2^n - 6) (2^n - 7) (2^n - 8)}{2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8 \cdot 9} \\ &+& ... \\ \end{cases} = \begin{cases} & & 1 \\ &+& 2^{n+1} \\ &+& -2^{n+1} + 2^{n(n+1)} \\ &+& 2^{n+3} \cdot \frac{(2^n - 1) (2^{n-1} - 1)}{3} \\ &+& 2^{n+2} \cdot \frac{(2^n - 1) (2^{n-1} - 1) (2^n - 3)}{3} \\ &+& 2^{n+5} \cdot \frac{(2^n - 1) (2^{n-1} - 1) (2^n - 3) (2^{n-2} - 1)}{3 \cdot 5} \\ &+& 2^{n+4} \cdot \frac{(2^n - 1) (2^{n-1} - 1) (2^n - 3) (2^{n-2} - 1) (2^n - 5)}{3^2 \cdot 5} \\ &+& 2^{n+7} \cdot \frac{(2^n - 1) (2^{n-1} - 1) (2^n - 3) (2^{n-2} - 1) (2^n - 5) (2^{n-1} - 3)}{3^2 \cdot 5 \cdot 7} \\ &+& 2^{n+5} \cdot \frac{(2^n - 1) (2^{n-1} - 1) (2^n - 3) (2^{n-2} - 1) (2^n - 5) (2^{n-1} - 3) (2^n - 7)}{3^2 \cdot 5 \cdot 7} \\ &+& 2^{n+9} \cdot \frac{(2^n - 1) (2^{n-1} - 1) (2^n - 3) (2^{n-2} - 1) (2^n - 5) (2^{n-1} - 3) (2^n - 7) (2^{n-3} - 1)}{3^4 \cdot 5 \cdot 7} \\ &+& ... \\ \end{cases}$

Note: I have not proven it here, but the rest of the terms (in the …) will all be multiples of a sufficiently large power of 2 ($$\ge 2^8$$). You can intuitively see this because the $$2^k$$ term grows much faster than the power of 2 in $$k!$$.

Taking this equation mod $$2^{n+3}$$ we see:

$3^{2^n} = (1 + 2)^{2^n} \equiv 1 + 2^{n+2} \cdot \frac{(2^n - 1) (2^{n-1} - 1) (2^n - 3)}{3} \pmod{2^{n+3}}$

and whatever $$\frac{(2^n - 1) (2^{n-1} - 1) (2^n - 3)}{3}$$ is, we know for certain that it is odd so we call it $$2k + 1$$. Then we can simplify this further to:

$3^{2^n} \equiv 1 + 2^{n+2} (2k + 1) \equiv 1 + 2^{n+2} \pmod{2^{n+3}}$

Huzzah!

Well, I don’t know if anyone else will appreciate this approach or find it motivating. It is certainly very grungy! But I like it because it feels like this approach might extend to other examples (like finding the period of $$4 \pmod{3^m}$$). Better to have a grungy general method to crank through than simply hope I can guess the rule!