Prove n^2+2^n Composite if n not 6k+3

[Math100]

Homework Statement

If $n>1$ is an integer not of the form $6k+3$, prove that $n^{2}+2^{n}$ is composite.
[Hint: Show that either $2$ or $3$ divides $n^{2}+2^{n}$.

Relevant Equations

None.

Proof:

Suppose $n>1$ is an integer not of the form $6k+3$.
Then we have $n=6k$ for some $k\in\mathbb{Z}$.
Thus $n^{2}+2^{n}=(6k)^{2}+2^{6k}$
$=36k^{2}+2^{6k}$
$=2(18k^{2}+2^{6k-1})$
$=2m$,
where $m=18k^{2}+2^{6k-1}$ is an integer.
This means $2\mid n^{2}+2^{n}$,
which implies that $n^{2}+2^{n}$ is composite.
Therefore, if $n>1$ is an integer not of the form $6k+3$,
then $n^{2}+2^{n}$ is composite.

 

[fresh_42]

Homework Statement:: If $n>1$ is an integer not of the form $6k+3$, prove that $n^{2}+2^{n}$ is composite.
[Hint: Show that either $2$ or $3$ divides $n^{2}+2^{n}$.
Relevant Equations:: None.

Proof:

Suppose $n>1$ is an integer not of the form $6k+3$.
Then we have $n=6k$ for some $k\in\mathbb{Z}$.

No, we don't. We have $n=6k$ or $n=6k+1$ or $n=6k+2$ or $n=6k+4$ or $n=6k+5.$
Examples: $36\, , \,37\, , \,38\, , \,40\, , \,41$ and only $36$ is of the form $6k.$

Use the hint!

If $n$ is even, then $4\,|\,(n^2+2^n)$ since $n$ is at least $2.$ And $n^2+2^n> 4,$ hence it is composite. (Derive what I just said.)

If $n$ is odd, then ...

Thus $n^{2}+2^{n}=(6k)^{2}+2^{6k}$
$=36k^{2}+2^{6k}$
$=2(18k^{2}+2^{6k-1})$
$=2m$,
where $m=18k^{2}+2^{6k-1}$ is an integer.
This means $2\mid n^{2}+2^{n}$,
which implies that $n^{2}+2^{n}$ is composite.
Therefore, if $n>1$ is an integer not of the form $6k+3$,
then $n^{2}+2^{n}$ is composite.

 

[Math100]

For $n=6k, n=6k+2$ or $n=6k+4$, I know that $2\mid n^2+2^{n}$. But for $n=6k+1$ or $n=6k+5$, how should I show/prove that $3\mid n^2+2^{n}$? Because for $n=6k+1$ or $n=6k+5$, this is what I got so far:

Suppose $n=6k+1$ for some $k\in\mathbb{Z}$.
Then we have $n^{2}+2^{n}=(6k+1)^{2}+2^{6k+1}$
$=36k^2+12k+2^{6k+1}+1$

But I don't see the pattern of factor of 3, how should I factor out the 3 from here? Similarly, this is what I got for $n=6k+5$:

Suppose $n=6k+5$ for some $k\in\mathbb{Z}$.
Then we have $n^{2}+2^{n}=(6k+5)^{2}+2^{6k+5}$
$=36k^2+60k+2^{6k+5}+25$
Again, I don't see the pattern of factor of 3 either.

 

[fresh_42]

If $n$ is odd, then you have the two cases you began with. Since we are interested in the factor $3,$ it is natural to consider your equations modulo $3,$ i.e. divide by $3$ and concentrate on the remainders. E.g. $36k^2+60k+2^{6k+5}+25 \equiv 0\cdot k^2+0\cdot k + 32 \cdot 2^{6k}+1\equiv2\cdot 2^{6k}+1 \mod 3.$ Are those numbers divisible by $3,$ and why or why not?

 

[Math100]

If $n$ is odd, then you have the two cases you began with. Since we are interested in the factor $3,$ it is natural to consider your equations modulo $3,$ i.e. divide by $3$ and concentrate on the remainders. E.g. $36k^2+60k+2^{6k+5}+25 \equiv 0\cdot k^2+0\cdot k + 32 \cdot 2^{6k}+1\equiv2\cdot 2^{6k}+1 \mod 3.$ Are those numbers divisible by $3,$ and why or why not?

Yes, because obviously, $36$ and $60$ in front of $k^2$ and $k$ are divisible by $3$ also $2^{6k+5}=2\cdot 2^{6k}$, and $2\cdot 2^{6k}=2^{6k+1}$.

So this means $3\mid 2^{6k+1}+1$.

 

[fresh_42]

Why is it divisible by $3$? Odd alone only gives us odd +1 = even which might or might not be divisible by $3$. What is your argument?

 

[fresh_42]

The only place where we used $n\neq 6k+3$ was as we did not consider this case. Do you have an idea why your proof wouldn't work if $n=6k+3$? And what about your other equation?

 

[Math100]

Because $2\cdot 2^{6k}\equiv 2$ mod $3$.

 

[Math100]

The only place where we used $n\neq 6k+3$ was as we did not consider this case. Do you have an idea why your proof wouldn't work if $n=6k+3$? And what about your other equation?

Because for $n=6k+3$:
we have $n^2+2^{n}=36k^2+36k+2^{6k+3}+9\equiv 2$ mod $3$.

 

[fresh_42]

Because $2\cdot 2^{6k}\equiv 2$ mod $3$.

So? We have $2^{6k+5}\equiv 32\cdot 2^{6k}\equiv 2\cdot 2^{6k}\equiv 2^{6k+1}\equiv 2 \mod 3$ and $2^{6k+3}\equiv 8\cdot 2^{6k}\equiv 2 \mod 3$ too. Where is the difference?

 

[Math100]

So? We have $2^{6k+5}\equiv 32\cdot 2^{6k}\equiv 2\cdot 2^{6k}\equiv 2^{6k+1}\equiv 2 \mod 3$ and $2^{6k+3}\equiv 8\cdot 2^{6k}\equiv 2 \mod 3$ too. Where is the difference?

Are you talking about the difference between $n=6k+1$ or $n=6k+5$ and $n=6k+3$?

 

[fresh_42]

Yes. We did not really use the condition $n\neq 6k+3$ except that we omitted the case. But $2^\text{odd}=2^{2m+1}=2\cdot 4^m \equiv 2\cdot 1^m\equiv 2\mod 3$ is the same in all cases. Why do we need the condition $n\neq 6k+3$ at all?

 

[Math100]

For $n=6k+5$,
we have $36k^2+60k+2^{6k+5}+25\equiv 0\cdot k^2+0\cdot k+32\cdot 2^{6k}+1\equiv 2\cdot 2^{6k}+1\equiv 0$ mod $3$.
Thus, $3\mid n^{2}+2^{n}$.

 

[fresh_42]

For $n=6k+5$,
we have $36k^2+60k+2^{6k+5}+25\equiv 0\cdot k^2+0\cdot k+32\cdot 2^{6k}+1\equiv 2\cdot 2^{6k}+1\equiv 0$ mod $3$.
Thus, $3\mid n^{2}+2^{n}$.

Yes, and the other equation for $n=6k+1$ is analogous.

 

[Math100]

Yes. We did not really use the condition $n\neq 6k+3$ except that we omitted the case. But $2^\text{odd}=2^{2m+1}=2\cdot 4^m \equiv 2\cdot 1^m\equiv 2\mod 3$ is the same in all cases. Why do we need the condition $n\neq 6k+3$ at all?

Is it because $2^{6k+3}=2^{3(2k+1)}$?

 

[fresh_42]

Is it because $2^{6k+3}=2^{3(2k+1)}$?

No. The proof fails at another point. But where and why?

 

[Math100]

No. The proof fails at another point. But where and why?

For $n=6k+3$:
we have $36k^2+36k+2^{6k+3}+9\equiv 0\cdot k^2+0\cdot k+8\cdot 2^{6k}+0\equiv 8\cdot 2^{6k}\equiv 1$ mod $3$.

 

[Math100]

When $n=6k+3$,
$n^2+2^{n}$ is prime.

 

[fresh_42]

For $n=6k+3$:
we have $36k^2+36k+2^{6k+3}+9\equiv 0\cdot k^2+0\cdot k+8\cdot 2^{6k}+0\equiv 8\cdot 2^{6k}\equiv 1$ mod $3$.

Almost. All correct. but it is $\equiv 2 \mod 3$. But it isn't divisible by $3$. Would be interesting to find some primes $n^2+2^n$ with $n=6k+3$, $k>0$.

 

[Math100]

Almost. All correct. but it is $\equiv 2 \mod 3$. But it isn't divisible by $3$. Would be interesting to find some primes $n^2+2^n$ with $n=6k+3$, $k>0$.

For $k=1$, the result of $n^2+2^n$ is prime, since it gives us $593$.

 

[fresh_42]

For $k=1$, the result of $n^2+2^n$ is prime, since it gives us $593$.

Here is a useful list: https://de.wikibooks.org/wiki/Primzahlen:_Tabelle_der_Primzahlen_(2_-_100.000)

 

[Math100]

Okay, so here's my revised proof:

Suppose $n>1$ is an integer not of the form $6k+3$.
Applying the Division Algorithm produces:
$n=6k$, $n=6k+1$, $n=6k+2$, $n=6k+4$, or $n=6k+5$.
Now we consider five cases.
Case #1: Suppose $n=6k$ for some $k\in\mathbb{Z}$.
Then we have $n^2+2^{n}=(6k)^2+2^{6k}$
$=36k^2+2^{6k}$
$=2(18k^2+2^{6k-1})$
$=2m$,
where $m=18k^2+2^{6k-1}$ is an integer.
Thus, $2\mid n^2+2^{n}$.
Case #2: Suppose $n=6k+1$ for some $k\in\mathbb{Z}$.
Then we have $n^2+2^{n}=(6k+1)^2+2^{6k+1}$
$=36k^2+12k+2^{6k+1}+1$
$\equiv 0\cdot k^2+0\cdot k+2\cdot 2^{6k}+1$
$\equiv 2\cdot 2^{6k}+1$
$\equiv 0$ mod $3$.
Thus, $3\mid n^2+2^{n}$.
Case #3: Suppose $n=6k+2$ for some $k\in\mathbb{Z}$.
Then we have $n^2+2^{n}=(6k+2)^2+2^{6k+2}$
$=36k^2+24k+2^{6k+2}+4$
$=2(18k^2+12k+2^{6k+1}+2)$
$=2m$,
where $m=18k^2+12k+2^{6k+1}+2$ is an integer.
Thus, $2\mid n^2+2^{n}$.
Case #4: Suppose $n=6k+4$ for some $k\in\mathbb{Z}$.
Then we have $n^2+2^{n}=(6k+4)^2+2^{6k+4}$
$=36k^2+48k+2^{6k+4}+16$
$=2(18k^2+24k+2^{6k+3}+8)$
$=2m$,
where $m=18k^2+24k+2^{6k+3}+8$ is an integer.
Thus, $2\mid n^2+2^{n}$.
Case #5: Suppose $n=6k+5$ for some $k\in\mathbb{Z}$.
Then we have $n^2+2^{n}=(6k+5)^2+2^{6k+5}$
$=36k^2+60k+2^{6k+5}+25$
$\equiv 0\cdot k^2+0\cdot k+32\cdot 2^{6k}+1$
$\equiv 2\cdot 2^{6k}+1$
$\equiv 0$ mod $3$.
Thus, $3\mid n^2+2^{n}$.
Therefore, if $n>1$ is an integer not of the form $6k+3$, then $n^2+2^{n}$ is composite.

 

[fresh_42]

I think you should handle all cases where $n$ is even in one step. And you should mention somewhere that $n^2+2^n>3$. Otherwise, we only have $2\,|\,n^2+2^n$ or $3\,|\,n^2+2^n$ and $n^2+2^n\in \{2,3\}$ would be possible, and those are not composite numbers.

 

[Math100]

I think you should handle all cases where $n$ is even in one step. And you should mention somewhere that $n^2+2^n>3$. Otherwise, we only have $2\,|\,n^2+2^n$ or $3\,|\,n^2+2^n$ and $n^2+2^n\in \{2,3\}$ would be possible, and those are not composite numbers.

How should I do this?

 

[Math100]

Between what lines (where) should I mention that $n^2+2^{n}>3$?

 

[fresh_42]

Between what lines (where) should I mention that $n^2+2^{n}>3$?

You could start with it. E.g.: $n>1$ means $n^2+2^n>7$ so it is sufficient to show that either $2\,|\,n^2+2^n$ or $3\,|\,n^2+2^n$.

If $n$ is even, then ...

If $n$ is odd, then we are left with the cases $n\equiv c\mod 6$ with $c\in \{1,5\}.$ Thus $n^2+2^n=36k^2 + 12\cdot c\cdot k +c^2 +2^{6k+c}= 36k^2 + 12\cdot c\cdot k +c^2 + 2^c\cdot 64^k\equiv 1 + 2^c \equiv 0 \mod 3.$

__________

In case this structure would still convince you if you read it, then it is the briefness you should generally aspire to achieve.

 

[Math100]

You could start with it. E.g.: $n>1$ means $n^2+2^n>7$ so it is sufficient to show that either $2\,|\,n^2+2^n$ or $3\,|\,n^2+2^n$.

If $n$ is even, then ...

If $n$ is odd, then we are left with the cases $n\equiv c\mod 6$ with $c\in \{1,5\}.$ Thus $n^2+2^n=36k^2 + 12\cdot c\cdot k +c^2 +2^{6k+c}= 36k^2 + 12\cdot c\cdot k +c^2 + 2^c\cdot 64^k\equiv 1 + 2^c \equiv 0 \mod 3.$

__________

In case this structure would still convince you if you read it, then it is the briefness you should generally aspire to achieve.

Using this method, do I still have to include/mention the Division Algorithm or not?

 

[fresh_42]

Using this method, do I still have to include/mention the Division Algorithm or not?

The rule should be: Write it in a briefness such that you can still understand it in a month from now. So I'd say yes. Leave hints like "division algorithm", or a note that $c^2\in \{1,25\}=\{1\} \mod 3$, or that $64^k\equiv 1^k \equiv 1 \mod 3.$

You must be able to create notes that you still understand later on without relearning the entire finding process again.

 

[Math100]

You could start with it. E.g.: $n>1$ means $n^2+2^n>7$ so it is sufficient to show that either $2\,|\,n^2+2^n$ or $3\,|\,n^2+2^n$.

If $n$ is even, then ...

If $n$ is odd, then we are left with the cases $n\equiv c\mod 6$ with $c\in \{1,5\}.$ Thus $n^2+2^n=36k^2 + 12\cdot c\cdot k +c^2 +2^{6k+c}= 36k^2 + 12\cdot c\cdot k +c^2 + 2^c\cdot 64^k\equiv 1 + 2^c \equiv 0 \mod 3.$

__________

In case this structure would still convince you if you read it, then it is the briefness you should generally aspire to achieve.

If $n$ is even,
then $n\equiv c$ mod $6$ for $c\in \{0,2,4\}.$
Thus $n^2+2^{n}=36k^2+12\cdot c\cdot k +c^2 +2^{6k+c}$
$=36k^2+12\cdot c\cdot k +c^2 +2^c\cdot 64^k$
$\equiv 2^c$
$\equiv 0\mod 2$.

 

[Math100]

Suppose $n>1$ is an integer not of the form $6k+3$.
Note that $n^2+2^{n}>7$ for $n>1$.
This means $2\mid n^2+2^{n}$ or $3\mid n^2+2^{n}$.
Applying the Division Algorithm produces:
$n=6k, n=6k+1, n=6k+2, n=6k+4,$ or $6k+5$.
Now we consider two cases.
Case #1: Suppose $n$ is an odd integer.
Then we have $n\equiv c$ mod $6$ for $c\in \{1,5\}$.
Thus $n^2+2^{n}=36k^2+12\cdot c\cdot k +c^2+2^{6k+c}$
$=36k^2+12\cdot c\cdot k +c^2+2^{c}\cdot 64^{k}$
$\equiv 1+2^{c}$
$\equiv 0$ mod $3$,
which implies that $3\mid n^2+2^{n}$.
Case #2: Suppose $n$ is an even integer.
Then we have $n\equiv c$ mod $6$ for $c\in \{0,2,4\}$.
Thus $n^2+2^{n}=36k^2+12\cdot c\cdot k +c^2+2^{6k+c}$
$=36k^2+12\cdot c\cdot k +c^2+2^{c}\cdot 64^{k}$
$\equiv 2^{c}$
$\equiv 0$ mod $2$,
which implies that $2\mid n^2+2^{n}$.
Therefore, if $n>1$ is an integer not of the form $6k+3$, then $n^2+2^{n}$ is composite.