# Proving an expression is composite

I am trying to prove that $n^4 + 4^n$ is composite if $n$ is an integer greater than 1. This is trivial for even $n$ since the expression will be even if $n$ is even.

This problem is given in a section where induction is introduced, but I am not quite sure how induction could be used to solve this problem. I have tried examining expansions of the expression at $n+2$ and $n$, but have found no success.

I would appreciate any hints on how to go about proving that the expression is not prime for odd integers greater than 1.

• Write it as a difference of squares. – Adam Hughes Jul 1 '14 at 19:54
• How? It's $n^4 + 4^n$ not $n^4 - 4^n$ – Mathmo123 Jul 1 '14 at 19:55
• @Mathmo123: see my answer below. – Adam Hughes Jul 1 '14 at 20:03

$(n^2)^2+(2^n)^2=(n^2+2^n)^2-2^{n+1}n^2$. Since $n$ is odd...

• Ah. Very neat!! – Mathmo123 Jul 1 '14 at 20:05
• Originally, I was not sure how I should go about writing it as a difference of squares. Thanks for your help. – pidude Jul 1 '14 at 20:12

Hint: calculate this value explicitly for $n=1,3$ (or predict what will happen). Can you see any common factors? Can you prove that there is a number $m$ such that if $n$ is odd, then $m|(n^4 + 4^n)$?

Let me know if you need further hints.

• I originally tried doing that but to no avail. Evaluated at 3 I obtain 145 which has factors of 5 and 29. At 5, the expression equals 1649, which has factors of 17 and 97. I will keep looking for a pattern and let you know if I need more hints. Thanks for your help. – pidude Jul 1 '14 at 19:59
• Ah... using this method, there will be a difference between multiples of 5 and other odd numbers. You will find that for odd numbers that are not a multiple of 5, 5 will be a divisor – Mathmo123 Jul 1 '14 at 20:01
• Ok, so I was able to prove that. Now I'm working numbers which are multiples of 5. – pidude Jul 1 '14 at 20:09

I am very impressive with Adam's solution. There is very neat. So, I beg for a chance to write the full description about the proof step-by-step.

• We can transform $n^4+4^n$ to $(n^2+2^n)^2-2^{n+1}n^2$ as Adam's suggestion by
1. $n^{(2^2)}+(2^2)^n = (n^2)^2+(2^n)^2$ associative law
2. Now, we mention $(a+b)^2 = (a+b)(a+b) = a^2+2ab+b^2$ algebraic multiplication
3. $(n^2)^2+(2^n)^2+2(n^2)(2^n)-2(n^2)(2^n)$ adding $+2ab-2ab$ to expression
4. $(n^2)^2+2(n^2)(2^n)+(2^n)^2-2(n^2)(2^n)$ re-arrange the expression
5. $(n^2+2^n)^2-2(n^2)(2^n)$ from step 2
6. $(n^2+2^n)^2-2^{n+1}n^2$ law of Exponential
• We try to get the $(n^2+2^n)^2-2^{n+1}n^2$ to conform to $a^2-b^2$ because $a^2-b^2=(a+b)(a-b)$ algebraic multiplication, again
1. Treat $n^2+2^n$ as $a$
2. Since $n$ is odd, n+1 is even. So, we can assume $2m=n+1$, where $m$ is integer
3. So, re-write the $2^{n+1}n^2$ to be $2^{2m}n^2$
4. $2^{2m}n^2=(n2^m)^2$ associative law
5. Treat $n2^m$ as $b$
• It implies that both $a$ and $b$ are both positive integer
• From $a^2-b^2=(a+b)(a-b)$ and the result of $n^4 + 2^4$, it implies that $a$ is greater than $b$
• Hence both $(a+b)$ and $(a-b)$ are positive integer, that causes the result of $n^4 + 2^4$ is combination of $(a+b)$ and $(a-b)$

Some interesting factorizations of a polynomial of type $x^4+\text{const}$: $$x^4+4=(x^2+2x+2)(x^2-2x-2) \tag{1}$$

$$x^4+1=(x^2+\sqrt[]{2}x+1)(x^2-\sqrt[]{2}x+1) \tag{2}$$

So one can ask, how to select the coefficients $a,b,c,d$ in

$$(x^2+ax+b)(x^2+cx+d) \tag{3}$$

such that all coefficients of the resulting polynomial are zero except the constant term and the coefficient of the 4th power. The latter is $1$.

If we expand $(3)$ we get

$$x^4+(c+a)x^3+(d+a c+b)x^2+(a d+b c)x+b d$$

And the coefficients disappear, if

$$\begin{eqnarray} c+a &=& 0 \\ d+ ac +b &=& 0 \\ ad+bc &=& 0 \end{eqnarray}$$

When solving for $b,c,d$ we get

$$\begin{eqnarray} c &=& -a \\ b &=& \frac{a^2}{2} \\ d &=& \frac{a^2}{2} \end{eqnarray}$$

and therefore

$$x^4+\frac{a^4}{4} = (x^2+a x+\frac{a^2}{2})(x^2-ax+\frac{a^2}{2})$$

For $a=2$ this gives $(1)$, $a=\sqrt[]{2}$ this gives $82)$ . Substituting $a=2^{t+1}$ we get

$$x^4+4^{2t+1} = (x^2+2\cdot 2^t x+2^{2t+1})(x^2-2\cdot 2^tx+2^{2t+1})$$

Substituting $x=n=2t+1$ gives the required result for odd $n$.