7.11.16

The order of 2 mod n when n is a Mersenne number

In my previous entries I discussed the largest power i of 2 such that 2i <  n for any odd integer n and I claimed a few things about it. Here I make another claim related to Mersenne numbers that I managed to prove.

Claim: If n = 2i - 1 (also known as a Mersenne number), then the order of 2 mod n is i.

Proof: If n is a Mersenne number then by definition n = 2i - 1 so then n - 1  = 2i and so clearly 2i = 1 modulo n.

By definition, the order of an element a modulo n is the smallest integer b such that ab = 1 mod n so it remains to show that i is the smallest integer such that 2i = 1 modulo n.

I'll show this by contradiction. Suppose there exists an integer k such that k < i and yet 2k= 1 mod n. Transforming this congruence relation to a diophantine equation yields

If 2= 1 mod n then for some integer x,  nx + (-1) =  2k  so nx - 1  =  2k

Clearly, x must be greater than 1 since it is given that n - 1 = n*1 - 1 = 2i and k is not equal to i

Therefore, (nx - 1) > (n - 1) so therefore 2k > 2i so therefore k > i, which is a contradiction to the supposition that k < i ...

Example: It is easy to calculate the order of two mod n for the first few Mersenne numbers.
The first few Mersenne numbers are 3, 7, 15, 31, 63, 127, 255 and the order of 2 mod n for each of these choices is 2,3,4,5,6,7,8 respectively.


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