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 positive 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!