Originally Posted by ATH
Testing natural numbers from 2 to 11213, this conjecture is true only for the exponents of the 23 first prime mersenne numbers except 2 is missing and 4 is included:
3,4,5,7,13,17,19,31,61,89,107,127,521,607,1279,2203,2281,3217,4253,4423,9689,9941,11213
You can simplify this alot:
k=2^{n}1, m=k*(n1)n+2, x=m*k
Now your conditions is equivalent to: 2^{x1} = 1 (mod k) AND (kn+2)^{x1} = 1 (mod k)
Explanation:
Since x=m*k:
2^(x1)==(a+1)(mod m*k) => 2^(x1) = m*k*c1 + a+1 for some constant c1
and
a==0(mod k) => a = k*c2 for some constant c2.
Inserting k*c2 for a in the first equation gives:
2^(x1) = m*k*c1 + k*c2 + 1 = 1 (mod k)
In the same way it can be shown:
m^(x1) = 1 (mod k)
But instead of m it's faster to use m mod k:
m = k*(n1)n+2 = n+2 (mod k) = kn+2 (mod k) (n+2 is negative, so if we want we can add k to make it positive)
So:
m^(x1) = (n+2)^(x1) = (kn+2)^(x1) = 1 (mod k)
This is why n=2 doesn't work since kn+2 = k and k^(x1) = 0 (mod k)
