khashi70 wrote: Let $ a$ be a fix natural number . Prove that the set of prime divisors of $ 2^{2^{n}} + a$ for $ n = 1,2,\cdots$ is infinite $ x_n=2^{2^n}+a$ We denote $ S$ be the set of primes p such that exist an positive integer M which for all $ n\geq M$ then $ p|x_n$ .We will so that $ S$ is a finite set . This result may be easy because $ \gcd(x+a,x^2+a)$ is a divisor of $ a(a+1)$ , which means that if $ p\in S$ then $ p|a(a+1)$ . Other hand ,by the condition $ p|x_n$ we have $ p=2$ or $ p$ is divisor of $ a+1$ . Lemma 1 :Consider $ k$ is a positive greater than $ v_2(a)$ then $ x_k$ is not a power of 2 .For each pair of natural numbers $ (m,n)$ such that $ n\geq v_2(\varphi(x_k))$ and $ m\equiv n (\mod \varphi(x_k))$we have $ x_m\equiv x_n (\mod x_k)$ . Proof : Let $ x_k=2^{v}.u$ ,by the condition we have $ n\geq (v+\varphi(u)-1)$ and $ m\equiv n (\mod \varphi(x_k))$ . We have \[ x_m-x_n=2^{2^n}(2^{2^m-2^n}-1) \] By Euler's theorem we have $ \varphi(u)|2^m-2^n$ therefore $ u|2^{2^m-2^n}-1$. Other hand $ 2^n\geq v$ so $ x_k|x_m-x_n$ . Lemma 2 :Let $ n,t$ be fixed positive integers,$ t$ is even , consider sequence $ y_k=2^{2^{n+kt}}+a$ then exist a positive integer $ k$ such that $ y_k$ have a prime divisor not in $ S$ . Let $ a+1=2^{u}.v$ .We will show that exist an integer $ k$ which satisfy \[ y_k\equiv a+1 (\mod v^2) \] This can be done by similar trick above , hence we can write :$ y_k=2^uv+t.v^2=v(2^u+tv)$ which have a prime divisor not divide $ v$ and different from 2 . Lemma 2 has been prove . Now let consider our problem . Take $ a$ number in the sequence ,which has a prime divisor not in S , by the definition of $ S$ exist a numbers $ (m,n)$ satisfy lemma 1 and then by lemma 2 ,exist $ m$ such that it has a different prime divisor ,and not in S ... So on ,we can construct a infinite set of prime numbers

Assume that this set be finite i.e there exist $ p_{1}, p_{2}, \cdots p_{k}$ which they are all the prime divisor of $ 2^{2^{n}} + a$ now consider these numbers : $ a^{2} + a$, $ a^{4} + a$ , $ \cdots a^{2^{k}} + a$ and assume $ r$ is a number such that none of this number is divisible by $ p_{i}^{r}$ for all $ i = 1,2,\cdots,k$ now we know if $ n$ be sufficient big then if factorize $ 2^{2^{n}} + a$ by $ p_{1}, p_{2}, \cdots p_{k}$ one of this prime number has a power bigger than $ r$ . so if we consider $ k + 1$ consecutive number $ n$ which are sufficient big then by Pigeonhole theorem there exist two of this number which one of these prime number (for example) $ p_{1}$ has a power bigger than $ r$ in both which means : $ p_{1}^{r}|2^{2^{u}} + a$ $ p_{1}^{r}|2^{2^{u + s}} + a$ ( $ 1\leq s \leq k$ ) Thus $ p_{1}^{r}|a^{2^{s}} + a$ which is contradiction ... So the problem is solved .

But ... where do we know that there exists such $ r$ from? Even there is something more incomprehensible - if $ a=2$, then $ a^{2^k}+a$ and $ 2^{2^k}+a$ will coincide and since there exists big enough $ n$ such that $ p_i^r|2^{2^n}+a$, then $ p_i^r|a^{2^n}+a$

but $ k$ is a fix number and each of $ a^{2}+a$ , $ a^{4}+a$ , $ \cdots$ , ${ a^{2^{k}}+a}$ has a factorization by prime numbers ... so we can choose this $ r$ .

oh , yes... I thought you take an infinite set $ a^{2^k}+a$.

