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

Clash Royale CLAN TAG#URR8PPP

up vote
4
down vote

favorite

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

elementary-number-theory coprime mersenne-numbers

share|cite|improve this question

edited Jul 28 at 22:37

asked Jul 28 at 22:27

jpatrick

334212

add a comment | 

up vote
4
down vote

favorite

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

elementary-number-theory coprime mersenne-numbers

share|cite|improve this question

edited Jul 28 at 22:37

asked Jul 28 at 22:27

jpatrick

334212

add a comment | 

up vote
4
down vote

favorite

up vote
4
down vote

favorite

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

elementary-number-theory coprime mersenne-numbers

share|cite|improve this question

edited Jul 28 at 22:37

asked Jul 28 at 22:27

jpatrick

334212

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

elementary-number-theory coprime mersenne-numbers

share|cite|improve this question

edited Jul 28 at 22:37

asked Jul 28 at 22:27

jpatrick

334212

share|cite|improve this question

share|cite|improve this question

edited Jul 28 at 22:37

edited Jul 28 at 22:37

edited Jul 28 at 22:37

asked Jul 28 at 22:27

jpatrick

334212

asked Jul 28 at 22:27

jpatrick

334212

asked Jul 28 at 22:27

jpatrick

334212

334212

add a comment | 

add a comment | 

2 Answers
2

active

oldest

votes

up vote
6
down vote



accepted

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

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

share|cite|improve this answer

edited Jul 28 at 23:17

answered Jul 28 at 22:50

Will Jagy

96.8k594195

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Just curious: how did you get that? Brute force?
  – Anonymous
  Jul 28 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 at 22:55
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @Anonymous the sequence $M_n=(2^n-1)$ is a divisibilty sequence. That means if $pmid n$ then $M_p$ divides $M_n$.
  – Daniel Buck
  Jul 28 at 23:27
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @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)cdottextsomething$.
  – jpatrick
  Jul 29 at 11:49
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  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^2mid 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 at 12:25
  
  

  
  
  
  

 | 
show 3 more comments

up vote
1
down vote

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 mboxBIG "; 
 // if (squarefac) fac += " WOW " ;
 // temp > 1
 return fac;
 // mp_Factored_primebound

share|cite|improve this answer

answered Jul 29 at 14:46

Will Jagy

96.8k594195

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2865623%2fdisprove-if-gcdn-2n-1-1-then-2n-1-is-squarefree%23new-answer', 'question_page');

);

Post as a guest

Name Email

2 Answers
2

active

oldest

votes

2 Answers
2

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
6
down vote



accepted

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

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

share|cite|improve this answer

edited Jul 28 at 23:17

answered Jul 28 at 22:50

Will Jagy

96.8k594195

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Just curious: how did you get that? Brute force?
  – Anonymous
  Jul 28 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 at 22:55
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @Anonymous the sequence $M_n=(2^n-1)$ is a divisibilty sequence. That means if $pmid n$ then $M_p$ divides $M_n$.
  – Daniel Buck
  Jul 28 at 23:27
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @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)cdottextsomething$.
  – jpatrick
  Jul 29 at 11:49
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  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^2mid 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 at 12:25
  
  

  
  
  
  

 | 
show 3 more comments

up vote
6
down vote



accepted

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

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

share|cite|improve this answer

edited Jul 28 at 23:17

answered Jul 28 at 22:50

Will Jagy

96.8k594195

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Just curious: how did you get that? Brute force?
  – Anonymous
  Jul 28 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 at 22:55
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @Anonymous the sequence $M_n=(2^n-1)$ is a divisibilty sequence. That means if $pmid n$ then $M_p$ divides $M_n$.
  – Daniel Buck
  Jul 28 at 23:27
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @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)cdottextsomething$.
  – jpatrick
  Jul 29 at 11:49
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  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^2mid 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 at 12:25
  
  

  
  
  
  

 | 
show 3 more comments

up vote
6
down vote



accepted

up vote
6
down vote



accepted

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

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

share|cite|improve this answer

edited Jul 28 at 23:17

answered Jul 28 at 22:50

