16
$\begingroup$

Given an integer $i$, find an integer $n$ ( $2^{j-1}\le n <2^j$), and a prime divisor $p$ of $M_n=2^n-1$, so that $v= j+i$; where $p$ is written as $k2^v+1$, $k$ odd.
In other words, $j$ is such that $2^{j-1}\le ord_p(2) <2^j$ where $ord_p(2)$ is the multiplicative order of $2$ in $Z/pZ^*$. Any odd number $p$ can be assigned such an $i$ value, but, when $p$ is prime, most of the times $v$ is smaller than $j$ and $i$ is negative. Most of the times $i$ is close to $-Log_2(p)+1$.

When only $i\ge 0$ are allowed, these primes $p$ become quite rare, and all the more that $i$ is large.

I wonder whether some real mathematician ever investigated this.

$65537 = 1.2^{16}+1$ is a divisor of $2^{2^5}-1$: here $v=16; j=6$ and $i=10$. This used to be the largest $i$ that I know.

$59393=29.2^{11}+1$ is a divisor of $2^{29.2^3}-1$: here $v=11; j=8$ and $i=3$.

$115201=225.2^9+1$ is a divisor of $2^{225}-1$: here $v=9; j=8$ and $i=1$.

For a Mersenne prime, $v=1$, (or $i=1-j$, it is always negative).

For a Fermat prime $p=2^{2^l}+1$, $v=2^l$, $j=l+2$, and $i=2^l-l-2$ can grow very big. Conversely, if one could prove that, for primes, $i$ as defined above is limited, wouldn't one also prove in the same time, as a corollary, that there are only finitely many Fermat primes?

I checked all primes below $4278255361$ and found only about $60$ primes (out of more than $200000000$) with $i\ge0$. This club is made more "select" if you let only the larger $i$ in: only about $30$ have $i\gt0$.

$51453953(i=0); 126074881(i=1); 115201(i=1)$ which are divisors of Mersenne number $M_n$ where $n$ is odd, were introduced to me here by Peter Košinár.

Other guys that you know are welcome in the club, if they qualify (larger than $4278255361$ and not already in the list for larger numbers hereafter). V.I.P. lounge access for $i>0$ only.

It seems that apart from Fermat primes themselves, prime divisors of Fermat numbers (like $2424833 (i=5)$) may provide some of the largest $i$ values. It can be demonstrated that prime divisors of Fermat numbers all have $i\ge0$. ... On the other hand, it seems that prime divisors of Mersenne numbers of prime index can very hardly have $i\ge0$...

But some very large $i$ are also obtained for primes which are not divisors of Fermat numbers.

For now, the top 13 is as follows:

  • N°13: $2424833 (i=5)$
  • N°12: $536903681 (i=8)$
  • N°11: $65537 (i=10)$
  • N°10: $140737471578113 (i=16)$
  • N°9: $18446744069414584321 (i=24)$
    Its $i$ almost matches that of $F_5=2^{2^5}+1 (i=25)$. $F_5$ would be in the top 10... if it was prime. This make me think of $18446744069414584321$ as a sort of 'failed' Fermat prime, though it is not even a divisor of a Fermat prime. Actually it is $(2^{3.2^5}+1)/F_5$.
  • N°8: $9444732965601851473921 (i=28)$
  • N°7: $604462909806215075725313 (i=31)$
  • N°6: $10384593717069655112945804582584321 (i=48)$
  • N°5: $2854495385411919762116496381035264358442074113 (i=66)$
  • N°4: $182687704666362864775461208552445184771578920961 (i=69)$
  • N°3: $11692013098647223345629483497433542615764159168513 (i=72)$
  • N°2: $187072209578355573530071639244871112681892570202113 (i=74)$
  • N°1: $883423532389192164791648750371459256584513952652893606156996040365965313 (i=110)$ Congratulations!

It seems that $Q_{p,j}=(2^{p.2^j}+1)/F_j$ has $i=2^j-j-2-Floor(Log_2(p))$. Therefore, just after Fermat primes, primes with large $i$ are to be looked for amongst $Q_{p,j}$, with $p$ as small as possible, whenever they are prime. The question is whether prime $Q_{p,j}$s are less rarities than prime $F_j$s... This might be so, since they have two indexes.

Also N°12, N°10 and the top 8 can be written as $p=2^q\pm2^{(q+1)/2}+1$ which is a divisor of $2^{4q}-1$, thanks to the Aurifeuillean factorization, therefore $ord_p(2)=4q$, $v=(q+1)/2$ and hence leads to $i=(q+1)/2 -3 -Floor(Log_2(q))$. This can be used to look for large $i$s, when $p=2^q\pm2^{(q+1)/2}+1$ is prime for a large $q$. Primes like this seem much more easy to find than prime $Q_{p,j}$.

