a nice remark about mersene composite

[baih]

a nice remark
Mersenne Number 2ⁿ-1

x² = (2^n-2)-1 mod 2ⁿ-1

there is no solution for x if 2ⁿ-1 composite

[carpetpool]

Claim: If 2^n-1 is not prime, then 2^(n-2)-1 is a quadratic non-residue mod 2^n-1.

The claim is false, however the contrapositive is true:

If 2^n-1 is prime, then 2^(n-2)-1 is a quadratic residue mod 2^n-1.

n = 2 is a special case implying that x^2 = 0 mod 3, which has solution x = 0 (trivial).

In all other cases, n must be odd. For simplicity, suppose p = 2^n-1.

2^(n-2)-1 = (p - 3)/4

p = 1 mod 3, and since p is prime, quadratic reciprocity tells us that x^2 = -3 mod p is solvable.

Hence, x^2 = (p - 3)/4 mod p,
4*x^2 = p - 3 mod p, or (2*x)^2 = -3 mod p.
The map x --> 2*x is a bijection in Zp/Z. Done. Proven.

Now what remains is to show when your claim is false (given n is composite):

If every prime q | p is congruent to 1 mod 3, then the claim is false.

Since q = 1 mod 3, x^2 = -3 mod q will have a solution,

using the Chinese Remainder Theorem allows us to construct a solution x to x^2 = -3 mod p, so the conclusion follows.

There are infinitely many composite numbers of the form 2^n-1 such that the claim is false.

If n = 3^k, then 2^n-1 is a counterexample if k > 2, since every prime q | 2^(3^k) - 1, the order of 2 mod q by definition divides 3^k, and trivially cannot be 1, so q = 1 mod 3.

I do not find your claim interesting at all, what I find interesting is finding the density of primes n such that each prime q | 2^n-1 is congruent to 1 mod 3:

Any arbitrary integer N has about ln(ln(N)) prime factors, so 2^n-1 will have on average, ln(n) prime factors by this assumption.

The probability that all of these factors are congruent to 1 mod 3 is about 1/2^(ln(n)). I suppose there is a better estimate?

[Dr Sardonicus]

Originally Posted by baih

a nice remark
Mersenne Number 2ⁿ-1

x² = (2^n-2)-1 mod 2ⁿ-1

there is no solution for x if 2ⁿ-1 composite

The smallest prime exponent which furnishes a counterexample is n = 37. Thread closed.