Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let be number $2^n+n^2$ prime and $n\geq 2$.

Proof that number $(n-3)$ is disivible by 6.

share|cite|improve this question
Could you provide some information about which contest this is from? – Tobias Kildetoft Jan 23 '13 at 15:02
It's from a book named "Mathematic for contest and olymiad" from Kosovo – user123451241 Jan 23 '13 at 15:04
Equivalently, $n$ is an odd multiple of $3$. – Matemáticos Chibchas Jan 23 '13 at 15:09
up vote 2 down vote accepted

Since $n\geq 2$ it is clear that $2^n+n^2$ cannot be 2. Therefore, $2^n+n^2$ is an odd prime. As such, $n$ cannot be even, for if it were, then $n^2+2^n$ would be even. Therefore $n$ is odd. If $n$ is odd then $2^n$ is 2 modulo 6. If $n^2+2^n$ is a prime then it is either 1 or 5 modulo 6. This means $n^2$ should be either 5 or 3 modulo 6. Since no square can be 5 modulo 6, the only choice you have is if it is 3 modulo 6. This happens only if $3|n$ but 6 does not. Therefore $6|n-3$.

share|cite|improve this answer

Any integer $n$ could be written in the form $n=6m+k$ where $n,k$ are integers and $0 \leq k \leq 5$.

If $k=0,2,4$ Then $n$ is an even number and then $2^n+n^2$ is also an even number greater than 2, rendering it not a prime.

In the case $k=1,5$ we have $2^n+n^2$ divisible by $3$, so we are left with the only possibility that $n=6m+3$, which is what we wanted to prove.

share|cite|improve this answer

Here are some hints:

Note that to show that $n-3$ is divisible by $6$, we just need to show that $n$ is odd (since then $n-3$ is even and thus divisible by $2$) and divisible by $3$ (since a number $m$ is divisible by $3$ iff $m-3$ is divisible by $3$).

Note that if $n$ is even, then you immediately get a non-trivial factor of the number.

To see that $n$ must be divisible by $3$, reduce the number mod $3$ and see that unless $n$ is divisible by $3$, this is $0$. Conclude...

share|cite|improve this answer

It is the special case $\rm\:p = 3\:$ of the following.

Theorem $\ $ If $\rm\ p < q = (p\!-\!1)^n\! + n^{p-1}$ are odd primes then $\rm\ 2,p\mid n\!-\!p,\ $ so $\rm\ 2p\mid n\!-\!p$

Proof $\ $ Note $\rm\, 2\mid n\!-\!p\,$ since $\rm\, n\,$ is odd (else $\rm\,2\mid n\Rightarrow 2\mid q).\,$ Also $\rm\,p\mid n\!-\!p,\,$ since $\rm\,p\mid n\,$ (else $\rm\,p\nmid n\,$ hence by $\rm\color{#C00}{little\ Fermat}$, $\rm\,{\rm mod}\ p\!:\ (p\!-\!1)^n\! \color{#C00}{ + n^{p-1}}\equiv (-1)^n \color{#C00}{+ 1} \equiv 0,\,$ so $\rm\,p\mid q,\,$ contra hypothesis).

share|cite|improve this answer

As found in other answers, $n$ must be odd.

Now if $3\mid(2^n+n^2)\iff3\mid(n^2-1)$ as $2^n\equiv(-1)^n\pmod 3\equiv -1$ as $n$ is odd.

and $3\mid(n^2-1)\implies n^2\equiv1\pmod3\implies n\equiv\pm1\pmod 3$

So, if $3\not\mid n,3\mid(2^n+n^2),$ the later is $>3$ as $n\ge2$

So, if $2^n+n^2$ is prime, $3\mid n$

(1)$\implies n\equiv3\pmod 6$ as $n\not\equiv0\pmod 6$ as $n$ is odd.

(2)Alternatively, as $3\mid n,n=3r$ and as $n$ is odd $n=2s+1$ for some integers $r,s$

So, $3r=2s+1\implies 3(r-1)=2(s-1)\iff \frac{2(s-1)}3=r-1$ is an integer.

So, $3\mid(s-1)$ as $(2,3)=1\implies s=3t+1$ for some integer $t$

So, $n=2s+1=2(3t+1)+1=6t+3$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.