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.

A theorem of Édouard Lucas related to the Fermat numbers states that :

Any prime divisor $p$ of $F_n=2^{2^n}+1$ is of the form $p=k\cdot 2^{n+2}+1$ whenever $n$ is greater than one.

Does anyone know is there some similar theorem for generalized Fermat numbers: $F_n(a)=a^{2^n}+1$ ?

I've been searching the internet but I couldn't find any similar theorem .

share|improve this question
add comment

2 Answers 2

up vote 2 down vote accepted

Let $p$ be an odd prime divisor of $a^{2^n}+1$. Then $p$ is of the form $p=k2^{n+1}+1$.

The simplest argument uses a small amount of group theory. The fact that $p$ divides $a^{2^n}+1$ can be rewritten as $$a^{2^n}\equiv -1\pmod{p}.$$ Squaring, we obtain that $a^{2^{n+1}}\equiv 1\pmod p$. It follows that $2^{n+1}$ is the smallest positive integer $e$ such that $a^e\equiv 1\pmod {p}$, so $a$ has order $2^{n+1}$ modulo $p$.

The full multiplicative group of the integers modulo $p$ has order $p-1$. The order of any element divides the order of the group, so $2^{n+1}$ divides $p-1$. Equivalently, $p$ is of the form $k2^{n+1}+1$.

In the case $a=2$, as noted in the post, if $n>1$ then we have the stronger result that $2^{n+2}$ divides $p-1$. That is not true for general $a$. For example, $41$ is a prime divisor of $3^{2^2}+1$, but $2^4$ does not divide $41-1$.

Asking that $a$ be even does not necessarily help. For example, $10^{2^2}=73\times 137$, but $2^4$ divides neither $73-1$ nor $137-1$.

Comment: The small amount of explicit group theory that we used can be dispensed with, if we develop a few of the basic properties of the order of an integer $a$ modulo $p$.

The usual proof that gives $2^{n+2}$ for $a=2$ uses the additional fact that if $n >1$, then $p$ has shape $8k+1$, and therefore the "base" $2$ is a quadratic residue of $p$. The same idea should work, for instance, with $a=18$.

share|improve this answer
    
Is this theorem that you proved well known ? I have noticed that many prime divisors are of the form $k\cdot2^{n+1}+1$ but wasn't sure how to prove it.. –  pedja Nov 20 '11 at 19:35
    
The idea is absolutely standard. In general, if $e$ is the smallest positive integer such that $a^e\equiv 1\pmod p$, then $e$ divides $p-1$. This is probably stated explicitly in most Number Theory texts. The proof just uses Fermat's (little) Theorem. We have $a^{p-1}\equiv 1$. Divide $p-1$ by $e$. Say we get non-zero remainder $r$. Then it is easy to show that $a^r\equiv 1\pmod{p}$, contradicting the definition of $e$ as the smallest positive power that gives $1$. I have not seen the application to prime divisors of $a^{2^n}+1$, except with $a=2$. But it's really the same. –  André Nicolas Nov 20 '11 at 19:50
    
@pedja: No real connection with your question, but you are interested in such things: Around 1960 (?) Sierpinski proved that there are infinitely many $k$ such that $k2^n +1$ is composite for every $n$. One example, found later, is $k=78557$. –  André Nicolas Nov 20 '11 at 20:29
    
,Yes I know that..Seventeen or Bust –  pedja Nov 21 '11 at 5:04
add comment

here miguel from spain i demostrated (and i dont know if is important or not) that... if p=4k+3 then: pˆ[((p-3)/2) +1] = +-2 (mod p) if and only if p is prime if p=8k+5 then: pˆ((p-1)/2) =-1 (mod p) if and only if p is prime

and i see in a web site that F8 Fermat number is F8=(a*2ˆ11)*(P62) i think have a mistake because q=a*2ˆ10 really. thank you waiting your answer Miguel R miguelangelreybonet@yahoo.es

share|improve this answer
1  
Welcome to the site. No need to introduce yourself in an answer. Just register your account, and put personal info and contact info there. But your answer is quite difficult to read. If you're familiar with TeX you should know it that you can use it here in-line surround things with dollar signs and so forth. Also your last paragraph is difficult to read. What web site are you referring to. You could give the link. There is syntax for that. Click "edit" under your answer, and click "help". –  Jyrki Lahtonen Jul 4 at 6:39
add comment

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.