# Is 641 the Smallest Factor of any Composite Fermat Number?

Consider the sequence $a_n = 2^{2^n}+1$ of so-called Fermat numbers. It's well known that $a_5$ isn't prime ($a_5 = 641 \cdot 6700417$, this is due to Euler). What I want to know about this sequence is the smallest factor of any of its composite terms. Is it simply 641, or does a later composite term in the sequence have a smaller factor?

I originally wanted to ask if there had been any effort to solve similar problems for other sequences as well, but that's not something I feel MSE would want. If someone has any info on this, however, they should feel free to comment or add it to their answer!

-
Also see A023394 where all terms below $10^{19}$ are given. – Jeppe Stig Nielsen Jan 28 at 14:32

If $q$ is a prime factor of $a_n=2^{2^n}+1$, then $q\equiv1\pmod{2^{n+1}}$ and hence $$q>2^{n+1}\ .$$ So if we are looking for $q<641$ then $n\le8$; if we want $a_n$ composite then $n\ge5$. Thus $n=5,6,7,8$, and there is no prime factor $q$ less than $641$, because all these numbers have been completely factorised.
How do you know that $q\equiv \pmod {2^{n+1}}$? I can see that $a_n=qk\equiv \pmod {2^{n+1}}$, but why does the integer $k$ have to be the inverse of $q\pmod {2^{n+1}}$? – user26486 Aug 26 '14 at 15:38
@mathh This is a standard result about Fermat numbers. Here is a quick proof: modulo $q$ we have $2^{2^{n+1}}\equiv1$ but $2^{2^n}\not\equiv1$; therefore the order of $2$ is a factor of $2^{n+1}$ but not a factor of $2^n$; therefore the order is $2^{n+1}$. But since $q$ is prime, the order of any element is a factor of $q-1$. – David Aug 26 '14 at 22:44
In fact, Lucas (in 1878) strengthened the result to $q\equiv1\pmod{2^{n+2}}$. See MathWorld (Weisstein). Other sources (Caldwell) say Euler already knew this, but I think it was Lucas. – Jeppe Stig Nielsen Jan 28 at 14:40
There is a deterministic answer to this, easy computer program. For each prime $p$ of interest, calculate $$2,4,16,256,\ldots, 2^{\left( 2^n \right)}, \ldots \pmod p$$ until you find repetition. For the prime being worked on, this tells you whether $2^{\left( 2^n \right)}$ can ever be congruent to $-1 \pmod p.$