Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
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
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 '11 at 22:39
2  
Drat, I was kind of hoping Joe would know the answer to this one. –  JSE Jul 14 '11 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 '11 at 23:18
show 2 more comments

3 Answers 3

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

share|improve this answer
    
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
add comment

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
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 '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
show 11 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.