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

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

2011-07-14T20:42:09Z

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.

Answer by Gerry Myerson for Greatest common divisor of a^{2^n}-1 and b^{2^n}-1

2011-07-15T00:31:42Z

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.

Answer by jp for Greatest common divisor of a^{2^n}-1 and b^{2^n}-1

2011-07-15T10:51:30Z

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

Answer by Anonymous for Greatest common divisor of a^{2^n}-1 and b^{2^n}-1

2011-07-17T01:45:47Z

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