# Prove a number is composite

How can I prove that $$n^4 + 4$$ is composite for all $n > 5$?

This problem looked very simple, but I took 6 hours and ended up with nothing :(. I broke it into cases base on quotient remainder theorem, but it did not give any useful information.
Plus, I try to factor it out: $$n^4 - 16 + 20 = ( n^2 - 4 )( n^2 + 4 ) - 5\cdot4$$ If a composite is added to a number that is a multiple of $5$, is there anything special? A hint would suffice.

Thanks,
Chan

-
Why the condition $n>5$? It is enough $n>1$. –  Américo Tavares Feb 9 '11 at 12:56

Try factoring as the product of two quadratic expressions: $n^4+4=(n^2+an+b)(n^2+cn+d)$.

-
Thanks for a useful hint. –  Chan Feb 9 '11 at 10:02
@Chan: Now try this: for which $t\in\mathbf Z$ does $n^4+t$ factor? –  lhf Feb 9 '11 at 10:05
BTW, I first saw that problem in the first chapter of Apostol's Introduction to Analytic Number Theory. I immediately thought of using Fermat's theorem: $n^4+4$ is divisible by 5, but that only works when $n$ is not a multiple of 5. Now Apostol does not discuss Fermat's theorem till later, so there had to be a more fundamental reason. Alas, it was an algebraic reason, not really an arithmetic reason. –  lhf Feb 9 '11 at 10:11
Thanks a lot for the information. I will try harder. –  Chan Feb 9 '11 at 10:13
The quickest way of factoring is probably to start like this: $(n^2)^2 + 2^2 = (n^2+2)^2 - (2n)^2 = \dots$ –  Hans Lundmark Feb 9 '11 at 10:27

This is a special case of a class of cyclotomic factorizations due to Aurifeuille, Le Lasseur and Lucas, the so-called Aurifeuillian factorizations of cyclotomic polynomials $\rm\;\Phi_n(x) = C_n(x)^2 - n\ x\ D_n(x)^2\;$. These play a role in factoring numbers of the form $\rm\; b^n \pm 1\:$, cf. the Cunningham Project. Below are some simple examples of such factorizations:

$$\begin{array}{rl} x^4 + 2^2 \quad=& (x^2 + 2x + 2)\;(x^2 - 2x + 2) \\\\ \frac{x^6 + 3^3}{x^2 + 3} \quad=& (x^2 + 3x + 3)\;(x^2 - 3x + 3) \\\\ \frac{x^{10} - 5^5}{x^2 - 5} \quad=& (x^4 + 5x^3 + 15x^2 + 25x + 25)\;(x^4 - 5x^3 + 15x^2 - 25x + 25) \\\\ \frac{x^{12} + 6^6}{x^4 + 36} \quad=& (x^4 + 6x^3 + 18x^2 + 36x + 36)\;(x^4 - 6x^3 + 18x^2 - 36x + 36) \\\\ \end{array}$$

-
It's $x^6+3^3$ in the second factorization. –  lhf Feb 12 '11 at 12:47
@lhf: Thanks, I've corrected the typo. –  Bill Dubuque Feb 12 '11 at 17:35

You can factor out $n^{4}+4$ algebraically by finding the four roots of $n^{4}+4=0$.

Since $n^{4}+4=0\Leftrightarrow n^{4}=4e^{i\pi }$, we have

$$\begin{eqnarray*} n &=&4^{1/4}e^{i\left( \dfrac{\pi +2k\pi }{4}\right) }\quad k=0,1,2,3 \\ && \\ n &=&\sqrt{2}e^{i\left( \dfrac{\pi }{4}\right) }=1+i\quad \left( k=0\right) \\ n &=&\sqrt{2}e^{i\left( \dfrac{3\pi }{4}\right) }=-1+i\quad \left( k=1\right) \\ n &=&\sqrt{2}e^{i\left( \dfrac{5\pi }{4}\right) }=-1-i\quad \left( k=2\right) \\ n &=&\sqrt{2}e^{i\left( \dfrac{7\pi }{4}\right) }=1-i\quad \left( k=3\right). \end{eqnarray*}$$

Now combining the complex conjugates factors, we get

$$\begin{eqnarray*} n^{4}+4 &=&\left( n-1-i\right) \left( n+1-i\right) \left( n+1+i\right) \left( n-1+i\right) \\ &=&\left( \left( n+1-i\right) \left( n+1+i\right) \right) \left( \left( n-1-i\right) \left( n-1+i\right) \right) \\ &=&\left( n^{2}+2n+2\right) \left( n^{2}-2n+2\right). \end{eqnarray*}$$

Note: for $n>1$, $n^2+2n+2>5$ and $n^2-2n+2>1$.

-

Factoring yields \begin{align} n^4+4 &=(n^2+2i)(n^2-2i)\\ &=(n+1+i)(n-1-i)(n+1-i)(n-1+i)\\ &=(n+1+i)(n+1-i)(n-1-i)(n-1+i)\\ &=((n+1)^2+1)((n-1)^2+1) \end{align} So for $n>1$, $n^4+4$ is composite.

-

In fact, it is true for $n>1$. You just need a clever way of factoring the expression:

$$n^4 + 4 = n^4 + 4 + 4n^2 - 4n^2 = \left ( \cdots + \cdots - \cdots \right ) \cdot \left ( \cdots + \cdots + \cdots \right )$$

-