I have two questions regarding your solution and I hope you will explain it to me 1. why can't s=k+1 2. how do you get the last statement I thought that a is given and fix so how did you deduce that $ p_{1}^{r}|2^{2^{u}} + a$ $ p_{1}^{r}|2^{2^{u + s}} + a ( 1\leq s \leq k )$ Thus $ p_{1}^{r}|a^{2^{s}} + a$ I'm sorry I just can't get it.

1-Our $ k + 1$ consecutive numbers are $ u$, $ u + 1$, $ \cdots ,u + k$ 2-$ p_{1}^{r}|a^{2^{u}} + a$ and $ a^{2^{u + s}} = (a^{2^{u}})^{s}$ so : $ a^{2^{u + s}}\equiv ( - a)^{2^{s}}$ (mod $ p_{1}^{r}$) I hope u get ur answers .

Thank you very much very nice solution.

A very useful $ \textsc{Kobayashi}$ Theorem. If the positive integer sequence $ (a_n)_{n\geq 1}$ is not bounded, and has a finite set of prime divisors, then the translated sequence $ (a_n + a)_{n\geq 1}$ has an infinite set of prime divisors, for any not-null integer $ a$. I have a short proof of this, using $ \textsc{Thue}$'s Theorem that the Diophantine equation $ Ax^3 + By^3 = C$ has finitely many integer solutions. Now, it's an overkill, since $ (2^{2^n})_{n\geq 1}$ has only $ 2$ as prime divisor.

Dear mavropnevma Can you show us your nice proof of this Kobayashi Theorem? Thanks in advance.

@mavropnevma: have you got any references to Kobayashi's theroem?

No reference, sorry (I found about it in some note in the Monthly, but can't remember where...). As for the proof, I gave enough hints, I think (look it over again, it's not difficult ).

mavropnevma wrote: A very useful $ \textsc{Kobayashi}$ Theorem. If the positive integer sequence $ (a_n)_{n\geq 1}$ is not bounded, and has a finite set of prime divisors, then the translated sequence $ (a_n + a)_{n\geq 1}$ has an infinite set of prime divisors, for any not-null integer $ a$. Here is a reference to Kobayashi's paper: Kobayashi, Hiroshi On existence of infinitely many prime divisors in a given set. Tokyo J. Math. 4 (1981), no. 2, 379-380. However, this is far above Olympiad level.

here is my solution. is it correct?? suppose that the set of prime divisors of this sequence is finite, namely $\{p_1,...,p_k\}$. let $n_1$ be a natural number such that $n_1>v_2((p_1-1)(p_2-1)....(p_k-1)a)$. suppose that ${v_{p_i}(2^{2^{n_1}}}+a)=\alpha_i$. we want to prove there exists $n_2$ and $t$ such that $2^{n_1}+t\phi(p_1^{\alpha_1+1})\phi(p_2^{\alpha_2+1})....\phi(p_k^{\alpha_k+1})=2^{n_2}$ (I) or in other words $p_1^{\alpha_1}.....p_k^{\alpha_k}(p_1-1).....(p_k-1)|2^{n_1}(2^{n_2-n_1}-1)$. note that because of the choice of $n_1$, the exponent of $2$ on the right hand side is more than the one in the left hand side, so we can omit them. now the left hand side is equal to an odd number $m$, and there exists a number $s$ such that $2^s\equiv 1$ $(mod$ $m)$. now let $n_2=n_1+s$, so such $n_2$ exists that (I) holds. now back into the main problem, we get that for each $i$, we have $v_{p_i}(2^{2^{n_2}}+a)=v_{p_i}(2^{2^{n_1}}+a)$, but $2^{2^{n_2}}+a>2^{2^{n_1}}+a$, a contradiction. so the set of prime divisors of the sequence is infinite.

mavropnevma wrote: A very useful using $ \textsc{Thue}$'s Theorem that the Diophantine equation $ Ax^3 + By^3 = C$ has finitely many integer solutions. Someone can post reference to THUE 's Theorem on Diophante Equation ?? Thanks!

