Sophie Germain Identity

The following algebraic identity is due to Sophie Germain:

\[\begin{align} 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{align}\]

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{align} 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{align}\]

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