Go Back > Extra Stuff > Miscellaneous Math

Closed Thread
Thread Tools
Old 2020-09-01, 02:39   #1
baih's Avatar
Jun 2019

2216 Posts
Default 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
baih is offline  
Old 2020-09-01, 03:16   #2
carpetpool's Avatar
Nov 2016

52·13 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?
carpetpool is offline  
Old 2020-09-01, 11:32   #3
Dr Sardonicus
Dr Sardonicus's Avatar
Feb 2017

3×1,657 Posts

Originally Posted by baih View Post
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.
Dr Sardonicus is offline  
Closed Thread

Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
Nice-to-have's kar_bon Prime Wiki 1 2019-02-26 09:57
Nice pic Dubslow Forum Feedback 0 2012-05-02 02:13
Let's do another nice big GNFS job! fivemack Factoring 84 2011-04-26 10:22
Mersene Prime and Number Theory Ricie Miscellaneous Math 24 2009-08-14 15:31
6 digit numbers and the mersene 40 Sykes1024 Math 7 2004-02-10 09:43

All times are UTC. The time now is 06:08.

Sun Oct 17 06:08:56 UTC 2021 up 86 days, 37 mins, 0 users, load averages: 0.92, 0.97, 0.95

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.