Let $\{x_n\}=\{2^{2^n}+a\}$ , first suppose $a$ is odd. Now let set of prime divisors of $\{x_n\}$ is finite. Now consider the sub sequences $\{a_i\}$ for finite number of $i's$. Now construct those such as in each of $\{a_i\}$ set of prime divisors of all element is same. Now certainly size at least one of those $\{a_i\}$ must be infinite. Consider the $\{a_k\}$ , contains maximum number of prime divisors and infinitely many terms. Now so maximum power of at least one of the prime dividing terms of $\{a_k\}$ must not be bounded. Now suppose ${\{a_k}\}=\{a'_1,a'_2,a'_3,......\}$. Now suppose we’ve like $v_p(x_m),v_p(x_n)\alpha>3$ then it’s easy to see $v_p(|m-n|)\geq (\alpha-2)$. Now suppose in the sequence $\{a_k\}$ a very large number is $n$ which is nothing but maximum power of a prime $p$ dividing terms of $\{a_k\}$ and whose power is unbounded. Now suppose $v_p(a_i)=n$ and first term greater than $a_i$ is $a_m$ such as $v_p(a_m)\geq n$. Now as we took $n$ to be a very large number so the gap between $m$ and $i$ must be greater than $p^{n-2}$ and that is also very large. Now by our assumption in that large gap, powers of $p's$ is less than $n$. So there must be always another prime with unbounded power, if not then there would enter some terms of another sequences other than $\{a_k\}$. Then so again we would get another sub sequence of infinite length. And similarly going on we would get all of the sub sequences are of infinite length because of large $n$, it’s not difficult show infinitely many $x_n$ can’t be power of a prime. Now so lets back to case where in $\{a_k\}$ there are at least two primes with unbounded power, now basically similarly we get all prime dividing terms of $\{a_k\}$ are unbounded. Now just consider two consecutive very large terms of $\{a_k\}$ and notice similarly we’ll get another sub sequence with infinite length. So going on as previous we’re getting contradiction, now if $a$ would be even then similarly we would do, and so we’re now done to show $\{x_n\}$ contains infinitely many prime divisors.

