A theorem about prime divisors of generalized Fermat numbers?

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 .

Solution 1:

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

Solution 2:

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. DOI: 10.1090/S0025-5718-98-00891-6
[38] Jiménez Calvo, I., A note on factors of generalized Fermat numbers. Appl. Math. Lett. 13.6 (2000), 1-5. DOI:10.1016/S0893-9659(00)00045-8

Some other references related to this topic are given there.