Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

share|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 –  arber Jan 23 '13 at 15:04
2  
Equivalently, $n$ is an odd multiple of $3$. –  Matemáticos Chibchas Jan 23 '13 at 15:09
add comment

5 Answers

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|improve this answer
add comment

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|improve this answer
add comment

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|improve this answer
add comment

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.