# Prime Decomposition of 5th Fermat Number

## Theorem

The prime decomposition of the $5$th Fermat number is given by:

\(\displaystyle 2^{\paren {2^5} } + 1\) | \(=\) | \(\displaystyle 4 \, 294 \, 967 \, 297\) | Sequence of Fermat Numbers | ||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle 641 \times 6 \, 700 \, 417\) |

## Proof 1

From Divisor of Fermat Number, if $2^{\paren {2^n} } + 1$ has a divisor, it will be in the form:

- $k \, 2^{n + 2} + 1$

In the case of $n = 5$, a divisor of $2^{\paren {2^n} } + 1$ is then of the form:

- $k \, 2^7 + 1 = k \times 128 + 1$

Further, such a number will (for small $k$ at least) be prime, otherwise it will itself have a divisor which is not of that form.

Thus we investigate:

\(\displaystyle 1 \times 128 + 1\) | \(=\) | \(\displaystyle 129\) | \(\displaystyle = 3 \times 43\) | which is not prime | |||||||||

\(\displaystyle 2 \times 128 + 1\) | \(=\) | \(\displaystyle 257\) | which is prime | ||||||||||

\(\displaystyle 3 \times 128 + 1\) | \(=\) | \(\displaystyle 385\) | \(\displaystyle = 5 \times 7 \times 11\) | which is not prime | |||||||||

\(\displaystyle 4 \times 128 + 1\) | \(=\) | \(\displaystyle 513\) | \(\displaystyle = 3^3 \times 19\) | which is not prime | |||||||||

\(\displaystyle 5 \times 128 + 1\) | \(=\) | \(\displaystyle 641\) | which is prime | ||||||||||

\(\displaystyle 6 \times 128 + 1\) | \(=\) | \(\displaystyle 769\) | which is prime |

We have that:

\(\displaystyle 2^{32} - 1\) | \(=\) | \(\displaystyle \paren {2^{16} + 1} \paren {2^{16} - 1}\) | Difference of Two Squares | ||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \paren {2^{16} + 1} \paren {2^8 - 1} \paren {2^8 + 1}\) |

But

- $2^8 + 1 = 257$

and so:

- $2^{\paren {2^5} } - 1 \equiv 0 \pmod {257}$

which means:

- $2^{\paren {2^5} } + 1 \equiv 2 \pmod {257}$

so there is no need to do a trial division of $2^{\paren {2^5} } + 1$ by $257$.

Now dividing $4 \, 294 \, 967 \, 297$ by $641$ we find:

6 700 417 --------------- 641 ) 4 294 967 297 3 846 ----- 448 9 448 7 ----- 267 2 256 4 ----- 10 89 6 41 ----- 4 487 4 487 =====

and the divisor has been found.

$\blacksquare$

## Proof 2

Note the remarkable coincidence that $2^4 + 5^4 = 2^7 \cdot 5 + 1 = 641$.

First we eliminate $y$ from $x^4 + y^4 = x^7 y + 1 = 0$:

\(\displaystyle x^4 + y^4\) | \(=\) | \(\displaystyle x^7 y + 1 = 0\) | |||||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle -x^4\) | \(=\) | \(\displaystyle y^4\) | ||||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle x^{28} \paren {-x^4} + 1\) | \(=\) | \(\displaystyle 0\) | ||||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle x^{32}\) | \(=\) | \(\displaystyle -1\) |

Now we use the above result for $x = 2$ and $y = 4$ in modulo $641$:

\(\displaystyle 2^4 + 5^4\) | \(\equiv\) | \(\displaystyle 0\) | \(\displaystyle \pmod {641}\) | ||||||||||

\(\displaystyle 2^7 \cdot 5\) | \(\equiv\) | \(\displaystyle -1\) | \(\displaystyle \pmod {641}\) | ||||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle 2^{28} \paren {-2^4}\) | \(\equiv\) | \(\displaystyle -1\) | \(\displaystyle \pmod {641}\) | |||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle 2^{32}\) | \(\equiv\) | \(\displaystyle -1\) | \(\displaystyle \pmod {641}\) | |||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle 2^{32} + 1\) | \(\equiv\) | \(\displaystyle 0\) | \(\displaystyle \pmod {641}\) |

Thus $2^{\paren {2^5} } + 1 = 6 \, 700 \, 417 \times 641$ and hence is not prime.

$\blacksquare$

## Also see

## Historical Note

The prime decomposition of the $5$th Fermat number was determined by Leonhard Paul Euler in $1732$.

## Sources

- 1986: David Wells:
*Curious and Interesting Numbers*... (previous) ... (next): $257$ - 1989: Ephraim J. Borowski and Jonathan M. Borwein:
*Dictionary of Mathematics*... (previous) ... (next): Entry:**Fermat prime** - 1997: David Wells:
*Curious and Interesting Numbers*(2nd ed.) ... (previous) ... (next): $257$ - 2008: David Nelson:
*The Penguin Dictionary of Mathematics*(4th ed.) ... (previous) ... (next): Entry:**Fermat number**(P. de Fermat, 1640) - 2008: Ian Stewart:
*Taming the Infinite*... (previous) ... (next): Chapter $7$: Patterns in Numbers: Gauss