# 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$

## Historical Note

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