The solution may be pre-posted but still I am reposting. Let primes dividing $f(n)$ as $n$ varies over all the positive integers be $p_1,p_2,....,p_k$. Then let $M=\sum_{i=1}^{k}v_2(p_i-1)$. And let $f(M)=\prod_{i=1}^{k}p_i^{a_i}$. Now we show that there exists a $k$ such that $n=\prod_{i=1}^kp_i^{a_i+1}$ and $n|f(M+k)-f(M)$ where $f(n)=2^{2^n}+a$. Clearly, $f(x+y)-f(x)=2^{2^x}(2^{2^x(2^y-1)}-1).$ $\forall$ $x$ and $y$ Now put $x=M$ and $y=\phi(\prod_{i=1}^{k}p_i^{a_i}r_i)$ where $p_i-1=2^{v_2(p_i-1)}r_i $ We now claim that $\phi(n)|2^M(2^y-1)$. Clearly $\phi(n)=\prod_{i=1}^{k}p_i^{a_i}(p_i-1)$.Now $M=\sum_{i=1}^kv_2(p_i-1)=v_2(2^{M}(2^y-1))=v_2(\phi(n))$. Now $y=\phi(\prod_{i=1}^{k}p_i^{a_i}r_i)=\phi(\frac{\phi(n)}{\prod_{i=1}^k2^{v_2(p_i-1)}})$ and hence $\frac{\phi(n)}{\prod_{i=1}^k(2^v_2(p_i-1)}|2^y-1$. This indicates $\phi(n)|2^M(2^y-1).$ Now we know that $f(M+y)-f(M)=2^{2^m}(2^{2^M(2^y-1)}-1)$ and hence $n|f(M+y)-f(M)$. Now take any of the primes $p_i$. If $v_{p_i}(f(M))<v_{p_i}(f(M+y))$ then contradiction arises because then $ v_{p_i}(f(M+y)-f(M))=v_{p_i}(f(M)) < v_{p_i}(n)$. Similarly the other case may also be contradicted. So only case is that $v_{p_i}(f(M))=v_{p_i}(f(M+y))$.Now this happens for all odd primes $p_i$. Notice that it indicates that the odd parts of both $f(M+y)$ and $f(M)$ are equal and hence it indicates that $f(M+y)=2^{l_1}f(M)$ for some.Now this indicates after some easy analysis that $v_2(a)=2^M+l_1$ Notice that we can once again carry on the same arguement this time $M$ replaced by $M+y$.In that case we have to suitably choose a number $s$ in place of $y$ which will depend on the exponents of the primes in $f(M+y)$.We will again get $f(M+y+s)=2^{l_2}f(M+y)$ and thus $v_2(a)=2^{M+y}+l_2$. We can continue the process continously then we notice that $l_i$ is a strictly decreasing sequence.Again as all the $l_i$s ar positive integers so eventually we will get one $t$ such that $l_t=0$.And hence we will get two $x,y$ with $x \neq y$ such that $f(x)=f(y)$ which is clearly a contradiction.

consider the sequence $a_{n}=2^{2^n} $ . Its an unbounded sequence and each term has only 1 prime divisor , viz , $2$ . hence , by Kobayashi's theorem , we get that the set of prime divisors of $(2^{2^n}+a)$,$ n=1,2,3 , .....$ is infinite (as $a>0$ )

FelixD wrote: @mavropnevma: have you got any references to Kobayashi's theroem? See this, it should help you. http://leonettipaolo.wordpress.com/2013/01/20/kobayashi-theorem/ And the original paper is attached too.

Insta-kill by Kobayashi's Theorem but let's be a bit more modest. For $a=1$ we know that Fermat numbers are pairwise coprime, so we are done and we are free to assume $a>1$. Suppose this set is finite and the set of all primes dividing at least one term of this sequence is $P=\{p_1,\dots,p_k\}$. Write each term as $p_1^{e_1}\cdot \dots \cdot p_k^{e_k}$ and choose the index $1 \le i \le k$ such that $p_i^{e_i}$ is maximal. Since we are assigning to each term one out of $k$ indices, we have by the Pigeon-hole Principle, $x_n=2^{2^n}+a$ and $x_m=2^{2^m}+a$ assigned the same index $i$ for some $n+k \ge m>n>N$ where $N>0$ is a sufficiently large constant. Now, let us observe that \begin{align*} p_i^{a_i}= p_i^{v_{p_i}(\gcd(x_m,x_n))} \ge \min (\sqrt[k]{x_n},\sqrt[k]{x_m})=O(\exp(\exp(n))) \end{align*}however, we have \begin{align*} p_i^{a_i} \mid 2^{2^n}\cdot ((2^{2^n})^{2^{m-n}-1}-1) \end{align*}yielding that \begin{align*} 1 \equiv ((2^{2^n})^{2^{m-n}-1} \equiv (-a)^{2^{m-n}-1} \bmod p_i^{a_i} \end{align*}and we see that $p_i^{a_i} \le |(-a)^{2^{m-n}-1}-1|=O(1)$ since $m-n$ is bounded above by $k$. This is a contradiction and the result follows from our deduction.

Kobayashi's theorem kills it since $a_n=2^{2^{n}}$ is not bounded and $2^{2^{n}}$ has only $2$ as prime divisor.

khashi70 wrote: Assume that this set be finite i.e there exist $ p_{1}, p_{2}, \cdots p_{k}$ which they are all the prime divisor of $ 2^{2^{n}} + a$ now consider these numbers : $ a^{2} + a$, $ a^{4} + a$ , $ \cdots a^{2^{k}} + a$ and assume $ r$ is a number such that none of this number is divisible by $ p_{i}^{r}$ for all $ i = 1,2,\cdots,k$ now we know if $ n$ be sufficient big then if factorize $ 2^{2^{n}} + a$ by $ p_{1}, p_{2}, \cdots p_{k}$ one of this prime number has a power bigger than $ r$ . so if we consider $ k + 1$ consecutive number $ n$ which are sufficient big then by Pigeonhole theorem there exist two of this number which one of these prime number (for example) $ p_{1}$ has a power bigger than $ r$ in both which means : $ p_{1}^{r}|2^{2^{u}} + a$ $ p_{1}^{r}|2^{2^{u + s}} + a$ ( $ 1\leq s \leq k$ ) Thus $ p_{1}^{r}|a^{2^{s}} + a$ which is contradiction ... So the problem is solved . NAILED DAT PROB

mavropnevma wrote: $ \textsc{Kobayashi}$ Theorem. If the positive integer sequence $ (a_n)_{n\geq 1}$ is not bounded, and has a finite set of prime divisors, then the translated sequence $ (a_n + a)_{n\geq 1}$ has an infinite set of prime divisors, for any not-null integer $ a$. I have a short proof of this, using $ \textsc{Thue}$'s Theorem that the Diophantine equation $ Ax^3 + By^3 = C$ has finitely many integer solutions. . To use Thue's Theorem you must have irreducibility of $f(x,y)=Ax^3 + By^3$. So what are your conditions for $A,B$ since for $A=B\neq 0$ this polynomial is reducible: $f(x,y)=A(x+y)(x^2-xy+y^2)$

Also https://artofproblemsolving.com/community/q1h2078594p14934435

fukano_2 wrote: The only prime that divides powers of two is two. So by Kobayashi, adding $a$ will give infinitely many primes I would really like to see a one-liner for Kobayashi

SenatorPauline wrote: I would really like to see a one-liner for Kobayashi $A=\left \{2 ^{2^n}: n \in \mathbb{N} \right \}$ has finite prime divisors, so $A'=\left \{2 ^{2^n}+a: n \in \mathbb{N} \right \}$ doesn't by Kobayashi's.

Iran TST 2009 P2. Show that \[\forall a\in\mathbb{N}: \not\exists k\in\mathbb{N}: k=\left|\{p\in\mathbb{P}: \exists n\in\mathbb{N}: p\mid 2^{2^n}+a\}\right|.\] Solution 1. Assume on the contrary that \[\exists a\in\mathbb{N}: \exists k\in\mathbb{N}: k=\left|\{p\in\mathbb{P}: \exists n\in\mathbb{N}: p\mid 2^{2^n}+a\}\right|.\]And assume that \[\{p\in\mathbb{P}: \exists n\in\mathbb{N}: p\mid 2^{2^n}+a\}=\{p_1,\dots,p_k\}.\]Choose \[r=\max_{1\le i\le k}\left\{\left\lfloor \log_{p_i}{(a^{2^k}+a)}\right\rfloor+1\right\}\]such that \[\forall i\in\{1,\dots,k\}: p_i^r>a^{2^k}+a.\]Choose \[n=\left\lfloor\log_2{\left(\log_2{\left(\prod_{i=1}^k p_i^r-a\right)}\right)}\right\rfloor+1\]such that \[2^{2^n}+a>\prod_{i=1}^k p_i^r.\]Then \[\forall m\ge n: \prod_{i=1}^k p_i^{\nu_{p_i}(2^{2^m}+a)}=2^{2^m}+a>\prod_{i=1}^k p_i^r.\]This means that \[\forall m\ge n:\exists i\in\{1,\dots,k\}:\nu_{p_i}(2^{2^m}+a)>r.\]Now by PP for some $j\in\{1,\dots,k\}$ \[\exists n+s>n+t\in\{n,n+1,\dots,n+k\}: \nu_{p_j}(2^{2^{n+s}}+a),\nu_{p_j}(2^{2^{n+t}}+a)>r.\]Accordingly \[-a\equiv 2^{2^{n+s}}=(2^{2^{n+t}})^{2^{s-t}}\equiv (-a)^{2^{s-t}}\equiv a^{2^{s-t}}\pmod {p_j^r},\]which means \[p_j^r\mid a^{2^{s-t}}+a\le a^{2^k}+a,\]contradicting the prior assumption that \[\forall i\in\{1,\dots,k\}: p_i^r>a^{2^k}+a,\]which establishes our proof. Solution 2. Since \[1=\left|\{p\in\mathbb{P}: \exists n\in\mathbb{N}: p\mid 2^{2^n}\}\right|,\]the result follows from Kobayashi's Theorem.

this kobayashi

Trivial by Kobayashi.

The set of prime divisors of $2^{2^n}$ is infinite (since $\{2^n\mid n=1,2,\ldots\}$ is a subset of this). By Kobayashi's Theorem the result follows.

kobayashi theorem is OK. https://zhuanlan.zhihu.com/p/112458972

Kobayashi's Theorem

The infinite set $S$ that contains all natural numbers of the form $2^{2^n}$ is divisible only by the prime $2$, so by Kobayashi's theorem, the set $S_1$ that contains all numbers of the form $2^{2^n}+a$ is divisible by infinitely many primes, giving the desired result.

$2^{2^n}$ has a finite set of prime divisors, so we may use Kobayashi's (sledgehammer )