Skip to main content.

Solution to puzzle 39: Prime or composite?

Is the number 2438100000001 prime or composite?  No calculators or computers allowed!


Firstly, notice that 2438100000001 = x5 + x4 + 1, with x = 300.

Then f(x) = x2 + x + 1 is a factor of g(x) = x5 + x4 + 1, since f(w) = g(w) = 0, where w is a (complex) primitive cube root of unity.
(More formally, since f(w) = g(w) = f(w2) = g(w2) = 0, by the Polynomial Factor Theorem, (x − w) and (x − w2) are factors of f and g.  Hence (x − w)(x − w2) = x2 + x + 1 is a factor of f and g.)

Therefore 2438100000001 is composite, with factor f(300) = 90301.

Source: Inspired by problem D 4 in (Adobe) Portable Document Format Problems in Elementary Number Theory (problems since taken down)

Back to top