Actually proposed by me, Sam first test solver.

I got this after submitting. It's something to do with the fact that if $p\mid 2^{2^n}+a$ then $p\mid 2^{2^m}+a$ where $m=n+\text{ord}_2 (\frac{p-1}{2^{v_2 (p-1)}})$.

EDIT: Ok I will write out the complete solution.

@^ That doesn't work when $a\equiv 1\pmod 2$, since then you have $2^{m-n}$ (even number) is congruent to $1$ mod $2^{2^n}+a-1$, which is even.

He probably meant $2^m\equiv 2^n$ in that mod.

Ignore this.

gurev wrote: Actually proposed by me, Sam first test solver. Sorry, fixed. That's what I get for trying to write down the authors from memory.

Suppose that for every nonnegative integer $n$, the number $2^{2^n}+a$ is always a prime. If $a$ is even then $2|2^{2^n}+a$, which is not a prime, a contradiction. If $a$ is odd, let $p_i=2^{2^i}+a$ with $p_i>2$ is a prime. We will prove that there exists number $m>i$ such that $p_i|2^{2^m}+a$ or $p_i|2^{2^m}-2^{2^i}$ or $p_i|2^{2^i(2^{m-i}-1)}-1$. Let $\text{ord}_{p_i}(2)=r$ then $r|2^i(2^{m-i}-1)$. Denote $r=p_1^{k_1}p_2^{k_2} \cdots p_x^{k_x} \cdot 2^y$. with $p_1,p_2, \cdots p_x \ge 3$ are prime numbers. Pick $i= v_2(r)=y$ and $m-i=(p_1-1)p_1^{k_1-1}(p_2-1)p_2^{k_2-1} \cdots (p_x-1)p_x^{k_x-1}$. Using LTE lemma and Fermat's little theorem, we can see that $v_p(r) \le v_p(2^i(2^{m-i}-1)$ for every prime $p|r$. This means there exists positive integer number $m>i$ such that $p_i|2^{2^m}+a$. This follows $p_i=2^{2^m}+a=2^{2^i}+a$. Hence, $m=i$, a contradiction. Thus, for some nonnegative integer $n$, the number $2^{2^n}+a$ is not prime.

this is an old problem

dothef1 wrote: If $a$ is even , $2$ divides $2^{2^n}+a$ . if $a$ is odd, chose $n= \phi (a+2)$ , since then $2^n\equiv 1 [a+2]$ implying $2^{2^n} \equiv 2 [a+2] $, but since $2 \equiv -a [a+2] $, we are done . Why is $2^n\equiv 1 [a+2]$ implying $2^{2^n} \equiv 2 [a+2]$ true? Shouldn't it be $2^n \equiv 1 [\phi (a+2)]$ implies $2^{2^n} \equiv 2 [a+2]$?

andria wrote: gurev wrote: Actually proposed by me, Sam first test solver. it isn't your problem you have copied this problem from the book 250 Problems in Elementary Number Theory - Sierpinski (1970) see problem 115 of page 10 It is extremely rude to accuse other users of intentional plagiarism. Why is it not possible that Gurev invented the problem independently?

Darn. Went to this problem after solving problems 1 and 2. Then I ran out of time on this problem.

somepersonoverhere wrote: Darn. Went to this problem after solving problems 1 and 2. Then I ran out of time on this problem. The same as you. In that time, the only thing I can think of in order to solve this is Fermat numbers. I tried to apply Fermat numbers' properties into this problem, but it's not working.

Here is solution Assume problem is false and so we get $ 2^{2^n}+a = p $ a prime, for some $n$ bigger than $ v_2(a-1)+1$. Notice that $v_2(p-1) = v_2(a-1) < n$, and so $2^{2^{n}}$ can be expressed as $x^{2^{m}}$ mod $p$ for any $m$. It is also a well-known fact that $-1$ can be expressed as $x^{2^{m}}$ mod $p$ for $m \le v_2(p-1)-1$. Therefore, $a = -2^{2^{n}}$ can be expressed as $x^{2^{m}}$ mod $p$ for $m \le v_2(p-1)-1$, and so $a^{\text{odd}} = -1$ mod $p$, for wise choice of $\text{odd}$. In particular, we can clearly make that odd of the form $2^x-1$ (by multiplying it by another odd number), for $x>1$. So we have $a^{2^x-1} = -1$ mod $p$. This implies $a^{2^x} = -a$ mod $p$, so $(-2^{2^n})^{2^x} = -a$, so $2^{2^{n+x}} = -a$ since $x>1$. Thus if $m=n+x > n$ we have $2^{2^m} +a =0$ mod $p$ and so $2^{2^m}+a$ is not prime. In fact, this proves that $\mathcal{O}(1)$% of those numbers are composite. Q.E.D

