Desapruebe: si$\gcd(n,2^n-1)=1$, entonces$2^n-1$ es squarefree.

Question

Refutar: Si $\gcd(n,2^n-1)=1$, $2^n-1$ es squarefree.

Equivalentemente, si $2^n-1$ no es squarefree, a continuación, $\gcd(n,2^n-1)\neq 1.$

El ejercicio, que puedo hacer,dice para mostrar que la afirmación anterior es falsa. He comprobado manualmente $n \leq 348$ en esta página: https://www.alpertron.com.ar/ECM.HTM. Tal vez no me he dado cuenta de algún factor. He intentado también por la facilidad de la computación por suponer que tienen prime $q$ que $q^2|2^n-1.$

Puede usted por favor me proporcione alguna pista, pero no la solución.?

Answer 1

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

Aquí se muestra con pocas restricciones:

 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
 

Answer 2

Como está escrito, stringify acepta números solo hasta aproximadamente 2,000,000,000. Sin embargo, poner un límite tan grande en la rutina de factorización lo haría muy, muy lento.

 #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