Proof that a certain number is disivible by 6

Question

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

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

Answer 1

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$.

Answer 2

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.

Answer 3

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...

Answer 4

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).

Answer 5

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$