What's the purpose of the restriction $a>1$? $a=1$ is true by considering $a=5$.

Could you do induction on this?

Probably not, as there is no plausible way to go from $2^{2^x}+a$ to $2^{2^y}+a+1$, especially when it's not easy (if possible at all) to find a relationship between $x$ and $y$ in this case.

shiningsunnyday wrote: What's the purpose of the restriction $a>1$? $a=1$ is true by considering $a=5$. $a=1$ does not warrant a number theoretic approach, as there is no easy way to determine the primality of any Fermat number, so counterexamples must be found by hand.

Suppose $2^{2^n} + a$ is prime for all $n$. Note that $a$ must be odd. Also note that $2^{2^{2^n}+a-1} \equiv 1 \pmod{2^{2^n}+a}$. Choose a $n > v_2(a-1)$. Note that $v_2(2^{2^n}+a-1) = v_2(a-1)$. Choose a $k$ such that $2^k - 1$ is a multiple of the largest odd factor of $2^{2^n}+a$. (For all odd $m$, there exists such a $k$; for example, $2^{\phi (m)} \equiv 1 \pmod{m}$.) Then, $2^{2^n} + a-1$ divides $2^n(2^k-1)$. Then, note that $2^{n+k} \equiv 2^n \pmod{2^{2^n}+a-1}$. Thus, $2^{2^{n+k}} \equiv 2^{2^n} \pmod{2^{2^n}+a} \implies 2^{2^{n+k}}+a \equiv 2^{2^n}+a \equiv 0 \pmod{2^{2^n}+a}$. Contradiction.

This problem was good. I am not good at orders modulo $n$. Further, I knew that this had something to do with Fermat Numbers but I didn't remember any properties of Fermat Numbers!!

My solution was a sort of variation on the official solution and all other solution posted in this forum...........

v_Enhance wrote: andria wrote: gurev wrote: Actually proposed by me, Sam first test solver. it isn't your problem you have copied this problem from the book 250 Problems in Elementary Number Theory - Sierpinski (1970) see problem 115 of page 10 It is extremely rude to accuse other users of intentional plagiarism. Why is it not possible that Gurev invented the problem independently? I agree.....criticizing before knowing the truth.......is just irritating.......

@sunny Originally I included $a=1$ but we made the switch because this case has to be handled separately and is basically a test of whether you know about $641$. @andria It's unfortunate that I wasn't the first person to think of the problem, and if any of the test creators had known of this we wouldn't have included it. However I don't think any of the real elmo takers had seen it before, and with such strict conditions for a good olympiad number theory problem it is unsurprising that coincidences like this happen.

gurev wrote: @sunny Originally I included $a=1$ but we made the switch because this case has to be handled separately and is basically a test of whether you know about $641$. Yeah.....ELMO is test of talent, not the test of knowledge.....

Which of the worlds idiots is down voting almost every post? Try to be sensible. Friends Evan Chen and Viswanath have got a down vote in every post though they speak right.

I seemed to be in the minority in that I found this problem easier than the other number theory problem, #1. It took me a lot longer to think of the simultaneous induction, but there seems to be a pretty clear path to the solution for this problem.

zacchro wrote: I seemed to be in the minority in that I found this problem easier than the other number theory problem, #1. It took me a lot longer to think of the simultaneous induction, but there seems to be a pretty clear path to the solution for this problem. Actually, I solved this problem before P1 also

AnonymousBunny wrote:

Well,I think you chose $2^{2^{n}}+a$ to be a prime.

I'm not sure what that's supposed to mean...

