Solution to MP41

We received solutions from Saïd Amghibech (internet), Pierre Bornsztein (France), Gilles Feyrit (France), Wolfgang Kais (Germany), Normand Laliberté – a partial solution (Ontario), Patrick LoPresti (USA), and Juan Mir Pieras (Spain).  All solutions were basically the same:

S := n⁴ + 4ⁿ is prime only when n = 1, in which case S= 5.  

Everybody noticed that when n is even, n⁴ and 4ⁿ are both even -- their sum will be properly divisible by 2 and, therefore, not prime.  (In fact, 24 = 42 = 16, so the sum will be divisible by 16 for all even values of n.)  We have thus reduced the problem to

Find those odd numbers n = 2k + 1, k ≥ 0, for which

S = n⁴ + 4^2k+1 = n⁴ + 4(4^k)²

1. Solution by Amghibech and Bornsztein.

Use the fact that

a⁴ + 4b⁴ = (a² + 2ab + 2b²)(a² - 2ab + 2b²)
=((a+b)² + b²)((a-b)² + b²)

At the end we will turn to the question of how to factor fourth degree polynomials.  For now, since S = n⁴ + 4(2^2k)² = n⁴ + 4(2^k)⁴ we use the factorization with a = n and b = 2^k:

S = ((n + 2^k)² + 2^2k)((n - 2^k)² + 2^2k)

The smaller factor is the sum of squares that are both bigger than 1 when k > 0 (and n > 1), so S will be prime only for k = 0.

2. Solution by Feyrit, Kais, and LoPresti.

Observe that r² + s² = (r+s)² – 2rs, so with r = n² and s = 2(4^k),

S = (n² + 2(4^k))² - 4n²4^k = (n² + 2(4^k))² - n²4^k+1

We note that since 4^k+1 = (2^k+1)², S is a difference of two squares, which can be factored as

S = ((n² + 2(4^k)) + n(2^k+1))((n² + 2(4^k)) - n(2^k+1))

We still must show that the smaller factor exceeds 1 when k > 0.  Here is an easy argument for k ≥ 3:

n² + 2(4^k) - n(2^k+1) = n² + 2^k(2^k+1) - (2k+1)(2^k+1)
> 2^k(2^k+1) - (2k + 1)(2^k+1)
= (2^k - 2k - 1)(2^k+1)
> 1

so we simply check that for k = 1 and 2, the smaller factor is 5 and 17.

3. Observation by LaLiberté and LoPresti.

            Since the initial values of S are 5, 32, 145, 512, ..., one might speculate that the values of S for odd n are divisible by 5.  Indeed, when n is odd and not congruent to 0 mod 5, 4ⁿ (mod 5) = –1 and n⁴ (mod 5) = 1, so S = 4ⁿ + n⁴ is congruent to 0 (mod 5).  This means that for n > 1, n odd, and n ≠ 5k, 5 is a proper factor of S.  This leaves open only the case n = 5k with k odd.  Unfortunately, when k = 1 (that is, when n = 5) S = 1649 = 17·97, which suggests that it is time to look for a new approach!  Either one must start over (as Lo Presti did), or try splitting the difference:  ^{(17 + 97)}/₂ = 57; thus, 17 = 57 – 40 and 97 = 57 + 40.  Of course, 40 = 2³·5, which is a BIG hint.  It suggests a way to factor S:

S = n⁴ + 4ⁿ = n⁴ + 4^5k = n⁴ + 2^10k
= (n² + 2^5k + 2^(5k+1)/2 n)(n² + 2^5k - 2^(5k+1)/2 n)

which we recognize as a special case of our first solution above.

Question: How does one factor a fourth degree polynomial?

The general quartic looks like

p(x) = c₄x⁴ + c₃x³ + c₂x² + c₁x + c₀,

or in its homogeneous form (replacing x by ^a/_b and multiplying through by b⁴),

q(a, b) = c₄a⁴ + c₃a³b + c₂a²b² + c₁ab³ + c₀b⁴.

It is a fact that any quartic polynomial with real coefficients can be factored into a product of two quadratic polynomials with real coefficients.  The formula has been known since the sixteenth century, and software is readily available that does the factorization for you; see, for example,

http://mathworld.wolfram.com/QuarticEquation.html

On the other hand, the factorization is practical only in special cases such as

q(a, b) = a⁴ + b⁴.

There is no need to memorize a formula here.  By symmetry the factorization must look like

a⁴ + b⁴ = (a² + xab + b²)(a² + yab + b²).

To find x and y, expand the right-hand side and observe that the coefficient of both a³b and ab³ is x + y, and of a²b² is 2 + xy.  For the equality to hold these coefficients must both be zero, so x = –y = √2.  Thus,

a⁴ + b⁴ = (a² + √2 ab + b²)(a² – √2 ab + b²).

To factor a⁴ + 4c⁴ (= a⁴ + (√2 c)⁴) one can use b = √2 c in our formula; alternatively, solve a⁴ + 4c⁴ = (a² + xac + 2c²)(a² – xac + 2c²) for x.  Either way, one gets the formula used in our first solution.  Bornsztein attached the name of Sophie Germain (1776 – 1831) to that formula, but it would be surprising had the ancient Greeks failed to know it 2000 years before Germain was born.  Another nice quartic that is easily factored is p(x) = x⁴ + x³ + x² + x + 1; as a simple exercise you might want to try factoring it yourself.