Prime Decomposition of 2^58+1

Theorem

The number $2^{58} + 1$ has the prime decomposition:

$2^{58} + 1 = 5 \times 107 \, 367 \, 629 \times 536 \, 903 \, 681$

Proof

From Aurifeuillian Factorization of 2 Mod 4th Power of Two plus 1, we have:

$2^{4 n + 2} + 1 = \paren {2^{2 n + 1} - 2^{n + 1} + 1} \paren {2^{2 n + 1} + 2^{n + 1} + 1}$

Setting $n = 14$:

\(\ds 2^{58} + 1\)

\(=\)

\(\ds \paren {2^{29} - 2^{15} + 1} \paren {2^{29} + 2^{15} + 1}\)

\(\ds \)

\(=\)

\(\ds \paren {536 \, 870 \, 912 - 32 \, 768 + 1} \paren {536 \, 870 \, 912 + 32 \, 768 + 1}\)

\(\ds \)

\(=\)

\(\ds 536 \, 838 \, 145 \times 536 \, 903 \, 681\)

\(\ds \)

\(=\)

\(\ds 5 \times 107 \, 367 \, 629 \times 536 \, 903 \, 681\)

$\blacksquare$

Historical Note

The prime decomposition of $2^{58} + 1$ was accomplished by Fortuné Landry in $1869$.

In his words:

No one of our numerous factorizations of $2^n \pm 1$ gave us as much trouble and labour as that of $2^{58} + 1$. This number is divisible by $5$ and if we remove this factor we obtain a number of $17$ digits whose factors have $9$ digits each. If we lose this result we shall miss patience and courage to repeat all calculations we have made and it is possible that many years will pass before someone else will discover the factorization of $2^{58} + 1$.

Then in $1871$, Léon-François-Antoine Aurifeuille discovered the factorization:

$2^{58} + 1 = \paren {2^{29} - 2^{15} + 1} \paren {2^{29} + 2^{15} + 1}$

which was subsequently generalized by François Édouard Anatole Lucas.

In his Curious and Interesting Numbers of $1986$, David Wells reports that this result appears in Volume $128$ of Scripta Mathematica, but as there do not appear to have been that many volumes of that publication, this statement is suspect.

Sources

• 1986: David Wells: Curious and Interesting Numbers ... (previous) ... (next): $2^{58} + 1$
• 1997: David Wells: Curious and Interesting Numbers (2nd ed.) ... (previous) ... (next): $2^{58} + 1$