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)$?
 A: 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. 
A: 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.
