In my previous post I mentioned that I did not know a simple proof that the period of 3(mod2m) was exactly 2m2 (For m3). 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(modb) is the smallest positive value d such that ad1(modb).

Lemma 1: If an1(modb) then n is divisible by the period d of a(modb)

Proof: Let n=td+r (where 0r<d), then 1an=(ad)tar1tar=ar(modb). So ar1(modb) and r<d. But d is (by definition) the smallest positive value such that ad1(modb), so the only option is that r=0 (is not positive). And thus n=td 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 apk1(modpm) and apk11(modpm) then the period of a(modpm) is exactly pk

Proof: Let d be the period of a(modpm). Then d divides pk by Lemma 1. But d does not divide pk1 (if it did, then apk11(modpm)). But the only d that divides pk, but not pk1 is d=pk. QED

Period of 3

OK, applying this to our case of 3(mod2m): we know from Euler’s totient theorem that:

3ϕ(2m)=32m11(mod2m)

Therefore the period d of 3(mod2m) must divide 2m1. Thus d=2k for k<m. And by Lemma 2, we can see that to prove it we must simply find a k such that 32k1(mod2m) and 32k11(mod2m).

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 n1, 32n2n+2+1(mod2n+3)

Proof: We prove this via induction on n:

  • Base Case (n=1): 321=9=23+1. QED
  • Inductive Step: Assuming 32n2n+2+1(mod2n+3): Thus there exists some t such that 32n=2n+2+1+t2n+3=(1+2t)2n+2+1, so:
32n+1=(32n)2=((1+2t)2n+2+1)2=(1+2t)2(2n+2)2+2(1+2t)2n+2+12n+3+1(mod2n+4)

QED

Corollary 4: For all m4, the period of 3(mod2m) is 2m2

Proof:

  • By Lemma 3: 32m22m+1(mod2m+1)1(mod2m)
  • By Lemma 3: 32m32m1+1(mod2m)1(mod2m)
  • By Lemma 2: 2m2 is the period of 3(mod2m)

QED

Small Cases

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

  • m=1: 31=31(mod21) so the period is 1.
  • m=2: 32=91(mod22) and 31=31(mod22) so the period is 2.
  • m=3: 32=91(mod23) and 31=31(mod23) so the period is 2.

Thus we can actually expand Corollary 4 to:

Theorem 5: The period of 3(mod2m) is:

  • 2m2 for all m3
  • 2m1 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: 32n=(1+2)2n and calculate these out using binomial expansion (assuming sufficiently large n):

(1+2)2n={1+212n+222n(2n1)2+232n(2n1)(2n2)23+242n(2n1)(2n2)(2n3)234+252n(2n1)(2n2)(2n3)(2n4)2345+262n(2n1)(2n2)(2n3)(2n4)(2n5)23456+272n(2n1)(2n2)(2n3)(2n4)(2n5)(2n6)234567+282n(2n1)(2n2)(2n3)(2n4)(2n5)(2n6)(2n7)2345678+292n(2n1)(2n2)(2n3)(2n4)(2n5)(2n6)(2n7)(2n8)23456789+...={1+2n+1+2n+1+2n(n+1)+2n+3(2n1)(2n11)3+2n+2(2n1)(2n11)(2n3)3+2n+5(2n1)(2n11)(2n3)(2n21)35+2n+4(2n1)(2n11)(2n3)(2n21)(2n5)325+2n+7(2n1)(2n11)(2n3)(2n21)(2n5)(2n13)3257+2n+5(2n1)(2n11)(2n3)(2n21)(2n5)(2n13)(2n7)3257+2n+9(2n1)(2n11)(2n3)(2n21)(2n5)(2n13)(2n7)(2n31)3457+...

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 (28). You can intuitively see this because the 2k term grows much faster than the power of 2 in k!.

Taking this equation mod 2n+3 we see:

32n=(1+2)2n1+2n+2(2n1)(2n11)(2n3)3(mod2n+3)

and whatever (2n1)(2n11)(2n3)3 is, we know for certain that it is odd so we call it 2k+1. Then we can simplify this further to:

32n1+2n+2(2k+1)1+2n+2(mod2n+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(mod3m)). Better to have a grungy general method to crank through than simply hope I can guess the rule!