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]
Example: Let n = 33. Clearly 33 = 25 + 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, …]
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, …]