Let $m,n$ be two positive integers and $2^{2n+1}-1\, | \, 2^{2m+1}-1$. Suppose $P_0$ be the largest prime number such that $P_0 \, | \, 2^{2m+1}-1$. If $P_0 \, | \, 2^{2n+1}-1$ then is the following equation true? $$2^{2n+1}-1 = 2^{2m+1}-1$$
$\begingroup$
$\endgroup$
5
-
$\begingroup$ Not necessarily. Of course a consequence is that 2n+1 divides 2m+1. It could happen that N is a Mersenne prime and that the larger number is N(N^2 +3N+3) and has N as its largest prime factor. A look through the Cunningham tables should find a small counterexample if there are any. Gerhard "Perhaps A Very Small Counterexample" Paseman, 2017.01.03. $\endgroup$– Gerhard PasemanCommented Jan 3, 2017 at 21:10
-
$\begingroup$ There aren't that many Mersenne primes. But there should be a positive probability that $2^p-1$ has a prime factor $> 2^{cp}$ for say $c = .8$, and also a positive and independent probability that $2^{3p}-1$ has no larger prime factor. So there should be a positive albeit small density of counterexamples among exponents $3p$. Likewise for $5p$, $7p$, etc. though rapidly decreasing. $\endgroup$– Noam D. ElkiesCommented Jan 3, 2017 at 21:14
-
$\begingroup$ ($p$ being a large prime.) $\endgroup$– Noam D. ElkiesCommented Jan 3, 2017 at 21:20
-
$\begingroup$ Fortunately you found an example involving a Mersenne prime and posted it just before I posted my comment. It would be nice to know if similar examples existed using other bases. Or even which N have N^4 + 5(N^3 + 2N^2 + 2N +1) break into 4 or more times as many prime factors as N has. Gerhard "Cell Phones Are Much Slower" Paseman, 2017.01.03. $\endgroup$– Gerhard PasemanCommented Jan 3, 2017 at 21:23
-
$\begingroup$ Yes, that's what I'm guessing, based on the fact that for each $\epsilon>0$ random $x$ has all prime factors are less than $x^\epsilon$ with positive probability, but also has a prime factor greater than $x^{1-\epsilon}$ with positive probability. But the first probability decays rapidly enough ($\exp$ of something like $\log(\epsilon) / \epsilon$) that the first example with $2^p-1 \mid 2^{5p}-1$ might be quite large. $\endgroup$– Noam D. ElkiesCommented Jan 3, 2017 at 21:41
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
No. $(2n+1,2m+1) = (17,51)$ is a counterexample because $$ 2^{51} - 1 = 7 \cdot 103 \cdot 2143 \cdot 11119 \cdot 131071 $$ and $131071 = 2^{17}-1$ is prime. The only other counterexample with $m \leq 100$ is $(2n+1,2m+1) = (37,111)$ with $P_0 = (2^{37}-1)/223 = 616318177$.
P.S. gp code:
forstep(k=3,200,2,if(!isprime(k),f=factor(2^k-1)[,1]; r = znorder(Mod(2,f[#f])); if(r<k, print([r,k]))))
P.P.S. The condition $2^{2n+1} - 1 \mid 2^{2m+1} - 1$ is equivalent to $2n+1 \mid 2m+1$.
answered Jan 3, 2017 at 21:03
-
1
-
1$\begingroup$ I was a minute too slow, I've just found this example :P $\endgroup$– WojowuCommented Jan 3, 2017 at 21:03
-
$\begingroup$ The equivalent condition is inherited from cyclotomic polynomials. $\endgroup$ Commented Jan 3, 2017 at 21:51
-
$\begingroup$ No need for cyclotomic polynomials. In general, for any integers $b,s>1$ and $r,r'\geq 0$ we have $r \equiv r' \bmod s \Rightarrow b^r - 1 \equiv b^{r'} - 1 \bmod b^s - 1$ (using $b^s \equiv 1$). If $r'$ is the least nonnegative residue of $r \bmod s$, then $b^{r'} - 1 < b^s - 1$, so $b^r-1$ is a multiple of $b^s-1$ iff $r$ is a multiple of $s$. $\endgroup$ Commented Jan 3, 2017 at 22:21
-
1$\begingroup$ Curiously, the pair $(17,51)$ is also a counterexample to a related problem: the largest prime factor of $2^{51}+1$ divides $2^{17}+1$. This is not the case for $(37,111)$. $\endgroup$ Commented Jan 5, 2017 at 20:32