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 2k = 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: