Some numbers look prime and are not. 629, for example, is not even, does not end in 5 and is not a multiple of 3. But $629=5^4+4$, and that form gives it away: it factors by an identity that bears Sophie Germain’s name.

The identity

For any numbers $a$ and $b$,

$$\begin{aligned}a^4+4b^4={}&\left(a^2+2b^2+2ab\right)\\&\times\left(a^2+2b^2-2ab\right).\end{aligned}$$

The trick for finding it is completing the square, as in the quadratic formula. The sum $a^4+4b^4$ is almost the square of $a^2+2b^2$; only the middle term, $4a^2b^2$, is missing. Adding and subtracting that term,

$$\begin{aligned}a^4+4b^4&=\left(a^4+4a^2b^2+4b^4\right)-4a^2b^2\\&=\left(a^2+2b^2\right)^2-(2ab)^2.\end{aligned}$$

Now it is a difference of two squares, and $u^2-v^2=(u+v)(u-v)$ finishes the job.

In the example, with $a=5$ and $b=1$:

$$5^4+4=(25+2+10)(25+2-10)=37\cdot17=629.$$

What looked prime

The identity shows at once that many innocent-looking numbers are composite. For example, $n^4+4$ is always composite when $n>1$: just take $a=n$ and $b=1$, and the two factors, $n^2+2n+2$ and $n^2-2n+2$, are greater than 1. Only $n=1$ escapes, because then the second factor is $1$ and $1^4+4=5$ is prime.

A more surprising example comes from powers of 2. The number $2^{10}+1=1025$ can be written as $1+4\cdot4^4$, with $a=1$ and $b=4$:

$$2^{10}+1=(1+32+8)(1+32-8)=41\cdot25.$$

This kind of factorisation, for numbers $2^{4k+2}+1$, was used in the nineteenth century to break huge numbers. In 1869 the Frenchman Fortuné Landry factored by hand the 18-digit number $2^{58}+1$; shortly afterwards Léon-François-Antoine Aurifeuille showed that, with the Sophie Germain identity, the first split takes one line.

Exercise: factor 3⁴ + 4 · 2⁴ = 145

With $a=3$ and $b=2$: $a^2+2b^2=9+8=17$ and $2ab=12$. So $145=(17+12)(17-12)=29\cdot5$.

Exercise: show that n⁴ + 4ⁿ is composite for every odd n greater than 1

If $n$ is odd, $n=2k+1$, and then $4^n=4\cdot4^{2k}=4\cdot\left(2^k\right)^4$. With $a=n$ and $b=2^k$, the identity gives

$$\begin{aligned}n^4+4^n={}&\left(n^2+2^{2k+1}+n\,2^{k+1}\right)\\&\times\left(n^2+2^{2k+1}-n\,2^{k+1}\right).\end{aligned}$$

The second factor is $(n-2^k)^2+2^{2k}$, which is greater than 1 when $n>1$. So the number is composite. With $n=545$, this answers the olympiad question. (If $n$ is even, $n^4+4^n$ is even and greater than 2, so it is also composite.)

Sources: biography of Sophie Germain, MacTutor · Leonard E. Dickson, History of the Theory of Numbers, vol. 1 (1919), chapter on the factorisation of $a^n\pm b^n$.

All Sophie Germain topics · ← Sophie Germain primes and cryptography · Chladni figures and the prize for vibrating plates →

Image credits.