Period of 3 (mod 2^m)

In my previous post I mentioned that I did not know a simple proof that the period of $3 (\mod 2^{m})$ was exactly $2^{m - 2}$ (For $m \geq 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 (\mod b)$ is the smallest positive value $d$ such that $a^{d} \equiv 1 (\mod b)$ .

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

Proof: Let $n = t d + r$ (where $0 \leq r < d$ ), then $1 \equiv a^{n} = (a^{d})^{t} \cdot a^{r} \equiv 1^{t} \cdot a^{r} = a^{r} (\mod b)$ . So $a^{r} \equiv 1 (\mod b)$ and $r < d$ . But $d$ is (by definition) the smallest positive value such that $a^{d} \equiv 1 (\mod 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 (\mod p^{m})$ and $a^{p^{k - 1}} ≢ 1 (\mod p^{m})$ then the period of $a (\mod p^{m})$ is exactly $p^{k}$

Proof: Let $d$ be the period of $a (\mod 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 (\mod 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 (\mod 2^{m})$ : we know from Euler’s totient theorem that:

3^{ϕ (2^{m})} = 3^{2^{m - 1}} \equiv 1 (\mod 2^{m})

Therefore the period $d$ of $3 (\mod 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 (\mod 2^{m})$ and $3^{2^{k - 1}} ≢ 1 (\mod 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 \geq 1$ , $3^{2^{n}} \equiv 2^{n + 2} + 1 (\mod 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 (\mod 2^{n + 3})$ : Thus there exists some $t$ such that $3^{2^{n}} = 2^{n + 2} + 1 + t \cdot 2^{n + 3} = (1 + 2 t) 2^{n + 2} + 1$ , so:

3^{2^{n + 1}} = (3^{2^{n}})^{2} = ((1 + 2 t) 2^{n + 2} + 1)^{2} = (1 + 2 t)^{2} (2^{n + 2})^{2} + 2 (1 + 2 t) 2^{n + 2} + 1 \equiv 2^{n + 3} + 1 (\mod 2^{n + 4})

QED

Corollary 4: For all $m \geq 4$ , the period of $3 (\mod 2^{m})$ is $2^{m - 2}$

Proof:

By Lemma 3: $3^{2^{m - 2}} \equiv 2^{m} + 1 (\mod 2^{m + 1}) \equiv 1 (\mod 2^{m})$
By Lemma 3: $3^{2^{m - 3}} \equiv 2^{m - 1} + 1 (\mod 2^{m}) ≢ 1 (\mod 2^{m})$
By Lemma 2: $2^{m - 2}$ is the period of $3 (\mod 2^{m})$

QED

Small Cases

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

$m = 1$ : $3^{1} = 3 \equiv 1 (\mod 2^{1})$ so the period is 1.
$m = 2$ : $3^{2} = 9 \equiv 1 (\mod 2^{2})$ and $3^{1} = 3 ≢ 1 (\mod 2^{2})$ so the period is 2.
$m = 3$ : $3^{2} = 9 \equiv 1 (\mod 2^{3})$ and $3^{1} = 3 ≢ 1 (\mod 2^{3})$ so the period is 2.

Thus we can actually expand Corollary 4 to:

Theorem 5: The period of $3 (\mod 2^{m})$ is:

$2^{m - 2}$ for all $m \geq 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 ( $\geq 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} (\mod 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 $2 k + 1$ . Then we can simplify this further to:

3^{2^{n}} \equiv 1 + 2^{n + 2} (2 k + 1) \equiv 1 + 2^{n + 2} (\mod 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 (\mod 3^{m})$ ). Better to have a grungy general method to crank through than simply hope I can guess the rule!