1. ## [SOLVED] Prove Composite

Problem:
Show that $8^{n}+1$ is composite for all $n\geq1$.

What I have so far:
In general,

$a^{n}+1 = (a+1)(a^{(n-1)} - a^{(n-2)} + a^{(n-3)} - \cdots + 1)$
but this only holds for $n$ odd.

Is there a way to factor when $n$ is even? Or would I have to find a solution specific to $a=8$?

2. Originally Posted by star_tenshi
Problem:
Show that $8^{n}+1$ is composite for all $n\geq1$.

What I have so far:
In general,

$a^{n}+1 = (a+1)(a^{(n-1)} - a^{(n-2)} + a^{(n-3)} - \cdots + 1)$
but this only holds for $n$ odd.

Is there a way to factor when $n$ is even? Or would I have to find a solution specific to $a=8$?
Note: You may want to wait for a more NT minded member to answer this in case of error

Have you tried induction?

3. Originally Posted by star_tenshi
Problem:
Show that $8^{n}+1$ is composite for all $n\geq1$.

What I have so far:
In general,

$a^{n}+1 = (a+1)(a^{(n-1)} - a^{(n-2)} + a^{(n-3)} - \cdots + 1)$
but this only holds for $n$ odd.

Is there a way to factor when $n$ is even? Or would I have to find a solution specific to $a=8$?
You can use that identity with n=3, if you write 8 as 2^3.

4. Originally Posted by Opalg
You can use that identity with n=3, if you write 8 as 2^3.
Yes, I know that, but I am looking at the case where n is even. Even if I were to use $8^{n} + 1 = (2^{3})^m + 1 = 2^{3m} + 1$, $3m$ is not always odd.

5. Make use of the identity: $a^3 + b^3 = (a+b)(a^2 -ab + b^2)$

Here imagine: $a = 2^n$ and $b = 1$

For all $n \geq 1$, we have:
\begin{aligned} 8^n + 1 & = \left(2^3\right)^n + 1 \\ & = \left(2^n\right)^3 + 1 \\ & = \left(2^n + 1\right)\left((2^n)^2 - 2^n + 1\right) \end{aligned}

So what can we conclude?

6. OHHH! Now I see what Opalg was trying to convey. Thanks again o_O for clearing that up!

We can conclude that $8^{n} + 1$ is composite.

Then to generalize, any number that can be expressed as $a^{3} + b^{3}$ is composite because it can be broken down into the factors $(a+b)(a^{2}-ab+b^{2})$!