# Disprove: If $\gcd(n,2^n-1)=1$, then $2^n-1$ is squarefree.

Disprove: If $\gcd(n,2^n-1)=1$, then $2^n-1$ is squarefree.

Equivalently, if $2^n-1$ is not squarefree, then $\gcd(n,2^n-1)\neq 1.$

Exercise, which I do,says to show that statement above is false. I checked manually $n \leq 348$ by this page: https://www.alpertron.com.ar/ECM.HTM. Maybe I didn't notice some factor. I tried also by easy computing by supposing to have prime $q$ that $q^2|2^n-1.$

Can you please to provide me with any hint, but no solution.?

$$2^{364} - 1 = 3 \cdot 5 \cdot 29 \cdot 43 \cdot 53 \cdot 113 \cdot 127 \cdot 157 \cdot 911 \cdot 1093^2 \cdot 1613 \cdot 2731 \cdot 4733 \cdot 8191 \cdot \mbox{BIG}$$

and $$364 = 4 \cdot 7 \cdot 13$$   $$2^{1755} - 1 = 7 \cdot 31 \cdot 73 \cdot 79 \cdot 151 \cdot 271 \cdot 631 \cdot 937 \cdot 3511^2 \cdot 6553 \cdot 8191 \cdot \mbox{BIG}$$ and $$1755 = 27 \cdot 5 \cdot 13$$

Here is output with few restrictions:

Sat Jul 28 16:16:32 PDT 2018
1    GCD:  1    1 =  1
2    GCD:  1    3 =  3
3    GCD:  1    7 =  7
4    GCD:  1    15 = 3  5
5    GCD:  1    31 =  31
6    GCD:  3    63 = 3^2  7
7    GCD:  1    127 =  127
8    GCD:  1    255 = 3 5  17
9    GCD:  1    511 = 7  73
10    GCD:  1    1023 = 3 11  31
11    GCD:  1    2047 = 23  89
12    GCD:  3    4095 = 3^2 5 7  13
13    GCD:  1    8191 =  8191
14    GCD:  1    16383 = 3 43  127
15    GCD:  1    32767 = 7 31  151
16    GCD:  1    65535 = 3 5 17  257
17    GCD:  1    131071 =  131071
18    GCD:  9    262143 = 3^3 7 19  73
19    GCD:  1    524287 =  524287
20    GCD:  5    1048575 = 3 5^2 11 31  41
Sat Jul 28 16:16:32 PDT 2018

• Just curious: how did you get that? Brute force? – Anonymous Jul 28 '18 at 22:52
• @Anonymous yes. I have a custom factoring command that says to use just primes factors from 2 up to a bound I specify. This time I said 10000, fairly quick regardless of the number being factored. – Will Jagy Jul 28 '18 at 22:55
• @Anonymous the sequence $M_n=(2^n-1)$ is a divisibilty sequence. That means if $p\mid n$ then $M_p$ divides $M_n$. – Daniel Buck Jul 28 '18 at 23:27
• @Anonymous it is easy to prove -- if $p|n$, then exists integer $k$ that $n=kp$, hence $2^n-1=2^{kp}-1=(2^p)^k-1^k=(2^p-1)\cdot\text{something}$. – jpatrick Jul 29 '18 at 11:49
• Note that $1093$ and $3511$ are the (only known) Wieferich-primes. If the exponent in the Mersenne number is a prime $p$, then a prime number $q$ satisfying $q^2\mid 2^p-1$ must be a Wieferich prime. With a prime exponent, the known Wieferich-primes cannot satisfy this condition , but your question only requires that $n$ and $2^n-1$ are coprime. Because of this strong necessary condition, it is conjectured that $2^p-1$ with prime number $p$ is always squarefree. – Peter Jul 29 '18 at 12:25

As written, stringify accepts numbers only up to about 2,000,000,000 . However, putting such a large bound in the factoring routine would make it very, very slow.

#include <iostream>
#include <stdlib.h>
#include <fstream>
#include <sstream>
#include <list>
#include <set>
#include <math.h>
#include <iomanip>
#include <string>
#include <algorithm>
#include <iterator>
#include <gmp.h>
#include <gmpxx.h>
using namespace std;

const int LARGEINT = 2147483647  ;
const int BILLION  = 1000000000  ;
const double my_pi = 4 * atan(1.0);

//  form.h      July2003

string stringify(unsigned int x)
{
ostringstream o;
o << x  ;
return o.str();
}

int mp_PrimeQ( mpz_class  i)
{
if ( i <= 0 ) return 0;
else if ( i == 1 ) return 1;
else return  mpz_probab_prime_p( i.get_mpz_t() , 50 );
} // mp_PrimeQ

string mp_Factored_primebound( mpz_class  i, mpz_class bound)
{
int squarefac = 0;
string fac;
fac = " = ";
int p = 2;
mpz_class  temp = i;
if (temp < 0 )
{
temp *= -1;
fac += " -1 * ";
}

if ( 1 == temp) fac += " 1 ";
if ( temp > 1)
{
int primefac = 0;
while( temp > 1 && p <= bound && p * p <= temp)
{
if (temp % p == 0)
{
++primefac;
if (primefac > 1) fac += " ";
fac += stringify( p) ;
temp /= p;
int exponent = 1;
while (temp % p == 0)
{
temp /= p;
++exponent;
} // while p is fac
if ( exponent > 1)
{
fac += "^" ;
fac += stringify( exponent) ;
if (p >2) ++squarefac ;
}
}  // if p is factor
++p;
} // while p
if (temp > 1 && primefac >= 1) fac += " ";
if (temp > 1 && temp < bound * bound  ){ fac += " "; fac +=   temp.get_str()   ;}

if (temp > 1 && temp >= bound * bound  ){ fac += " cdot mbox{BIG} "; }
//  if (squarefac) fac += "      WOW " ;
} // temp > 1
return fac;
} // mp_Factored_primebound