8
$\begingroup$

It is known that if a Fermat number $F(n) \triangleq 2^{2^n} + 1$ is composite, then every one of its prime factors can be written as

$p = 2^{n+2}k + 1\;,$

for some positive integer $k$. Since $p \leq F(n)$, we can show that $k < 2^{2^{n-1} - n - 2}$.

Now, going backwards, given some prime number of this form, I want to know if there is a Fermat number that "contains" it.

It's possible to write $p$ in $n+1$ ways:

$p = 2^{n+2}k + 1 = 2^{n+1}(2k) + 1 = 2^n(4k) + 1 = \ldots = 2^3(2^{n-1}k) + 1 = 2^2(2^{n}k) + 1\;,$

which suggests $n+1$ possible Fermat numbers to be a multiple of $p$. However, since $k$ is not arbitrarily large, we may eliminate the $r$ smallest ones, where

$\begin{align} r &= \max_{s \in \mathbb{Z}} \left\{2^{s+1}(2^{n-s+1}k) + 1 \not \leq \sqrt{F(s-1)} \right\} =\\ &= \max_{s \in \mathbb{Z}} \{2^{s+1}(2^{n-s+1}k) + 1 \not \leq 2^{2^{s-2}}\} =\\ &= \max_{s \in \mathbb{Z}} \{2^{n-s+1}k \not< 2^{2^{s-2}-s-1}\} =\\ &= \max_{s \in \mathbb{Z}} \{2^{n+2}k \geq 2^{2^{s-2}}\} =\\ &= \max_{s \in \mathbb{Z}} \{s \leq \log_2(n + \log_2k + 2) + 2\}\\ &= \lfloor \log_2(n + \log_2k + 2) + 2 \rfloor\;. \end{align}$

How do I go on and sieve the remaining Fermat numbers, $F(r)$ to $F(n)$?

  • 0
    @Gottfried Helms OH, CRAP, I made a mistake, you're right. In my Cryptography book, Euler's method is enunciated with $n+1$, but there's an exercise that proves we can be greedy and raise that power to $n+2$. I mixed the two versions.2011-06-11

2 Answers 2

1

Short answer: Simply check the numbers

$2,2^2,2^4,2^8,2^{16},\ldots,2^{2^n}$

modulo $p$ and see which one, if any, equals $-1$ modulo $p$. Each one is the square of the previous one, so this is fast to check.


Let $p>2$ be any odd prime. Consider the multiplicative group $(\mathbb{Z}/p\mathbb{Z})^\times$ and note that $2 \in (\mathbb{Z}/p\mathbb{Z})^\times$.

Now calculate the multiplicative order of $2$ modulo $p$, let us call that order $r$. Now if $r$ is not a power of 2, i.e. $r$ has an odd prime factor, then our $p$ does not divide any Fermat number (easy exercise).

If on the other hand $r$ is on the form $r=2^n$, then in particular

$2^{2^n} \equiv 1 \pmod p$

and because $r$ is minimal, we have necessarily,

$2^{2^{n-1}} \equiv -1 \pmod p$

which is eqivalent to $2^{2^{n-1}}+1 \equiv 0 \pmod p$ or

$p|F(n-1)$

and by the easy exercise this is the only Fermat number which $p$ divides (it follows that no $p$ can divide more than one Fermat number).

As an example take $p=641$, consider the order of $2$ inside $(\mathbb{Z}/641\mathbb{Z})^\times$. We know it will be some divisor of the group order $640$. It turns out that the order is $r=64$. A power of two, $64=2^6$, we conclude $641|F(5)$.

Normally to calculate the order $r$, one would check

$2,2^2,2^3,2^4,2^5,\ldots$

modulo $641$, and it would be guaranteed that you hit $1$ sooner or later. So repeated multiplication by $2$. But for our purpose we need only check

$2,2^2,2^4,2^8,2^{16},\ldots$

and if at some point we do hit $1$, we know the preceding number was $-1$, and we have our answer. If we get past $2^{1024}$ or something, we are past $2^{640}$ already, and we know we will never hit $1$ by repeated squaring, so we conclude the order $r$ is not a power of two, and our prime divides no Fermat number.

2

If you have some prime number $p=2^{n+2}k+1$ with $k$ odd, then you know that if it divides some $F(m)$ it must be the case that $m\le n$. So you can just calculate the numbers $F(1),F(2),\dots,F(n)$ doing all the calculations modulo $p$, and see if you ever get zero.

I'd be surprised if there were a significantly better way.