fantastic problem

solution pls

Take $l>\log_2d$ and consider a prime factor $p$ of $2^{2^l}+d$ such that $p\not\equiv1\pmod{2^l}$. Such a $p$ must exist, or $2^{2^l}+d\equiv1\pmod{2^l}\implies 2^l\mid d-1$, a contradiction as $1<d<2^l$. Now, let $p-1=2^ab$ for some odd $b$ and $a<l$ and set $k=l+\text{ord}_b2$. We now have that $p-1\mid 2^k-2^l$ as it is divisible by both $2^a$ and $b$, so $p\mid 2^{2^k}-2^{2^l}$ and $p\mid 2^{2^k}+d$. Now it suffices to show that there are arbitrarily large primes that divide a number of the form $2^{2^n}+d$, as by the above argument we may take such a large prime greater than $m$ that divides $2^{2^N}+d$ for some $N>l$. This is a well-known Iran TST problem, and you can see here: https://artofproblemsolving.com/community/c6h275813p1492629 for the proof.

You can prove this method: Prove that 2^(2^l)+d have infinity primes as its divisors when l goes to infinity

Just Kobayashi's theorem.

Unless I am mistaken, it seems that all of the proofs above only prove that there are infinitely many primes dividing the terms. However, there can be infinitely many primes dividing the terms, just each prime divides at most one term. So, it is possible that there are only finitely many primes $\not\equiv 1 \pmod { 2^l}$, in which case ABCDE's solution falls apart at the end? I am sorry if I misunderstood your proofs, and please correct me if I am wrong, since I could this infinite prime case the hardest part of this problem.

ABCDE wrote: $2^{2^l}+d\equiv1\pmod{2^l}\implies 2^l\mid d-1$ Obviously this part is wrong if $2\mid d$.

Let $S=\{ p \textrm { a prime } : p|2^{2^n}+d \textrm { for some n } \}$. $S$ is infinite. Assume that there is a positive integer $m$ such that $(2^{2^k}+d,2^{2^l}+d)< m$ for all pairs $(k,l)$ of distinct positive integers. Let $S_1=\{p\in S|p< m\}$ and $S_2=\{p\in S|p\geq m\}$. There is a positive integer $X$ such that $v_p(2^{2^n}+d)<X$ for all $n\in\mathbb{N}$ and $p\in S_1$, otherwise there is a prime in $S_1$ with a very large power that divides two distinct terms of $2^{2^n}+d$. Any prime divisor of $S_2$ divide $2^{2^n}+d$ for exactly one $n$. Let $p\in S_2$ a divisor of $2^{2^n}+d$. Note that the congruence $2^k\equiv 2^n\pmod{p-1}$ has infinitely many solution $k>n$ if $2^{n+1}\not|p-1$. Therefore by our assumption we must have $p\equiv 1\pmod{2^{n+1}}$. Take $n$ very large so that $2^{n+1}>d+\left(\prod_{q\in S_1}q\right)^X$. Let $\alpha_q$ be the largest power of $q$ that divide $2^{2^n}+d$. By our previous observation $d\equiv \prod_{q\in S_1} q^{\alpha_q}\pmod {2^{n+1}}$ from which we find $d=\prod_{q\in S_1}q^{\alpha_q}$, since $d>1$, there is a $q\in S_1$ such that $\alpha_q>0$. but then $q|2$. Therefore $d=2^t$, where $t\in\mathbb{N}$. Write $t=2^uv$ for some odd $v$. It is not hard to prove that the sequence $2^{l-u}-v$ has infinitely many primes dividing at least one of its terms. Let $r>m$ be a prime that divides a term, say $2^{l-u}-v$, with large $l$. Let $k=l+r-1$. Then $2^ur|(2^l-t,2^k-t)$. Therefore $2^{2^ur}+1|(2^{2^l-t}+1,2^{2^k-t}+1)|(2^{2^m}+2^t,2^{2^k}+2^t)$, but clearly $2^{2^ur}+1>r>m$. Contradiction !

Lemma 1: the set of prime divisors of $n^k+c$ is infinite.