Will Jagy

96.8k594195

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

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

share|cite|improve this answer

edited Jul 28 at 23:17

answered Jul 28 at 22:50

Will Jagy

96.8k594195

share|cite|improve this answer

share|cite|improve this answer

edited Jul 28 at 23:17

edited Jul 28 at 23:17

edited Jul 28 at 23:17

answered Jul 28 at 22:50

Will Jagy

96.8k594195

answered Jul 28 at 22:50

Will Jagy

96.8k594195

answered Jul 28 at 22:50

Will Jagy

96.8k594195

96.8k594195

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Just curious: how did you get that? Brute force?
  – Anonymous
  Jul 28 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 at 22:55
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @Anonymous the sequence $M_n=(2^n-1)$ is a divisibilty sequence. That means if $pmid n$ then $M_p$ divides $M_n$.
  – Daniel Buck
  Jul 28 at 23:27
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @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)cdottextsomething$.
  – jpatrick
  Jul 29 at 11:49
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  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^2mid 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 at 12:25
  
  

  
  
  
  

 | 
show 3 more comments

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Just curious: how did you get that? Brute force?
  – Anonymous
  Jul 28 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 at 22:55
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @Anonymous the sequence $M_n=(2^n-1)$ is a divisibilty sequence. That means if $pmid n$ then $M_p$ divides $M_n$.
  – Daniel Buck
  Jul 28 at 23:27
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @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)cdottextsomething$.
  – jpatrick
  Jul 29 at 11:49
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  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^2mid 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 at 12:25
  
  

  
  
  
  

Just curious: how did you get that? Brute force?
– Anonymous
Jul 28 at 22:52

Just curious: how did you get that? Brute force?
– Anonymous
Jul 28 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 at 22:55

@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 at 22:55

1

1

@Anonymous the sequence $M_n=(2^n-1)$ is a divisibilty sequence. That means if $pmid n$ then $M_p$ divides $M_n$.
– Daniel Buck
Jul 28 at 23:27

@Anonymous the sequence $M_n=(2^n-1)$ is a divisibilty sequence. That means if $pmid n$ then $M_p$ divides $M_n$.
– Daniel Buck
Jul 28 at 23:27

1

1

@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)cdottextsomething$.
– jpatrick
Jul 29 at 11:49

@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)cdottextsomething$.
– jpatrick
Jul 29 at 11:49

1

1

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^2mid 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 at 12:25

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^2mid 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 at 12:25

 | 
show 3 more comments

up vote
1
down vote

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 mboxBIG "; 
 // if (squarefac) fac += " WOW " ;
 // temp > 1
 return fac;
 // mp_Factored_primebound

share|cite|improve this answer

answered Jul 29 at 14:46

Will Jagy

96.8k594195

add a comment | 

up vote
1
down vote

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 mboxBIG "; 
 // if (squarefac) fac += " WOW " ;
 // temp > 1
 return fac;
 // mp_Factored_primebound

share|cite|improve this answer

answered Jul 29 at 14:46

Will Jagy

96.8k594195

add a comment | 

up vote
1
down vote

up vote
1
down vote

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 mboxBIG "; 
 // if (squarefac) fac += " WOW " ;
 // temp > 1
 return fac;
 // mp_Factored_primebound

share|cite|improve this answer

answered Jul 29 at 14:46

Will Jagy

96.8k594195

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 mboxBIG "; 
 // if (squarefac) fac += " WOW " ;
 // temp > 1
 return fac;
 // mp_Factored_primebound

share|cite|improve this answer

answered Jul 29 at 14:46

Will Jagy

96.8k594195

share|cite|improve this answer

share|cite|improve this answer

answered Jul 29 at 14:46

Will Jagy

96.8k594195

answered Jul 29 at 14:46

Will Jagy

96.8k594195

answered Jul 29 at 14:46

Will Jagy

96.8k594195

96.8k594195

add a comment | 

add a comment | 

 

draft saved

draft discarded

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2865623%2fdisprove-if-gcdn-2n-1-1-then-2n-1-is-squarefree%23new-answer', 'question_page');

);

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email