Hold on... Say $n=2$ and $a=3$. Wouldn't that get 19 which is prime?

You have to prove that for all $a$, there exists some $n$ for which that thing isn't a prime.

Seems like time changes lots of things... About less than 10 months ago this very problem took me about 60-90minutes which today took me less than 3. A very nice problem by the way! (It's really hard to see good NT these days...) My solution (Today's) We assume that the sequence takes prime values for all sufficiently large $n$. (This way, we shall be able to prove that In fact infinitely many terms of this sequence are composite!) Now, fix a large positive integer $n>>>9000v_2(a-1)$. Let us fix the prime number $p=2^{2^n}+a$. Now, we let $l$ be the largest odd number which divides $p-1$. Then, we set $m \equiv n \bmod \phi(l)$ Therefore, $2^{m-n} \equiv 1 \bmod l$ and since $n>v_2(a-1)=v_2(p-1)$ we have that $p-1 \mid 2^m-2^n$. Therefore, $p\mid 2^{2^m-2^n}-1$ and so, $p \mid (2^{2^m}+a)-p$ which means that since $p<<2^{2^m}+a$ and $p$ divides it, that $2^{2^m}+a$ is composite giving the desired contradiction. Remark:- Since $v_2(0)=\infty$ this won't work for Fermat Numbers

See also here for one more property of that sequence http://artofproblemsolving.com/community/c6h275813p1492629

silouan wrote: See also here http://artofproblemsolving.com/community/c6h275813p1492629 silouan, I don't see why these two problems are similar. The other one uses Kobayashi's theorem, whereas this uses some elementary argument about primes and orders.

We can assume that a is odd and take $n$ such $\phi(\phi(a+2))|n$. $\phi$ is Eulers totient function.

Let $a > 1$ be a positive integer. Prove that for some nonnegative integer $n$, the number $2^{2^{2^n}}+a$ is not prime.

If a is even then $2<2^{2^1}+a$ is divisible 2. So assume that a is odd. Let $\upsilon_2(a-1)=k$ since $a\neq1$. If $2^{2^k}+a$ is a composite then we are done. So assume that it is a prime. Then $\upsilon_2(2^{2^k}+a-1) =k$ because $2^{2^k}>2^k$. Then $2^{2^k}+a-1\mid2^{k+\varphi(\bigg(\frac{2^{2^k}+a-1}{2^k}\bigg)}-1=2^l-1\mid2^{l+k}-2^k$ for some $l>0$. Then by fermat's little theorem $2^{2^k}+a\mid2^{2^{2^k}+a-1}-1\mid2^{2^{l+k}-2^k}-1\mid2^{2^{l+k}}-2^{2^k}$. Therefore $2^{2^k}+a\mid2^{2^{l+k}}+a$. So substitute $n=k+l$ and we are done.

Solved with mfang92, niyu, and nukelauncher. Assume for contradiction otherwise. Take $p=2^{2^n}+a$ where $n\gg e:=\nu_2(a-1)$. I claim that $p\mid2^{2^m}+a$, where \[m:=n+\varphi\left(\frac{p-1}{2^e}\right).\]By Euler's theorem, $2^m\equiv2^n\pmod{(p-1)/2^e}$, and furthermore since $2^m\equiv2^n\equiv0\pmod{2^e}$, we have $2^m\equiv2^n\pmod{p-1}$ by Chinese Remainder theorem. Hence $2^{2^m}\equiv2^{2^n}\equiv-a\pmod p$ by Fermat's little theorem, so $p\mid2^{2^m}+a$. But $2^{2^m}+a$ is prime and greater than $p$, absurd. Remark: This also proves there are infinitely many $n$ such that $2^{2^n}+a$ is not prime. Otherwise take $n\gg e$ such that $2^{2^k}+1$ is prime for all $k\ge n$.

Sps $ p | 2^{2^{n}} + a $ , if we can construct a $m$ such that $ p | 2^{2^{m}} + a $ , then we will get desired contradiction.. Construction : If $$m \equiv n mod ( ord_{\frac{ord_{p}2}{2^{(v_{2}(ord_{p}2)}}} 2)$$works.