# Finding a Fermat number with a given prime factor

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)$?

-
is there some specific reason, that you switch from $2^{n+2}k+1$ for p to $2^{n+1}k+1$ in the above? (Maybe I'm missing something obvious?) –  Gottfried Helms Jun 10 '11 at 5:28
@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. –  Luke Jun 11 '11 at 17:56

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.

-

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.

-