Let $ a$ be a fixed natural number. Prove that the set of prime divisors of $ 2^{2^{n}} + a$ for $ n = 1,2,\cdots$ is infinite

Question

$\textbf{Question:}$Let $ a$ be a fixed natural number. Prove that the set of prime divisors of $ 2^{2^{n}} + a$ for $ n = 1,2,\cdots$ is infinite.

I have come to know that this problem easily follows from "Kobayashi's theorem". But that probably won't give any points on a contest-math situation.

Apart from that, I think we would need to somehow use the idea behind the Euclid's proof of infinitude of primes. But it seems too tricky. I could hardly make any progress in this problem. So, any kind of hint or solution is appreciated. Thanks in advance.

Answer 1

Suppose with fixed number a we get a composite of the form $N=2^{2^n}+a$ which has some prime divisors. If we prove that these composites are infinitely many then we can conclude that the number of prime divisors of N for a fixed a is infinite(this is what the question is asking, if I understood it correctly).

I found this theorem in a number theory book by Sierpinski. The proof is by A. Schintzel.

Theorem: For every natural number $k ≠ 1$ there exists infinitely many natural numbers like n such that number $2^{2^n}+k$ is composite.

Proof:

Let a be an arbitrary natural number and k an integer unequal to unity.Take $k-1=2^s h$ where $2^s$ is the greatest power of $2$ which divides $k-1$ and h is an odd number which can be positive or negative. Take m such that $2^{2^m}>a-k$ and number t such that $t≥s$ and also $t≥m$. If $2^{2^t}+k≥2^{2^m}+k> a$ is composite, then we have a composite number in the form $2^{2^n}+k$ greater than a. So we assume $p=2^{2^t}+k$ is prime. Since $t≥s$ and $k-1=2^sh$, then we have:

$p-1=2^{2^t}+k-1=2^sh_1$

where $h_1$ is a positive odd number.Now due to Euler's theorem we have:

$2^{\phi(h_1)} ≡ 1 \ mod (h_1)$

Since $p-1=2^s h_1$, then:

$2^{s+\phi(h_1)}≡ 2^s \ mod (p-1)$

Since $t≥s$ , we get:

$2^{t+\phi(h_1)}≡ 2^t \ mod (p-1)$

Finally due to Fermat's little theorem we have:

$2^{2^{t+\phi(h_1)}}+k ≡ 2^{2^t}+k≡ 0 \ mod (p)$

Since $2^{t+\phi(h_1)}> 2^t$ then we may write:

$2^{2^{t+\phi(h_1)}}+k>2^{2^t}+k=p$

Hence number $2^{2^{t+\phi(h_1)}}+k$ will be a composite greater than a, because:

$p=2^{2^t}+k≥2^{2^m}+k > a$

The proof is done.