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.

  • 3
    $\begingroup$ Write it as a difference of squares. $\endgroup$ – Adam Hughes Jul 1 '14 at 19:54
  • $\begingroup$ How? It's $n^4 + 4^n$ not $n^4 - 4^n$ $\endgroup$ – Mathmo123 Jul 1 '14 at 19:55
  • $\begingroup$ @Mathmo123: see my answer below. $\endgroup$ – 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...

| cite | improve this answer | |
  • $\begingroup$ Ah. Very neat!! $\endgroup$ – Mathmo123 Jul 1 '14 at 20:05
  • $\begingroup$ Originally, I was not sure how I should go about writing it as a difference of squares. Thanks for your help. $\endgroup$ – 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.

| cite | improve this answer | |
  • 1
    $\begingroup$ 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. $\endgroup$ – pidude Jul 1 '14 at 19:59
  • 1
    $\begingroup$ 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 $\endgroup$ – Mathmo123 Jul 1 '14 at 20:01
  • $\begingroup$ Ok, so I was able to prove that. Now I'm working numbers which are multiples of 5. $\endgroup$ – 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)$
| cite | improve this answer | |

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

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.