# Infinitely many common prime divisors

By Zsigmondy's theorem, there are infinitely many prime divisors of $$2^{2^n}-1$$. That is, the set $$A=\{p \text{ is a prime}: p\mid 2^{2^n}-1 \text{ for some }n\in\Bbb{N}\}$$ is infinite.

Also, as shown here Primes dividing a polynomial, for any given $$f(x)\in\Bbb{Z}[x]$$, $$B_{f}=\{p \text{ is a prime}: p\mid f(n) \text{ for some }n\in\Bbb{N}\}$$is also infinite.

Can we show that $$A\cap B_{f}$$ is also an infinite set?

Update: For two different polynomials, the common prime divisor set is indeed infinite, I found this result here. ($$B_{f}\cap B_{g}$$ is a infinite set for any $$f,g$$) However, I cannot find any result concerning expression like $$2^{2^n}-1$$.

Update2: Maybe it's easier to consider $$A'=\{p \text{ is a prime}: p\mid 2^{n}+1 \text{ for some }n\in\Bbb{N}\}$$ and $$A'\cap B_{f}$$?

• I don't understand how Zsigmondy's theorem applies to your set $A$. Commented Jul 2, 2020 at 4:01
• @tristan For any $n$, we get a new prime divisor $p$ by Zsigmondy's theorem. $p\nmid 2^j-1$ for all $j<2^n$. Commented Jul 2, 2020 at 4:08
• You can see that $$2^{2^n}-1=\prod_{j=0}^{n-1}F_j$$ where $F_j=2^{2^j}+1$ is the $j^{th}$ Fermat number. It is well known that all prime factors of $F_j$ is of the form $2^{j+1}k+1$ for some natural number $k$. Would it help proceed?
– ShBh
Commented Jul 2, 2020 at 4:19
• @ShubhrajitBhattacharya I can't see that helps. Commented Jul 2, 2020 at 6:03
• @Peter Yes. I can’t find any counterexample for $f$. Commented Jul 2, 2020 at 8:10

Question 1: Presumably the answer is yes, the intersection should be infinite, but one won't be able to prove this.

There is really very little control one has over the factors of Fermat numbers besides being $$2$$-adically close to $$1$$, which is no restriction on the condition of being factors of a polynomial. On the other hand, it's highly implausible but still an open question whether all the Fermat numbers $$F_n = 2^{2^n} + 1$$ are prime for large enough $$n$$. But they are certainly all $$2 \bmod 3$$, so if they were all eventually prime then $$f(x) = x^2 + 3$$ (whose factors are all $$1 \bmod 3$$) would not be divisible by any of those Fermat primes, and so have only finitely many prime factors in common (like $$6700417$$).

Question 2: Yes, the intersection is infinite and even has positive density among all primes.

To say that there exists an $$n$$ such that

$$2^n \equiv -1 \bmod p$$

is to say that the multiplicative order of $$2$$ modulo $$p$$ is even (if the order is $$2m$$ then take $$n = m$$). Let $$f(x)$$ be any polynomial, and let $$K/\mathbf{Q}$$ be the splitting field. For all but finitely many $$m$$, the degree

$$[K(\zeta_{2^{m}},\sqrt[2^m]{2}):K(\zeta_{2^{m}})] > 1.$$

For such $$m$$, The Cebotarev density theorem implies the existence of a $$p$$ (even a positive density of primes $$p$$) such that Frobenius at $$p$$ in $$\mathrm{Gal}(K(\zeta_{2^{m}},\sqrt[2^m]{2})/\mathbf{Q})$$ is non-trivial in $$\mathrm{Gal}(K(\zeta_{2^{m}},\sqrt[2^m]{2})/K(\zeta_{2^{m}})$$. Quite directly, this implies that:

1. The polynomial $$f(x)$$ splits completely modulo $$p$$, so $$p$$ is certainly a factor of $$f(n)$$ for some $$n$$.

2. $$p \equiv 1 \bmod 2^m$$

3. $$2$$ is not a $$2^m$$th power modulo $$p$$.

Since the group $$\mathbf{F}^{\times}_p$$ is cyclic of order divisible by $$2^m$$ by ($$2$$), the condition ($$3$$) implies that $$2$$ has even order, and so one has the desired prime.

The simplest example is $$m=1$$, i.e. when the splittin field $$K$$ of $$f(x)$$ does not contain $$\mathbf{Q}(\sqrt{2})$$. Then $$f(n)$$ is divisible by many primes $$p$$ for which $$2$$ is not a quadratic residue modulo $$p$$, and for such $$p$$ we have

$$2^{(p-1)/2} + 1 \equiv 0 \mod p.$$