4^(3k) + 2^(3k) +1 is a prime number. What is a proof for that?

Question

In a free time I found some math problems and it really seems like I can't solve this one. Can you please help me?

Answer 1

This is not true.  For example, if k=2, then 4^(3k)+2^(3k)+1 = 4161, which is not prime.  (Its factors are 3, 19, and 73.)

Answer 2

Hi Nino:

 

that's an interesting problem for sure.  Let us look at it a bit more carefully.  If it was not a prime number, it would mean that is would be equal to the product of two integers greater than 1, say M*N.  So the problem is to try to factorize this number into a product of at least two different integers.

 

If we set X = 2^3k, you can see that the potential prime number (P) in question can be written:

 

P = 2^3k * 2^3k + 2^3k + 1 = X² + X + 1

 

Now since we are trying to decompose P into the product of numbers, we know that if A and B are the roots of this second degree polynomial, then we could write:

 

P = (X - A) * (X - B)

 

which would clearly give us some information of whether P is prime, if the factors (X - A) and (X - B) were integers greater than 1.

 

So let us find the roots of the polynom:

 

X² + X +1 = 0 = aX² + bX + c, with a = b= c= 1

 

Calculate the delta:

 

Δ = b² - 4ac = -3 = ( ¿√3 )²  where  ¿ is the complex number with the property  ¿² = -1

 

The complex roots of the polynomial are then A, B = (-b ±√Δ)/(2a), or

 

A = (-1 + ¿√3)/2

B = (-1 - ¿√3)/2

 

Therefore, we can factorize P as:

 

P = X² + X +1 = (X - A) * (X - B)

P = [ X + (1 + ¿√3)/2 ] * [ X + (1 - ¿√3)/2 ]

 

Now since X = 2^3k is a positive integer, we see that P can be written as the product of 2 non-integer, complex numbers.  Therefore, it cannot be decomposed as the product of integer numbers, proving that it must be a prime number.

 

Hope this helps!

 

Jean-Michel