Lemma 2: if $a>1$ then $\text{gcd}(a^m+1,a^n+1)=a^{\text{gcd}(m,n)}+1$ for odd $m,n$. Consider a large enough integer $l$ then if we can find a prime $p$ such that: $$v_2(p-1)\leq l\ ,\ p>m\ ,\ p\mid 2^{2^l}+d\ \clubsuit$$then: $$2^{l}\stackrel{p-1}{\equiv}2^{l+\phi(p-1)}\Longrightarrow 2^{2^{l}}\stackrel{p}{\equiv}2^{2^{l+\phi(p-1)}}\Longrightarrow 2^{2^{l}}+d\stackrel{p}{\equiv}2^{2^{l+\phi(p-1)}}+d\Longrightarrow \text{gcd}(2^{2^{l}}+d,2^{2^{l+\phi(p-1)}}+d)\geq p>m$$So assume that there isn't any prime with these conditions ($\clubsuit$). hence for any sufficiently large integers $l$ the prime factorization of $2^{2^l}+d$ is in the following form: $$2^{2^{l}}+d=p_1^{a_1}p_2^{a_2}\dots p_k^{a_k}(2^{l+1}s_1+1)^{\beta_1}(2^{l+1}s_2+1)^{\beta_2} \dots (2^{l+1}s_t+1)^{\beta_t}$$where $p_1,p_2,\dots ,p_k<m$. Assume $M=p_1^{a_1+1}p_2^{a_2+1}\dots p_k^{a_k+1}$. Since $l$ is sufficiently large for any $s$: $$2^{l+\phi(\phi(M))s}\stackrel{\phi(M)}{\equiv}2^{l}\Longrightarrow 2^{2^{l+\phi(\phi(M))s}}\stackrel{M}{\equiv}2^{2^{l}}\Longrightarrow 2^{2^{l+\phi(\phi(M))s}}+d\stackrel{M}{\equiv}2^{2^{l}}+d\stackrel{M}{\equiv} p_1^{a_1}p_2^{a_2}\dots p_k^{a_k}(2^{l+1}s_1+1)^{\beta_1}(2^{l+1}s_2+1)^{\beta_2} \dots (2^{l+1}s_t+1)^{\beta_t}$$Hence for any $1\leq i\leq k$ we have: $$v_{p_i}(2^{2^{l+\phi(\phi(M))s}}+d)=a_i$$So we conclude that: $$2^{2^{l+\phi(\phi(M))s}}+d=p_1^{a_1}p_2^{a_2}\dots p_k^{a_k}(2^{l+\phi(\phi(M))s+1}u_1+1)^{c_1}(2^{l+\phi(\phi(M))s+1}u_2+1)^{c_2} \dots (2^{l+\phi(\phi(M))s+1}u_r+1)^{c_r}$$now observe that: $$d\stackrel{2^{l+\phi(\phi(M))s+1}}{\equiv}2^{2^{l+\phi(\phi(M))s}}+d\stackrel{2^{l+\phi(\phi(M))s+1}}{\equiv}p_1^{a_1}p_2^{a_2}\dots p_k^{a_k}\Longrightarrow 2^{l+\phi(\phi(M))s+1}\mid d-p_1^{a_1}p_2^{a_2}\dots p_k^{a_k}$$Hence: $$d=p_1^{a_1}p_2^{a_2}\dots p_k^{a_k}$$then for any $i$ such that $a_i\geq 1$ we have: $\left.\begin{array}{ccc} p_i\mid d\\ \\ p_i\mid 2^{2^l}+d=p_1^{a_1}p_2^{a_2}\dots p_k^{a_k}(2^{l+1}s_1+1)^{\beta_1}(2^{l+1}s_2+1)^{\beta_2} \dots (2^{l+1}s_t+1)^{\beta_t} \end{array}\right\}\Longrightarrow p_i\mid 2^{2^{l}}\Longrightarrow p_i=2$ Hence $d=2^s$ ($t\geq 1$). hence for any $m$ we have: $$2^{2^m-s}+1=(2^{m+1}s_1+1)^{j_1}\dots (2^{m+1}s_u+1)^{j_w}$$ take a prime $p\mid 2^{2^m-s}+1$. observe that from lemma there is a large number $q$ and $m$ such that: $\left.\begin{array}{ccc} q\mid 2^m-s\\ \\ q\mid 2^{m+(q-1)h}-s \end{array}\right\}\stackrel{(2)}{\Longrightarrow} 2^{2^{v_2(s)}q}+1\mid 2^{2^m-s}+1,2^{2^{v_2(s)}q}+1\mid 2^{2^{m+(q-1)h}-s}+1\Longrightarrow \text{gcd}(2^{2^m}+2^s,2^{2^{m+(q-1)h}}+2^s)\geq 2^{2^{v_2(s)}q}+1>m$ (since $q$ is large enough). Q.E.D

Just to note that Lemma 1 above is a straight consequence of Kobayashi's theorem.

WizardMath wrote: Just to note that Lemma 1 above is a straight consequence of Kobayashi's theorem. What's Kobayashi's theorem, please? Can't find it on the Internet.

