Period of 3 (mod 2^m)
In my previous post I mentioned that I did not know a simple proof that the period of
Background
First let’s remember that the period (also called the order) of an element
Lemma 1: If
Proof: Let
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
Proof: Let
Period of 3
OK, applying this to our case of
Therefore the period
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
Proof: We prove this via induction on
- Base Case (
): . QED - Inductive Step: Assuming
: Thus there exists some such that , so:
QED
Corollary 4: For all
Proof:
- By Lemma 3:
- By Lemma 3:
- By Lemma 2:
is the period of
QED
Small Cases
Note: Corollary 4 only applies when
: so the period is 1. : and so the period is 2. : and so the period is 2.
Thus we can actually expand Corollary 4 to:
Theorem 5: The period of
for all for all
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:
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 (
Taking this equation mod
and whatever
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