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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
Also see A023394 where all terms below $10^{19}$ are given. – Jeppe Stig Nielsen Jan 28 at 14:32
up vote 14 down vote accepted

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.

share|cite|improve this answer
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.$

share|cite|improve this answer

Your Answer


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.