Prime Decomposition of 5th Fermat Number

From ProofWiki
Jump to navigation Jump to search

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