Let $a > 1$ be a positive integer. Prove that for some nonnegative integer $n$, the number $2^{2^n}+a$ is not prime. Proposed by Jack Gurev
Problem
Source: ELMO 2015, Problem 4 (Shorlist N4)
Tags: Elmo, number theory, primes
27.06.2015 04:39
Actually proposed by me, Sam first test solver.
27.06.2015 04:51
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)}})$.
27.06.2015 04:57
27.06.2015 05:00
EDIT: Ok I will write out the complete solution.
27.06.2015 05:27
@^ 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.
27.06.2015 05:32
He probably meant $2^m\equiv 2^n$ in that mod.
27.06.2015 05:48
Ignore this.
27.06.2015 06:52
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.
27.06.2015 07:48
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.
27.06.2015 15:48
this is an old problem
27.06.2015 16:13
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]$?
27.06.2015 17:01
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?
27.06.2015 17:24
Darn. Went to this problem after solving problems 1 and 2. Then I ran out of time on this problem.
28.06.2015 00:09
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.
28.06.2015 04:28
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
28.06.2015 04:41
What's the purpose of the restriction $a>1$? $a=1$ is true by considering $a=5$.
28.06.2015 04:42
Could you do induction on this?
28.06.2015 04:57
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.
28.06.2015 05:15
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.
28.06.2015 11:31
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.
28.06.2015 12:26
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!!
28.06.2015 15:27
My solution was a sort of variation on the official solution and all other solution posted in this forum...........
28.06.2015 15:28
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.......
28.06.2015 15:49
@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.
28.06.2015 18:25
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.....
29.06.2015 05:12
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.
29.06.2015 08:45
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.
30.06.2015 03:44
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
08.07.2015 22:08
AnonymousBunny wrote:
Well,I think you chose $2^{2^{n}}+a$ to be a prime.
10.07.2015 13:56
I'm not sure what that's supposed to mean...
14.07.2015 05:29
Hold on... Say $n=2$ and $a=3$. Wouldn't that get 19 which is prime?
14.07.2015 06:14
You have to prove that for all $a$, there exists some $n$ for which that thing isn't a prime.
19.04.2016 12:53
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
19.04.2016 13:56
See also here for one more property of that sequence http://artofproblemsolving.com/community/c6h275813p1492629
19.04.2016 14:57
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.
18.06.2016 19:24
18.06.2016 21:14
We can assume that a is odd and take $n$ such $\phi(\phi(a+2))|n$. $\phi$ is Eulers totient function.
23.06.2016 11:58
Let $a > 1$ be a positive integer. Prove that for some nonnegative integer $n$, the number $2^{2^{2^n}}+a$ is not prime.
13.06.2019 07:44
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.
17.03.2020 08:46
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$.
08.06.2021 07:14
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.