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

3 Answers 3

up vote 4 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
1  
@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
    
@AndréNicolas can you explain how did you get ord(2,p) = $2^{n+1}$? –  Karim Mansour Apr 20 at 3:30

here miguel from spain i demostrated (and i dont know if is important or not) that...

if $p=4k+3$ then: $p^{\frac{p-3}{2}+1} = \pm 2 \pmod p$ if and only if p is prime

if $p=8k+5$ then: $p^{\frac{p-1}{2}} =-1 \pmod p$ if and only if p is prime

and i see in a web site that F8 Fermat number is $F8=(a\cdot2^{11})\cdot(P62)$ i think have a mistake because $q=a\cdot2^{10}$ really. thank you waiting your answer Miguel R miguelangelreybonet@yahoo.es

share|improve this answer
2  
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 '14 at 6:39

A simple Google search lead me to a chapter in the proceedings Public-Key Cryptography and Computational Number Theory edited by Kazimierz Alster, Jerzy Urbanowicz, Hugh C. Williams, which contains some results and references which might be interesting in connection with your question, in particular it lists some known results, which I have copied below.

While the Fermat numbers $F_m$ have long been of great interest to mathematicians, the generalized Fermat numbers $$F_m(a,b)=a^{2^m}+b^{2^m}, \qquad \gcd(a,b)=1$$ and the more special case $b = 1$, were not seriously studied until the 1960s;

[part of the text skipped]

The observations above are explained by the results in this subsection; they were recently published by I. Jiménez Calvo [38].

Theorem 3.1 (Jiménez Calvo). Let $p=k\cdot 2^n+1$ be a prime, where $k$ is odd and $n=n'2^l$, with $n'>3$ odd. If $p$ divides the Fermat number $F_m=2^{2^m}+1$, then it also divides the generalized Fermat number $$F_{m-l}(k,1)=k^{2^{m-1}}+1.$$

To put the next result of Jiménez Calvo into perspective, we quote from [9] the following generalization of the Euler-Lucas theorem (Theorem 2.1):

Theorem 3.2 (Björn and Riesel). Let $p=k\cdot 2^n+1$ be a prime, where $k$ is odd. Suppose that $p\mid F_m(a,b)$ and $u \equiv a/b \pmod b$ is a $2^t$-th power residue but not a $2^{t+1}$-th power residue $\pmod p$. Then $n=m+t+1$.

For a proof, see [9]. A partial converse is given by the following

Theorem 3.3 (Jiménez Calvo). Let $p=k\cdot 2^n+1$ be a prime, where $k$ is odd. Let $v:=\operatorname{ord}_2(n)$, and $u$ be such that $2$ is a $2^u$-th power residue but not a $2^{u+1}$-th power residue $\pmod p$. Furthermore, suppose that $n$, $k$ have a common divisor $d>3$, and if $k' := k/d$, then $2$ is a $k$'-th power residue $\pmod p$.
Then $p\mid k^{2^m}+1$ with $m=n-u-v-1$.

As an immediate consequence (in the case $k' = 1$) we get the following result. By the supplementary laws of quadratic reciprocity we always have $u\ge1$.

Corollary 3.4. Let $p=k\cdot 2^n+4$ be a prime, with $k$ odd and $k\mid n$. Then $$p\mid k^{2^m}+1 \qquad\text{for some}\qquad m\le n-2.$$

[9] Björn, A., Riesel, H. Factors of generalized Fermat numbers. Math. Comp. 67 (1998), 441-446.
[38] Jiménez Calvo, I., A note on factors of generalized Fermat numbers. Appl. Math. Lett. 13.6 (2000), 1-5.

Some other references related to this topic are given there.

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.