Find all prime numbers p such that $2^p+p^2 $ is also a prime number.
Problem
Source: Albanian IMO 2011 TST
Tags: modular arithmetic, number theory, number theory unsolved
27.05.2011 10:10
ridgers wrote: Problem 4 : Find all prime numbers p such that $2^p+p^2 $ is also a prime number. $p=2$ is not a solution $p=3$ is a solution $p>3$ implies $p^2\equiv 1\pmod 3$ and $2^p\equiv -1\pmod 3$ and so $2^p+p^2\equiv 0\pmod 3$ and since $2^p+p^2>3$, it's not prime. Hence the unique solution $\boxed{p=3}$
27.05.2011 16:29
$p$ is clearly odd. For $p=3$ we have a solution. Otherwise, using Fermat's Little Theorem, $2^{p-1} \equiv 1 \pmod 3$ or $2^{p}\equiv 2 \pmod 3$. Also $p^2 \equiv 1 \pmod 3$, hence $2^p +p^2 $ is divisible by $3$. Therefore $p=3$ is the only solution. Edit: You don't get $2^p \equiv 2 \pmod 3$ using Fermat's Little Theorem.
27.05.2011 18:45
enndb0x wrote: using Fermat's Little Theorem, $2^{p-1} \equiv 1 \pmod 3$ How did you use FLT there?
27.05.2011 22:46
He didn't - just had a blindspot, writing instead of the correct, but useless $2^{p-1} \equiv 1 \pmod p$ or $2^{p}\equiv 2 \pmod p$ the relations $\pmod 3$.
06.06.2011 09:29
mavropnevma wrote: He didn't - just had a blindspot, writing instead of the correct, but useless $2^{p-1} \equiv 1 \pmod p$ or $2^{p}\equiv 2 \pmod p$ the relations $\pmod 3$. $2^2 \equiv_3 1$ and $p-1=2.l$ then $2^{p-1}\equiv_3 1$ In here we coundnt use FLT .
06.06.2011 09:40
Precisely. For $p$ odd, one has $2^{p-1} = 4^{(p-1)/2} = (3+1)^{(p-1)/2} \equiv 1 \pmod{3}$, without any use of Fermat's little theorem. Using Fermat's little theorem to get $2^2 = 2^{3-1} \equiv 1 \pmod{3}$, and then the fact that for odd $p$ we have $2 \mid p-1$, therefore also $2^{p-1} \equiv 1 \pmod{3}$, is a gross overkill (to say the least).
06.06.2011 12:25
Correct! $ 2^{2n+1}\equiv 2\mod{3} $!
12.06.2011 18:05
if $p>3=>3 | 2^p+p^2=>p\le3=>p=3$ is a sloution $p=2$ is not a solution!
02.06.2012 14:44
As previously mentioned, the case $p=2$ does not give solutions while $p=3$ does. For $p>3$ we must have $p \equiv \pm 1 \pmod 3\implies p^2 \equiv 1 \pmod 3$, and since $p$ is odd $2^p \equiv -1 \pmod 3$, that is $3$ divides $2^p+p^2$. Anyone can prove that $\{ p \in \mathbb P : \exists n : p|2^n+n^2\}$ is infinite? (I didn't think too much to the solution, but I have already seen some similar problems so I suppose it's feasible.)
02.06.2012 17:20
The set $\{ p \in \mathbb P \ ; \ \exists n : p \mid 2^n+n^2\}$ is infinite, since it contains all primes $p\equiv 1\pmod{4}$. Indeed, take $k$ such that $k^2 \equiv -1 \pmod{p}$, and $n = k(p-1)$. On one hand $2^n = (2^{p-1})^k \equiv 1 \pmod{p}$, and on the other hand $n^2 = k^2(p^2-2p+1) \equiv k^2 \equiv -1 \pmod{p}$, so $2^n + n^2 \equiv 0 \pmod{p}$.
20.02.2014 19:28
Really too easy for a TST; since you revived the topic then , If $p>3$ observe, $2^p+p^2=\underbrace{(2^p+1)}+\underbrace{(p^2-1)}$ Where those two underlined term is divisible by $3$...
27.03.2016 23:51
So easy for TST
28.03.2016 19:22
This problem is equal to "Find all prime numbers $p,q$ such that $p^q+q^p$ is also a prime number."
21.05.2018 07:20
toluene wrote: This problem is equal to "Find all prime numbers $p,q$ such that $p^q+q^p$ is also a prime number." But this is even tougher
21.05.2018 07:21
I solved it using congruent modulo
02.02.2021 18:14
$2^p+p^2\equiv 2+1\mod 3$ so $p\in\{3,2\}$ As $p\neq 2$ hence $p=3$ toluene wrote: This problem is equal to "Find all prime numbers $p,q$ such that $p^q+q^p$ is also a prime number." For this clearly $2|p^q+q^p$ now if $p^q+q^p=2$ which clearly is not possible. So one of $p, q$ is even. Then $q=2$ so question becomes equivalent to $2^p+p^2=P$ where $P$ is prime which has only solution at $p=3$$\blacksquare$
02.02.2021 18:25
Am I the only one who thinks this is quite easy for a TST problem? This is the first TST problem I've ever solved.
02.02.2021 18:28
toluene wrote: This problem is equal to "Find all prime numbers $p,q$ such that $p^q+q^p$ is also a prime number." This also isn't that hard.
02.02.2021 20:48
Yeah, that is very easy. As solutions above, consider $p=2,3$, separately. Now, let $p>3$, thus $p=6k\pm 1$ for some $k\in\mathbb N$. Assume there is such $p=6k\pm 1$ for some $k\in\mathbb N$, so that $2^p+p^2=q\in\mathbb P$, i.e. $$2^{6k\pm 1}+(6k\pm 1)^2=q=6l\pm 1$$for some $l\in\mathbb N$. Taking modulo $6$, we get $$2^{6k\pm 1}\equiv \pm 1-1\pmod 6$$ If $2^{6k+ 1}\equiv +1-1\equiv 0\pmod 6$, then clear contradiction, since $2^{6k+ 1}\not\equiv 0\pmod 3$. If $2^{6k-1}\equiv -1-1\equiv 4\pmod 6$, then this simplifies to $4^{k}\equiv 2\pmod 6$, but notice that this does not hold for any $k\in\mathbb N$, since $4^{k}\equiv 4\pmod 6$ for all $k\in\mathbb N$.
12.09.2021 16:17
First, $p=2$ is not a solution since $2^2+2^2=4+4=8$ is not prime. $p=3$ is a solution since $2^3+3^2=8+9=17$ is prime. For all primes, greater than $3$, they are either $1$ or $2$ mod $3$, which means that $p^2\equiv 1\;(\text{mod}\;3)$. Since all primes greater than $3$ are odd, we also have that $2^p\equiv 2\;(\text{mod}\;3)$. Therefore, for all primes greater than $3$, $$2^p+p^2 \equiv 2+1\equiv 0\;(\text{mod}\;3)$$This is never a prime since no primes greater than $3$ are divisible by $3$. Therefore, the only solution is $\boxed{p=3}$.
19.09.2021 17:38
We claim that the only prime that works is $p = 3$. It is easy to see that $p = 2$ does not work. Now assume that $p > 3$. This means that $2^p \equiv 2 \pmod{3}$ and that $p^2 \equiv 1 \pmod{3}$. Adding the two yields $2^p+p^2 \equiv 0 \pmod{3}$, contradiction. Too easy.
23.09.2021 04:55
Suppose $p>3$. Then $2^p\equiv2\pmod3$ as $p$ is odd. We also have $p^2\equiv1\pmod3$. So $2^p+p^2\equiv0\pmod3$, so it is not a prime number as it is greater than $3$. $\boxed{p=3}$ is a solution. $p=2$ is not a solution.
05.09.2023 03:07
If, $p>3$, then $2^p\equiv 2\pmod{3}$, since $p,$ is odd. Now, also $p^2 \equiv 0\pmod{3}$, so the sum is 0 mod 3. but this can not be a prime number. Testing, $p=\boxed{3}$, is the only solution.
21.10.2023 14:53
If $p$ is odd then $2^p\equiv 2\pmod{3}$ and if $p$ is not a multiple of $3$ then $p^2\equiv 1\pmod{3}$. So $3\mid 2^p+p^2$ if $p>4$. $p=2$ gives $8$ which would not work, $p=3$ gives $17$ which works. So the only answer is $3$.
22.10.2023 04:11
It is easy to see that $p=2$ is not a solution and $p=3$ is a solution (the required expression is then 17 which is clearly prime). Now, if $p>3$, then it is odd and not divisible by $3$. Thus, \[2^p+p^2 \equiv 2 + 1 \equiv 0 \pmod{3}\]Thus, it is divisible by 3. Since $2^p+p^2>2^3+3^2=17>3$, this means that this expression is clearly not a prime for all primes $p\geq 5$. Thus, the only solution is $\boxed{p=3}$.