14.10.16

A Simple Formula For Finding The Order Of An Element

I have shown quite a few ways for finding the order of an element but all of the methods listed here so far entail going through a bunch of iterations. None of these methods are that exciting to me, not even the ultra sleek way of generating powers of 2 mod n backwards.

For the past several years I have been chasing after a far grander idea, the idea that there is a simple formula for finding the order of 2 mod n. It seems like there is a quick formula indeed but it is not the same for all.


Claim: If n is an odd integer such that n = 2i + 1 then the order of 2 mod n is 2*i.


Furthermore, given the set of all powers of 2 smaller than n, say S1 = [2, 4, 8,  ..., 2i] then the set of the remaining powers of 2 mod n, is S2 = [2i - 1, 2i - 3, 2i - 7, ..., 1]


Proof: Later


Example: Let n = 33. Clearly 33 = 2+ 1 so the order of 2 mod n is 2*5 = 10. It can be verified that 210 = 1 mod 33



Note: 2i + 1 can be either a prime or a composite integer but the formula stays the same. For all other n it seems that there are two different formulas depending on whether n is a prime or a composite.



Interestingly enough, if I construct a set of powers of 2 plus 1,  namely the set of 2i + 1 for i = 1,2,3 4, 5, 6... then obviously this set is [3, 5, 9, 17, 33, 65, …]

Note that the order of 2 mod 3 is 2, the order of 2 mod 5 is 4, the order of 2 mod 9 is 6, the order of 2 mod 17 is 8, the order of 2 mod 33 is 10, the order of 2 mod 65 is 12, and so on.

Reminder: the order of 2 mod n is the smallest integer k such that 2k = 1 mod n


Below is a slow calculator for finding the order of 2 mod n for any odd integer n:




So I boldly claim what no one (hopefully) has claimed before:


Claim: The set of the order of 2 mod n for each element of the set [3, 5, 9, 17, 33, 65,…]
is precisely the set of all even integers [2, 4, 6, 8, 10, 12, …]