Welcome to MathOverflow

Question

11

3

Let a and b be coprime integers. Do we know, expect, or unexpect that there are infinitely many primes p which divide

$gcd(a^{2^n} - 1, b^{2^n}-1)$

for some n? Certainly any Fermat prime will divide both if I let n get large enough, but one doesn't know whether there are infinitely many of those.

edited Jul 14 2011 at 21:42

asked Jul 14 2011 at 20:42

JSE
13.4k●33●83

1

Add some hypothesis ($a,b$ multiplicatively independent?) to avoid cases like $b=a^2$. – Felipe Voloch Jul 14 2011 at 20:55

Also have a look at some recent papers of Corvaja and Zannier. – Felipe Voloch Jul 14 2011 at 20:58

2

@Felipe: If $b=a^2$, then the gcd is just $a^{2^n}-1$, so the problem becomes easier since Jordan is only asking about the support problem, i.e., the set of primes dividing at least one number in a sequence. And of course, in this easier case, Bang (before Zsigmondy) proved that all but finitely many terms in the sequence $a^N-1$ have a primitive prime divisor. So Support($a^{N_i}-1$) is infinite for any increasing sequence of integers $N_1,N_2,\dots$. – Joe Silverman Jul 14 2011 at 22:39

2

Drat, I was kind of hoping Joe would know the answer to this one. – JSE Jul 14 2011 at 22:43

1

Hah! My initial impression after thinking about it for a few minutes is that it looks very hard. Even $\gcd(a^n-1,b^n-1)$ is hard, e.g., not known it equals 1 infinitely often (assuming $a$ and $b$ mult. indep.). Of course, the support problem for $\gcd(a^n-1,b^n-1)$ is trivial by Fermat's little theorem. But $2^n$ is such a sparse sequence, I don't see where to begin. Here's a question: Is the support of $\gcd(a^{n^2}-1,b^{n^2}-1)$ infinite? Follows from "infinitely many primes of the form $n^2+1$", but do we have the tools to prove this unconditionally? – Joe Silverman Jul 14 2011 at 23:18

show 2 more comments

Gerry Myerson · Answer 1 · 2011-07-15 00:31:42Z UTC

1

Just to get a feeling for what's going on here, I asked Maple for $\gcd(2^{2^n}-1,3^{2^n}-1)$ for $n=1,2,\dots,20$ and got

1 for $n=1$,

5 for $n=2,3$,

$85=5\cdot17$ for $n=4,5,6,7$,

$21845=5\cdot17\cdot257$ for $n=8,\dots,15$,

$1431655765=5\cdot17\cdot257\cdot65537$ for $n=16$ to $n=19$, all pretty much as expected, then

$19515599812384085=5\cdot17\cdot257\cdot65537\cdot13631489$ for $n=20$.

The first few results are as expected from the question statement, as 5, 17, 257, and 65537 are Fermat primes. 13631489 is a factor of a Fermat number.

answered Jul 15 2011 at 0:31

Gerry Myerson
15.7k●1●47●87

Of course, each term is divisible by the previous term. A slightly harder, but maybe more natural, question, would be the set of primes dividing some term in the sequence $\gcd(2^{2^n}+1,3^{2^n}+1)$. More generally, some subsequence of $\gcd(\Phi_N(2),\Phi_N(3))$, where~$\Phi_N$ is the cyclotomic polynomial. In this case, we're taking $N=2^n$ for $n=1,2,3,...$. – Joe Silverman Jul 15 2011 at 0:59

It seems that $\gcd(2^{2^n}+1,3^{2^n}+1)$ is 5 for $n=1$ and 1 for $2\le n\le20$. – Gerry Myerson Jul 15 2011 at 1:12

@Gerry: Do you want to conjecture it's 1 for all $n\ge2$? Here's an amusing example. Consider the sequence $A_n=\gcd(2^n+3^n+1,2^n+7^n+2)$. I checked that $A_n=1$ for all $n\le5000$. Further, the support of the sequence $(A_n)$ contains no primes smaller than 5000. Challenge: Prove that $A_n=1$ for infinitely many $n$. I have no idea how to begin to attack this, nor the easier(?) case of a function field analogue over $\mathbb{C}[T]$. For $\mathbb{C}[T]$, Ailon and Rudnick prove (under suitable hypotheses) that $\gcd(a(T)^n-1,b(T)^n-1)=1$ for lots of $n$. – Joe Silverman Jul 15 2011 at 2:43

1

@Joe, I am far too timid to make a conjecture based on $2\le n\le20$. A bit closer to the ground, Ilan Vardi found $\gcd(n^7+19,(n+1)^7+19)=1$ for $n\lt8424432925592889329288197322308900672459420460792433$ but the equality fails for the next $n$. – Gerry Myerson Jul 15 2011 at 5:58

@Gerry $\gcd(2^{2^n}+1,3^{2^n}+1)=1$ for $2 \le n \le 29$. Took about 30 minutes with ntl (up to 28 took 15 minutes in sage). $\gcd(2^{2^n}-1,3^{2^n}-1)=19515599812384085$ for $20 \le n \le 29$. – joro Jul 15 2011 at 10:50

show 11 more comments

jp · Answer 2 · 2011-07-16 13:15:19Z UTC

One can rewrite your problem as follows:

For $p$ prime, $p\mid a^{2^n}-1$ for some $n$ is equivalent to $\mathrm{ord}_{\mathbb{F}_p^\times}(a)$ being a power of $2$.

The probability for a random element of the multiplicative group $\mathbb{F}_p^\times$ to have order a power of $2$ is $\frac{2^n}{p-1}$ where $n$ is chosen maximal among the natural numbers $m$ with $2^m \mid p-1$.

A naive (hopefully not too naive) heuristic for the expected number of primes dividing both $a^{2^n}-1$ and $b^{2^n}-1$ for some $n$ is $-$ assuming that both conditions are independent:

$$\sum_{n\in\mathbb N}\sum_{\mbox{$p\in\mathbb{P}$ : $n$ maximal w.r.t. $p = 1 \bmod 2^n$}} \left(\frac{2^n}{p-1}\right)^2 \approx \sum_{n\in\mathbb N} \sum_{q\in\mathbb N} \frac{1}{\log(q\cdot 2^n+1)\cdot q^2}$$

For the approximation the heuristics is used that the probability for a number $m$ to be prime is about $\frac{1}{\log m}$. As the latter sum diverges one would expect that infinitely many primes divide your greatest common divisor for some $n$.

Anonymous · Answer 3 · 2011-07-17 01:45:47Z UTC

A comment on one of Joe's questions: Let $B$ be any real number. It is known unconditionally that there are infinitely many $m$ for which $\phi(m)$ is a square and for which the smallest prime factor of $m$ exceeds $B$. One can even take $m$ as a product of two primes here; see, e.g., article 4 from

http://www.integers-ejcnt.org/vol11a.html

or an arXiv preprint of Tristan Freiberg.

If we choose $B$ larger than $|a|$ and $|b|$, then $m \mid \gcd(a^{\phi(m)}-1, b^{\phi(m)}-1)$, and so there is a prime $> B$ in the support of $\gcd(a^{n^2}-1, b^{n^2}-1)$.

Greatest common divisor of a^{2^n}-1 and b^{2^n}-1

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

3 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.