 mersenneforum.org a nice remark about mersene composite
 Register FAQ Search Today's Posts Mark Forums Read 2020-09-01, 02:39 #1 baih   Jun 2019 1000102 Posts a nice remark about mersene composite a nice remark Mersenne Number 2n-1 x2 = (2n-2)-1 mod 2n-1 there is no solution for x if 2n-1 composite  2020-09-01, 03:16 #2 carpetpool   "Sam" Nov 2016 22·79 Posts 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?  2020-09-01, 11:32   #3
Dr Sardonicus

Feb 2017
Nowhere

3·1,193 Posts Quote:
 Originally Posted by baih a nice remark Mersenne Number 2n-1 x2 = (2n-2)-1 mod 2n-1 there is no solution for x if 2n-1 composite
The smallest prime exponent which furnishes a counterexample is n = 37. Thread closed. Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post kar_bon Prime Wiki 1 2019-02-26 09:57 Dubslow Forum Feedback 0 2012-05-02 02:13 fivemack Factoring 84 2011-04-26 10:22 Ricie Miscellaneous Math 24 2009-08-14 15:31 Sykes1024 Math 7 2004-02-10 09:43

All times are UTC. The time now is 23:03.

Wed Oct 28 23:03:35 UTC 2020 up 48 days, 20:14, 1 user, load averages: 1.58, 1.65, 1.77