Prove a number is composite

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 (\pi +2k\pi)/4}\quad k=0,1,2,3 \\ && \\ n &=&\sqrt{2}e^{i\pi /4 }=1+i\quad \left( k=0\right) \\[2ex] n &=&\sqrt{2}e^{i 3\pi /4 }=-1+i\quad \left( k=1\right) \\[2ex] n &=&\sqrt{2}e^{i 5\pi/4 }=-1-i\quad \left( k=2\right) \\[2ex] n &=&\sqrt{2}e^{i 7\pi/4}=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$.

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

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

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.