4
$\begingroup$

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.?

$\endgroup$
6
$\begingroup$

$$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
$\endgroup$
  • $\begingroup$ Just curious: how did you get that? Brute force? $\endgroup$ – Anonymous Jul 28 '18 at 22:52
  • $\begingroup$ @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. $\endgroup$ – Will Jagy Jul 28 '18 at 22:55
  • 1
    $\begingroup$ @Anonymous the sequence $M_n=(2^n-1)$ is a divisibilty sequence. That means if $p\mid n$ then $M_p$ divides $M_n$. $\endgroup$ – Daniel Buck Jul 28 '18 at 23:27
  • 1
    $\begingroup$ @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}$. $\endgroup$ – jpatrick Jul 29 '18 at 11:49
  • 1
    $\begingroup$ 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. $\endgroup$ – Peter Jul 29 '18 at 12:25
1
$\begingroup$

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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.