Prove that $2^{58}+1$ can be written as a product of 3 positive integers, each greater than 1.

Question

I first attempted to factor it using SFFT, but I got 3 terms left over that wasn't a product. Am I headed in the right direction, or is the correct answer using a completely different method?

Answer 1

There is this paper on Cyclotomic and Aurifeuillian polynomials with a section dedicated to the problem of finding factors of large numbers. So $$2^{58}+1=4^{29}+1=(4+1)\cdot(4^{28}-4^{27}+4^{26}-4^{25}+4^{24}-...+4^{2}-4^{1}+1)$$ $5$ is one factor. Now applying Aurifeuillian factorisation $$2^{58}+1=2^2\cdot (2^{14})^4+1=\left(2\cdot (2^{14})^2\right)^2+1=\left(2\cdot 2^{28}\right)^2+2\cdot \left(2\cdot 2^{28}\right) +1-2\cdot 2\cdot 2^{28}=\\ \left(2\cdot 2^{28}+1\right)^2-\left(2^{15}\right)^2=\left(2\cdot 2^{28}+1-2^{15}\right)\cdot \left(2\cdot 2^{28}+1+2^{15}\right)=\\ \left(2^{29}+1-2^{15}\right)\cdot \left(2^{29}+1+2^{15}\right)$$ So we found two more factors $2^{29}+1-2^{15}$ and $2^{29}+1+2^{15}$ both clearly larger than $5$. From Euclid lemma, $5$ (which is a prime) will divide one of them, thus, there will be (at least) 3 factors.