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