Can someone find new primes for the top ten, which are not of the $2^q\pm2^{(q+1)/2}+1$ kind ?

Any non-Proth prime in the club? yes! $262657=513.2^9+1$. This is probably not the only one.. Any Cullen prime in the club? $141.2^{141} + 1$ has $i=-4$ though.

prime p / i 
  • 6487031809 / 2
  • 70525124609 / 0
  • 190274191361 / 0
  • 646730219521 / 0
  • 2710954639361 / 1
  • 2748779069441 / 1
  • 4432676798593 / 1
  • 4485296422913 / 0
  • 6597069766657 / 1
  • 25409026523137 / 0
  • 25991531462657 / 2
  • 31065037602817 / 0
  • 46179488366593 / 0
  • 67280421310721 / 0
  • 76861124116481 / 1
  • 140737471578113 / 16
  • 151413703311361 / 1
  • 192971705688577 / 1
  • 640126220763137 / 0
  • 1095981164658689 / 1
  • 1238926361552897 / 1
  • 18446744069414584321 / 24
  • 9444732965601851473921 / 28
  • 604462909806215075725313 / 31
  • 10384593717069655112945804582584321 / 48
  • 2854495385411919762116496381035264358442074113 / 66
  • 182687704666362864775461208552445184771578920961 / 69
  • 11692013098647223345629483497433542615764159168513 / 72
  • 187072209578355573530071639244871112681892570202113 / 74
  • 883423532389192164791648750371459256584513952652893606156996040365965313 / 110
$\endgroup$
4
  • $\begingroup$ later addition: the conjecture that prime divisors of Mersenne numbers of prime index all have $i<0$ is wrong. $2006858753$ has $i=0$, and is divisor of $2^{797}-1$. This is the only member of the club with this property (out of the 60 members smaller than $4278255361$)... $\endgroup$
    – René Gy
    Mar 8, 2014 at 22:37
  • $\begingroup$ Are you familiar with the lists of factors of numbers of the form $2^n-1$ compiled by Wagstaff et al.? See, e.g., homes.cerias.purdue.edu/~ssw/cun/index.html $\endgroup$ Mar 9, 2014 at 1:00
  • $\begingroup$ thank you, I ve heard of it, but now I realize that primes with large $i$ are likely to be obtained, by doing mining in these lists. So far, I used factordb.com to check the primality of very large numbers. I don't know which is best. $\endgroup$
    – René Gy
    Mar 9, 2014 at 13:50
  • $\begingroup$ Old post, but if $p$ divides the $m$-th Fermat number, then $j=m+2$, so $i$ is the number that is called $n-m-2$ here. The greatest known value of this to date is $i=10$ (for $25 \cdot 2^{2141884} + 1 = p | F_{2141872}$), but the empirical distribution (see the bottom of the link) looks close enough to the heuristic distribution (geometric with parameter $1/2$) that I would expect it to be unbounded. $\endgroup$ Oct 8, 2022 at 2:26

1 Answer 1

1
$\begingroup$

$2^5\lt49\lt2^6$; $2^{49}-1$ is divisible by the prime $p=4432676798593$; $p-1$ is $2^7$ times an odd number; so if I follow your definitions, $i=1$.

$\endgroup$
3
  • $\begingroup$ Thank you! this one was already in the club. Most of the times, when $p$ with $i\ge0$ divides $2^n-1$, where $n$ is odd, $n$ is composite, like here $49$. I know only one exception, see the above comment. $\endgroup$
    – René Gy
    Mar 9, 2014 at 13:41
  • $\begingroup$ If you're going to keep the club membership a secret, how do you expect anyone to help you? You wrote, "Other guys that you know (larger than 4278255361) are welcome in the club." My guy is larger than 4278255361. $\endgroup$ Mar 9, 2014 at 21:43
  • 1
    $\begingroup$ My apologies. I was not clear enough. The "club" is for $i\ge0$, I have checked all primes up to $4278255361$, but I had also found larger primes with that property. When I started, the list was quite short, but now they are more than 75 primes altogether, and continuously growing, (60 of them are below $4278255361$ up to where the list is exhaustive I believe). I thought it was too long list for publication here. I will update the the question with a list of all the primes larger than $4278255361$. But, I would say now a real challenge would be to bring new guys in the top 4. (see above) $\endgroup$
    – René Gy
    Mar 10, 2014 at 19:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .