20200901, 02:39  #1 
Jun 2019
100010_{2} Posts 
a nice remark about mersene composite
a nice remark
Mersenne Number 2^{n}1 x^{2} = (2^{n2})1 mod 2^{n}1 there is no solution for x if 2^{n}1 composite 
20200901, 03:16  #2 
"Sam"
Nov 2016
2^{2}·79 Posts 
Claim: If 2^n1 is not prime, then 2^(n2)1 is a quadratic nonresidue mod 2^n1.
The claim is false, however the contrapositive is true: If 2^n1 is prime, then 2^(n2)1 is a quadratic residue mod 2^n1. 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^n1. 2^(n2)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^n1 such that the claim is false. If n = 3^k, then 2^n1 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^n1 is congruent to 1 mod 3: Any arbitrary integer N has about ln(ln(N)) prime factors, so 2^n1 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? 
20200901, 11:32  #3 
Feb 2017
Nowhere
3·1,193 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Nicetohave's  kar_bon  Prime Wiki  1  20190226 09:57 
Nice pic  Dubslow  Forum Feedback  0  20120502 02:13 
Let's do another nice big GNFS job!  fivemack  Factoring  84  20110426 10:22 
Mersene Prime and Number Theory  Ricie  Miscellaneous Math  24  20090814 15:31 
6 digit numbers and the mersene 40  Sykes1024  Math  7  20040210 09:43 