Sophie Germain Identity

The following algebraic identity is due to Sophie Germain:

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

She discovered this identity in her explorations related to Fermat's last theorem and primality testing. The identity is often used to find factors of integers of a certain form, and is common in contest mathematics. Here is a basic example:

Prove that $3^{44}+4^{29}$ is composite.

---

Write $3^{44} + 4^{29}$ as

$$3^{44}+4^{29}=3^{11\times4}+\big(4\times4^{28}\big)=\big(3^{11}\big)^4+4\big(4^7\big)^4.$$

Then, by the Sophie Germain identity with $a=3^{11}$ and $b=4^7$:

$$\begin{aligned} 3^{44}+4^{29} &=\big(3^{11}\big)^4+4\cdot4^{28}\\ &=\Big[\big(3^{11}\big)^2+2\cdot\big(4^7\big)^2+2\big(3^{11}\big)\big(4^7\big)\Big] \cdot \Big[\big(3^{11}\big)^2+2\cdot\big(4^7\big)^2-2\big(3^{11}\big)\big(4^7\big)\Big], \end{aligned}$$

which is the product of two integers which are each greater than 1. $_\square$

Note that if $a,b$ are positive integers, both factors of $a^4+4b^4$ are sums of two squares and are positive integers greater than $1,$ unless $b=1$ and $a-b=0,$ i.e. $a=b=1.$ (In this case, $a^4+4b^4 = 5$ is in fact prime.) This fact is often useful in proofs (it is used several times in the last section of this wiki).

Here are a few typical applications of the identity.

Show that for any positive integer $n>1,$ $n^4+4^n$ is not a prime.

---

The proof is similar to the example in the introduction. If $n$ is even, then so is $n^4+4^n.$ If $n$ is odd, say $n = 2k+1,$ then

$$n^4+4^n = n^4 + 4\big(2^k\big)^4 = \left(\big(n+2^k\big)^2+4^k\right)\left(\big(n-2^k\big)^2+4^k\right)$$

and both factors are $>1.$ $_\square$

While it is often enough to know that a factorization exists, sometimes the form of the factorization is useful, as in the following problem and examples:

(MIT ATF Math Prize for Girls, 2011)

The number $104,060,465$ is divisible by a five-digit prime number. What is it?

---

Notice that $104,060,401$ looks like the fourth row of Pascal's triangle; that is,

$$104,060,401 = 1+\binom{4}{1} 100 + \binom{4}{2} 100^2 + \binom{4}{3}100^3 + 100^4 = (100+1)^4 = 101^4.$$

So our number is $101^4 + 64 = 101^4 + 4 \cdot 2^4.$ Apply Sophie Germain's identity to factor it as

$$104,060,465 = (103^2+2^2)(99^2+2^2) = 10613 \cdot 9805.$$

The only possible five-digit prime factor is $10613,$ and since we are given that there is a five-digit prime factor, this must be it. $_\square$

Sophie Germain's identity appears in an important question in abstract algebra: "Under what conditions on $n$ and $a$ is the polynomial $x^n-a$ irreducible?"

It's clearly necessary that $a$ not be an $n^\text{th}$ power, but this is not enough. For instance, $x^6 - 4$ factors over the rational numbers as $\big(x^3-2\big)\big(x^3+2\big).$ So in fact it is also necessary that $a$ not be a $p^\text{th}$ power for any prime $p$ dividing $n.$

Is this condition sufficient, or are there other counterexamples?

Yes, if $n$ is divisible by $4$ and $a =-4b^4$ for some $b,$ the polynomial $x^n -a$ factors by Sophie Germain's identity.

It turns out that this is the entire list of counterexamples:

Let $K$ be a field, $a \in K,$ and let $n>1$ be a positive integer. Then $x^n-a$ is irreducible over $K$ if and only if

• $a$ is not a $p^\text{th}$ power for any $p|n$, and

• if $4|n,$ $a$ is not of the form $-4b^4$ for $b\in K.$

The proof is beyond the scope of this wiki, but the upshot of the theorem is that Sophie Germain's identity is essentially the "only" nontrivial factorization of a binomial of this type.

This section is dedicated to the proof of the following theorem:

Let $x,y,z$ be nonnegative integers. The only solutions to $3^x+4^y = 5^z$ are $(0,1,1)$ and $(2,2,2).$

The proof involves Sophie Germain's identity in multiple cases.

Look mod $4$: $(-1)^x + 0^y \equiv 1.$ So $y \ne 0$ and $x$ is even. Write $x=2a,$ so the equation becomes $9^a + 4^y = 5^z.$

Now look mod $5$: $z=0$ is impossible, so the equation becomes $(-1)^a+(-1)^y \equiv 0,$ so exactly one of $a$ and $y$ is even.

Case 1: $a$ is even, $y$ is odd.
Write $a=2b,$ $y=2c+1,$ and the equation becomes $\big(3^b\big)^4 + 4 \cdot \big(2^c\big)^4 = 5^z,$ so Sophie Germain's identity gives a factorization

$$5^z = \left(\big(3^b+2^c\big)^2+4^c\right)\left(\big(3^b-2^c\big)^2+4^c\right).$$

The difference between the two factors is $2^{c+2}3^b,$ which is not divisible by $5,$ but both factors are powers of $5,$ so the only possibility is that the second one is $1.$ This means that $c=0$ and $b=0,$ which gives $x=0,y=1,z=1.$

Case 2: $a$ is odd, $y$ is even.
Write $y=2c,$ and the equation becomes $9^a + 16^c = 5^z.$ Look mod $8$: $5^z \equiv 1,$ so $z$ is even. Write $z=2d,$ and now we have $9^a+16^c = 25^d.$ Then factorization gives

$$\big(5^d-4^c\big)\big(5^d+4^c\big) = 9^a.$$

Again, the difference between these two factors is $2^{2c+1},$ which is not divisible by $9,$ so $5^d-4^c=1.$

Looking modulo $5,$ we get that $c$ is odd, say $c=2e+1,$ so $5^d = 1+4(2^e)^4$ and Sophie Germain's identity gives

$$5^d = \left(\big(1+2^e\big)^2+4^e\right)\left(\big(1-2^e\big)^2+4^e\right),$$

and again the difference between the two factors is $2^{e+2},$ which is not divisible by $5,$ so the second factor is $1,$ which implies $e=0.$ So $c=1$ and $d=1,$ which gives $y=z=2$ and hence $x=2.$

The proof is complete. $_\square$

(Reference: Carl Johan Ragnarsson, "An Interesting Application of the Sophie Germain Identity," Mathematical Mayhem v. 26, no. 7, pp. 417-428.)