$\text{Kobayashi's Theorem}$ Consider a sequence $\{a_n\}_{n\in\mathbb{N}}$ which has only finitely many primes dividing atleast one of its terms. Then the sequence $\{a_n+c\}_{n\in\mathbb{N}}\forall c\in\mathbb{Z}$ has infinitely many primes dividing atleast one of its terms.

babu2001 wrote: $\text{Kobayashi's Theorem}$ Consider a sequence $\{a_n\}_{n\in\mathbb{N}}$ which has only finitely many primes dividing atleast one of its terms. Then the sequence $\{a_n+c\}_{n\in\mathbb{N}}\forall c\in\mathbb{Z}$ has infinitely many primes dividing atleast one of its terms. Thank you. But $c$ can't be zero.

Let $a_n=2^{2^n}+d$. Suppose there exist $m$ and $d$ such that $(a_k,a_l)\leq m$ for all $k$ and $l$. It follows that if $p^t$ divides $a_k$ and $a_l$ for some positive integers $t$, $k$ and $l$, then $p^t<m$. In other words, $\nu_p(a_k)$ is bounded. Lemma 1: If positive integers $n$ and $k$ satisfy $\nu_2(k)<n$, then $k|2^l-2^n$ for some $l>n$. Proof: Let $k=2^a b$, where $b$ is odd. We have $a<n$. There exists $m$ such that $b|2^m-1$. Then $$2^ab|2^{n+m}-2^n=2^n(2^m-1)$$ Lemma 2: If $p|a_n$ for some prime $p>m$ and integral $n$, then $p\equiv 1\pmod{2^n}$. Proof: Suppose $2^n$ does not divide $p-1$. Then it follows from lemma 1 that $p-1$ divides $2^l-2^n$ for some $l>n$. Then $$a_l-a_n=2^{2^l}-2^{2^n}=2^{2^n}(2^{2^l-2^n}-1)$$The quantity $2^{2^l-2^n}-1$ is divisible by $p$ because $2^l-2^n$ is divisible by $p-1$. Then $p\leq (a_n,a_l)\leq m$, contradiction. Lemma 3: $d$ is a power of $2$ Proof: For each $n$ we write $a_n=2^{k_n}b_nc_n$, where $b_n$ contains only odd prime divisors of $a_n$ that are less than $m$ and $c_n$ contains those that are not less than $m$. It follows from Lemma 2 that $c_n\equiv 1\pmod{2^n}$, therefore $a_n\equiv d\equiv 2^{k_n}b_n\pmod{2^n}$. The number of primes less than $m$ is finite and for each of them the sequence $\nu_p(a_n)$ is bounded. Moreover, $k_n=\nu_2(d)$ when $n>\nu_2(d)$. This means there exists $M$ such that $2^{k_n}b_n<M$ for every integer $n$, that is, $2^{k_n}b_n=d$ for sufficiently large $n$. Thus $d$ divides $a_n=2^{2^n}+d$ for sufficiently large $n$, which means $d$ is a power of $2$. Lemma 4: For large enough $n$, there exists $l>n$ such that $a_n|a_l$. Proof: Let $d=2^k$. Choose $n>\nu_2(k)$. Then $\nu_2(2^n-k)=\nu_2(k)$. It follows from Lemma 1 that there exists $l$ such that $2^n-k|2^l-2^n$ and therefore $2^n-k|2^l-k$. Since $\nu_2(2^l-k)=\nu_2(k)=\nu_2(2^n-k)$, the number $\frac{2^l-k}{2^n-k}$ is odd, and thus $2^{2^n-k}+1$ divides $2^{2^l-k}+1$. Multiplying by $2^k$, we get that $a_n|a_l$. It follows from Lemma 4 that $a_n=(a_n,a_l)\leq m$ for each $n>\nu_2(k)$, a contradiction.

ACGNmath wrote: Lemma 2: If $p|a_n$ for some prime $p>m$ and integral $n$, then $p\equiv 1\pmod{2^n}$. Proof: Suppose $2^n$ does not divide $p-1$. Then it follows from lemma 1 that $p-1$ divides $2^l-2^n$ for some $l>n$. Then $$a_l-a_n=2^{2^l}-2^{2^n}=2^{2^n}(2^{2^l-2^n}-1)$$The quantity $2^{2^l-2^n}-1$ is divisible by $p$ because $2^l-2^n$ is divisible by $p-1$. Then $p\leq (a_n,a_l)\leq m$, contradiction. $p|2^{2^l-2^n}-1$ does not imply $p|2^{2^n}+d, 2^{2^l}+d$. How did you get contradiction?