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.

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

2 Answers 2

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|improve this answer
2  
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}}$? –  mathh Aug 26 at 15:38
1  
@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 at 22:44

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|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.