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

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.

-
Add some hypothesis ($a,b$ multiplicatively independent?) to avoid cases like $b=a^2$. – Felipe Voloch Jul 14 '11 at 20:55
Also have a look at some recent papers of Corvaja and Zannier. – Felipe Voloch Jul 14 '11 at 20:58
@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 '11 at 22:39
Drat, I was kind of hoping Joe would know the answer to this one. – JSE Jul 14 '11 at 22:43
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 '11 at 23:18

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

-
Boiling this line of thought down even further: we expect (do we?) that there are infinitely many primes of the form $p=3\cdot 2^n+1$, and the "random element" heuristic above predicts that $1/9$ of these primes will eventually divide both $a^{2^n}-1$ and $b^{2^n}-1$; this already gives infinitely many primes dividing these gcds. – Greg Martin Jul 22 '11 at 22:47

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

-
Well, I guess I've actually made things too hard here, since $\gcd(a^n-1, b^n-1) \mid \gcd(a^{n^2}-1, b^{n^2}-1)$; hence the support problem is trivial, again by Fermat's little theorem. I'll leave my answer up for now though. – so-called friend Don Jul 17 '11 at 2:04
Good point, I guess that was as silly question. – Joe Silverman Jul 17 '11 at 2:46

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.

-
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 '11 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 '11 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 '11 at 2:43
@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 '11 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 '11 at 10:50