Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.