Fermat Numbers Modulo a Prime

Jiří Klaška Institute of Mathematics Faculty of Mechanical Engineering Brno University of Technology Technická 2 CZ – 616 69 Brno Czech Republic

                 klaska@fme.vutbr.cz

Abstract Nearly forty years ago Aigner published an interesting theorem regarding the periodicity of the sequence of Fermat numbers reduced by a given prime modulus. In this article we perform a detailed analysis of Aigner’s result and his proof. Above all, however, we show that Aigner’s theorem can be substantially simplified and also refined.

1 Introduction

Let F_{n} = 2^{2^{n}} + 1 where n ∈ ℕ ∪ {0}. The numbers F_{n} are called Fermat numbers after the French mathematician Pierre de Fermat (1601–1665). Many remarkable properties of Fermat numbers are known. See, for example, the books [3, 4] or consult The On-Line Encyclopedia of Integer Sequences [7, \underline{A000215}].

In 1986, Austrian mathematician Alexander Aigner (1909–1988) published his final paper [1] in which he opened up a new issue of so-called elite primes. Recall that a prime p is called elite if only a finite number of Fermat numbers F_{n} are quadratic residues modulo p. See also [7, \underline{A102742}].

Aigner’s paper [1, p. 87] also contains an interesting theorem concerning the periodicity of the sequence (F_{n} mod p)_{n=0}^{∞}, where p is a prime. Recall now the original German formulation of Aigner’s theorem and his proof arguments.

Theorem 1. (Aigner, 1986) Ist p − 1 = 2^{r}u mit ungeradem u und 2^{s}t mit 0 ≤ s ≤ r und t | u der genaue “Potenzindex” des Restes 2 mod p, so hat die Vorperiode r − s Glieder und die Länge der Periode wird gleich der Ordnung h des Restes 2 in der multiplikativen Gruppe mod u/t = u′.

Proof. Es existiert eine geeignete Primitivwurzel g mod p, so daß 2 ≡ g^{2^{s}t} ist. Quadrierung der Potenz mod p bedeutet Verdopplung des Exponenten mod p − 1. Wir sind solange in der Vorperiode, als im Exponenten der Faktor 2^{r} noch nicht erreicht ist. Hernach sind alle Exponenten durch 2^{r}t teilbar. Und soll nach h Schritten die erste Wiederholung auftreten, so ergibt dies 2^{r+h}t ≡ 2^{r}t nach dem Modul p − 1 = 2^{r}tu′ oder 2^{h} ≡ 1(u′).

Unfortunately, Aigner’s result presented in Theorem 1 has not received the attention that it deserves and has not appeared in any of the recently published books [3, 4] specifically devoted to Fermat numbers. The main reason is probably that the paper [1] was published in German, which, along with some vague wording, makes it difficult to properly understand Theorem 1 and its proof. In this article, we carry out a detailed analysis of Aigner’s result to show that Theorem 1 can be substantially simplified and also refined. The exact formulation of Theorem 1 and its proof in English is presented in Theorem 15 with its simplification provided by Theorem 20.

Throughout this paper, we adopt the following notation. If A is a finite set, #A denotes the number of elements of A. Specifically, if A = ∅, then #A = 0.

2 Basic concepts and auxiliary results

We recall some of the basic definitions and known statements that we need later in the paper.

Lemma 2. Let p be a prime. Then there exist i, j ∈ {0, 1, …, p} such that i < j and F_{i} ≡ F_{j} (mod p).

Proof. The conclusion follows from Dirichlet’s well-known pigeonhole principle.

Remark 3. The reader may find some interesting facts on the history of this principle in article [5].

Lemma 4. Let i ∈ ℕ ∪ {0}, j ∈ ℕ and let i < j. Further, let p be a prime. Then (i) and (ii) hold.

(i) If F_{i} ≡ F_{j} (mod p), then F_{i+t} ≡ F_{j+t} (mod p) for all t ∈ ℕ.

(ii) If F_{j} ≢ F_{j+t} (mod p) for all t ∈ ℕ, then F_{i} ≢ F_{i+t} (mod p) for all t ∈ ℕ.

Proof. We prove (i). Let t ∈ ℕ. First, observe that

F_{i} ≡ F_{j} (mod p) ⟺ 2^{2^{i}} ≡ 2^{2^{j}} (mod p).

Next, by raising both sides of 2^{2^{i}} ≡ 2^{2^{j}} (mod p) to 2^{t}-th power we obtain 2^{2^{i+t}} ≡ 2^{2^{j+t}} (mod p). Hence, F_{i+t} ≡ F_{j+t} (mod p).

We prove (ii). Suppose that F_{i} ≡ F_{i+s} (mod p) for an s ∈ ℕ. Since i < j, there exists a l ∈ ℕ such that j = i + l. Using part (i) of Lemma 2.3, we now get

F_{j} = F_{i+l} ≡ F_{i+l+s} = F_{j+s} (mod p),

which is a contradiction.

It is clear, that Lemma 4 has a crucial importance for further considerations. Indeed, it guarantees that the sequence (F_{n} mod p)_{n=0}^{∞} becomes periodic at some point. In the usual terminology (see, for example, [7]) we say that (F_{n} mod p)_{n=0}^{∞} is an eventually (or ultimately) periodic sequence. Let us now recall some basic definitions.

Definition 5. Let p be a prime.

(i) Let H(p) = {h ∈ ℕ ∪ {0} : F_{h} ≢ F_{h+i} (mod p) for all i ∈ ℕ} and let h(p) = #H(p). Then we call h(p) the length of the pre-period of the sequence (F_{n} mod p)_{n=0}^{∞}. Specifically, if h(p) = 0, then we say that (F_{n} mod p)_{n=0}^{∞} does not have a pre-period.

(ii) Let i ∈ ℕ ∪ {0}, j ∈ ℕ and let i < j. If F_{i} ≡ F_{j} (mod p), we call the number j − i the length of the period of (F_{n} mod p)_{n=0}^{∞}.

(iii) Let h(p) be the length of the pre-period of (F_{n} mod p)_{n=0}^{∞}. Then we call the number k(p) = min{t ∈ ℕ : F_{h(p)} ≡ F_{h(p)+t} (mod p)} the length of the primitive period of the sequence (F_{n} mod p)_{n=0}^{∞}.

An important relationship between the length of a period and the length of the primitive period k(p) is provided by Lemma 6.

Lemma 6. Let i ∈ ℕ ∪ {0}, j ∈ ℕ and let i < j. Further, let p be a prime. Then F_{i} ≡ F_{j} (mod p) if and only if i ≥ h(p) and i ≡ j (mod k(p)).

Proof. Let F_{i} ≡ F_{j} (mod p). Then, by Definition 5, i ≥ h(p) and k(p) ≤ j − i. It is obvious that j −i can be written uniquely in the form of j −i = α·k(p)+β where α ∈ ℕ, β ∈ ℕ∪{0} and 0 ≤ β < k(p). Hence,

F_{i} ≡ F_{j} (mod p) ⟺ F_{i} ≡ F_{i+α·k(p)+β} (mod p).  (1)

On the other hand, we have F_{i} ≡ F_{i+k(p)} (mod p) and, by induction, we find that F_{i} ≡ F_{i+s·k(p)} (mod p) for each s ∈ ℕ. In particular, if s = α, then

F_{i} ≡ F_{i+α·k(p)} (mod p).  (2)

Combining (1) and (2), we now get

F_{i+α·k(p)} ≡ F_{i+α·k(p)+β} (mod p).  (3)

Suppose that β ≠ 0. Then, by (3), (F_{n} mod p)_{n=0}^{∞} is periodic with the length of period equal to β. Since β < k(p), we have a contradiction. Consequently, β = 0 and j − i = α · k(p). Hence, k(p) | j − i, and i ≡ j (mod k(p)) follows.

Let i ≥ h(p) and let i ≡ j (mod k(p)). Then k(p) | j − i and thus, there exists an α ∈ ℕ such that j −i = α·k(p). This, together with F_{i} ≡ F_{i+α·k(p)} (mod p), yields F_{i} ≡ F_{j} (mod p), as required.

It is also useful to recall the following definitions.

Definition 7. Let a, m ∈ ℕ and let gcd(a, m) = 1.

(i) The least t ∈ ℕ such that a^{t} ≡ 1 (mod m) is called the multiplicative order of a modulo m and is denoted by ord_{m}(a).

(ii) If ord_{m}(a) = ϕ(m), then a is called a primitive root of m. Here, ϕ means the Euler function.

(iii) Let g be a primitive root of m. The unique t ∈ ℕ satisfying 1 ≤ t ≤ ϕ(m) and g^{t} ≡ a (mod m) is called index (or discrete logarithm) of a to the base g modulo m and denoted by ind_{g}(a).

For the theory of indices and primitive roots, see, for example, [2, pp. 147–168] or [6, pp. 347–385].

Lemma 8. Let a, m, s, t ∈ ℕ and let gcd(a, m) = 1. Then (i)–(iv) hold.

(i) a^{s} ≡ 1 (mod m) if and only if ord_{m}(a) | s. In particular, if m = p is a prime, then ord_{p}(a) | p − 1.

(ii) a^{s} ≡ a^{t} (mod m) if and only if s ≡ t (mod ord_{m}(a)).

(iii) We have

ord_{m}(a^{s}) = \frac{ord_{m}(a)}{gcd(s, ord_{m}(a))}.

(iv) Let g be a primitive root of a prime p and let a ∈ {1, …, p − 1}. Then we have

gcd(p − 1, ind_{g}(a)) = \frac{p − 1}{ord_{p}(a)}.

For a proof of part (i) of Lemma 8, see, for example, [2, p. 148] or [6, p. 348]. A proof of part (ii) can be found in [2, p. 148] or [6, p. 349]. For a proof of part (iii), see [2, p. 149] or [6, p. 351]. Finally, a proof of (iv) can be found in [8, p. 115].

3 Aigner’s theorem revised

In this section, we use the following special case of the Chinese remainder theorem.

Theorem 9. Let m_{1} and m_{2} be relatively prime positive integers. Then, for all integers a and b, the system of congruences

x ≡ a (mod m_{1}), x ≡ b (mod m_{2})

has a solution, and this solution is uniquely determined modulo m_{1}m_{2}.

For a proof of the Chinese remainder theorem see, for example [2, p. 79], or consult [6, p. 162].

Lemma 10. Let α, β ∈ ℕ and let gcd(α, β) = 1. Then, for every γ ∈ ℕ, there exists a c ∈ ℕ satisfying the conditions

gcd(c, γ) = 1, c ≡ β (mod α).  (4)

Proof. Let γ be a positive integer and let

d = max{δ ∈ ℕ : δ | γ, gcd(δ, α) = 1}.  (5)

The basic idea of the proof is as follows. We show that (4) is met by every solution c ∈ ℕ of the system of congruences

c ≡ 1 (mod d), c ≡ β (mod α).  (6)

First, observe that (7) immediately follows from (5).

If p is a prime satisfying p | \frac{γ}{d}, then p | α.  (7)

Next, it is obvious that implication (8) applies.

If c ∈ ℕ, p is a prime satisfying p | d and c ≡ 1 (mod d), then p ∤ c.  (8)

Assume now that c ∈ ℕ, p is a prime satisfying p | (γ/d) and that c ≡ β (mod α). Then, by (7), p | α. Therefore there exists a q ∈ ℕ such that α = pq. Hence, c ≡ β (mod pq), which implies c ≡ β (mod p). Using the hypothesis gcd(α, β) = 1 we obtain gcd(pq, β) = 1, and β ≢ 0 (mod p) follows. This together with c ≡ β (mod α) yields c ≢ 0 (mod p). Hence, (9).

If c ∈ ℕ, p is a prime satisfying p | \frac{γ}{d}, and c ≡ β (mod α), then p ∤ c.  (9)

Combining (8) with (9) we see that, if c ∈ ℕ, p is a prime satisfying p | γ = d · (γ/d), c ≡ 1 (mod d) and c ≡ β (mod α), then p ∤ c. Consequently, every solution c ∈ ℕ of the system of congruences (6) satisfies (4).

Since, by (5), gcd(d, α) = 1, the system of congruences (6) is solvable by Theorem 9. Moreover, if c satisfies (6), then c is uniquely determined modulo αd. The proof is complete.

Proposition 11. Let p be a prime and let a ∈ {1, …, p − 1}. Then there exists a primitive root g of p satisfying

ind_{g}(a) = \frac{p − 1}{ord_{p}(a)}.  (10)

Proof. Let h be a primitive root of p. Then there exists a unique s ∈ ℕ, 1 ≤ s ≤ ϕ(p) = p−1 such that a ≡ h^{s} (mod p), that is, s = ind_{h}(a). Next, let t be positive integer satisfying a^{t} ≡ 1 (mod p). From the assumptions made, it follows that

a^{t} ≡ 1 (mod p) ⟺ h^{st} ≡ 1 (mod p) ⟺ p − 1 | st.  (11)

Let us now put d := gcd(p − 1, s). Then we have

p − 1 | st ⟺ \frac{p − 1}{d} | \frac{ts}{d} ⟺ \frac{p − 1}{d} | t.  (12)

Combining (11) with (12), we obtain

a^{t} ≡ 1 (mod p) ⟺ \frac{p − 1}{d} | t,

which means that

ord_{p}(a) = \frac{p − 1}{d}.

We now use Lemma 10. Let us put α := (p − 1)/d and β := s/d. Since gcd(α, β) = 1, for each γ ∈ ℕ there exists a c ∈ ℕ satisfying (4). In particular for γ = p − 1, there exists a c ∈ ℕ such that

gcd(c, p − 1) = 1, c ≡ \frac{s}{d} (mod \frac{p − 1}{d})  (13)

and this c is uniquely determined modulo αd = p − 1.

From the second relation of (13) we receive cd ≡ s (mod p − 1). Since h is a primitive root of p, we have ord_{p}(h) = p − 1, thus, cd ≡ s (mod ord_{p}(h)). Next, applying part (ii) of Lemma 8, we get

cd ≡ s (mod ord_{p}(h)) ⟺ h^{cd} ≡ h^{s} (mod p) ⟺ h^{cd} ≡ a (mod p).  (14)

Let us now prove that g := h^{c} is a primitive root of p. Using part (iii) of Lemma 8 and applying the first part of (13), we obtain (15).

ord_{p}(g) = ord_{p}(h^{c}) = \frac{ord_{p}(h)}{gcd(c, ord_{p}(h))} = \frac{p − 1}{gcd(c, p − 1)} = p − 1.  (15)

Finally, from g ≡ h^{c} (mod p) it follows g^{d} ≡ h^{cd} (mod p) and, by (14), we have h^{cd} ≡ a (mod p). Hence, g^{d} ≡ a (mod p). This together with d = (p − 1)/ ord_{p}(a) yields ind_{g}(a) = (p − 1)/ ord_{p}(a), as required.

Remark 12. A primitive root g of a prime p satisfying (10) may not be determined uniquely. For example, if a = 2 and p = 31, then ord_{31}(2) = 5. By direct calculation, we can find that there exist exactly two primitive roots of 31 satisfying (10)—namely, ind_{12}(2) = ind_{21}(2) = 30/5 = 6.

Proposition 13. Let p be a prime and let a ∈ {1, …, p − 1}. Further, let g be a primitive root of p. Then we have

ind_{g}(a) | p − 1 if and only if ind_{g}(a) = \frac{p − 1}{ord_{p}(a)}.  (16)

Proof. Let ind_{g}(a) | p − 1. Then there is a c ∈ ℕ such that p − 1 = c · ind_{g}(a). Hence,

gcd(p − 1, ind_{g}(a)) = ind_{g}(a) · gcd(c, 1) = ind_{g}(a).  (17)

On the other hand, by part (iv) of Lemma 8, we have

gcd(p − 1, ind_{g}(a)) = \frac{p − 1}{ord_{p}(a)}.

This, together with (17), yields ind_{g}(a) = (p − 1)/ ord_{p}(a).

Since the converse implication is evident, the desired result follows.

Corollary 14. Let p be an odd prime and let p − 1 = 2^{r}u where r, u ∈ ℕ and 2 ∤ u. Then there exist a uniquely determined s ∈ ℕ ∪ {0} and t ∈ ℕ such that

0 ≤ s ≤ r, t | u and 2^{s}t = ind_{g}(2) for some primitive root g of p.  (18)

Proof. First, by part (i) of Lemma 8, we have ord_{p}(2) | p − 1 = 2^{r}u. This means that ord_{p}(2) = 2^{q}v for a q ∈ ℕ ∪ {0}, 0 ≤ q ≤ r and v ∈ ℕ satisfying v | u, 2 ∤ v. Let us now put s := r − q and t := u/v. Then s ∈ ℕ ∪ {0}, 0 ≤ s ≤ r, t ∈ ℕ, and t | u. Next, by Proposition 11, there exists at least one primitive root g of p such that

ind_{g}(2) = \frac{p − 1}{ord_{p}(2)} = \frac{2^{r}u}{2^{q}v} = 2^{s}t.

From this and from (16) it now follows that s and t are the only numbers satisfying (18).

We are now ready to properly understand Aigner’s Theorem 1, presented in the introduction. Theorem 1 can be formulated more exactly as follows.

Theorem 15. Let p be an odd prime and let p − 1 = 2^{r}u where r, u ∈ ℕ and 2 ∤ u. Then (i)–(iii) hold.

(i) There exist uniquely determined s ∈ ℕ ∪ {0} and t ∈ ℕ such that 0 ≤ s ≤ r, t | u and 2^{s}t = ind_{g}(2) for some primitive root g of p.

(ii) h(p) = r − s.

(iii) k(p) = ord_{u′}(2), where u′ = u/t.

Proof. Since the proof of (i) has already been given in Corollary 14, it is sufficient to prove (ii) and (iii).

We prove (ii). Let g be a primitive root of p and let ind_{g}(2) = 2^{s}t where s ∈ ℕ ∪ {0}, 0 ≤ s ≤ r, t ∈ ℕ, and t | u. Then by part (i) of Theorem 15, s and t are uniquely determined and we have

2 ≡ g^{2^{s}t} (mod p).  (19)

By raising both sides of (19) to 2^{j}, with j ∈ ℕ ∪ {0}, we obtain

2^{2^{j}} ≡ g^{2^{s+j}t} (mod p).  (20)

Let w ∈ ℕ ∪ {0} and let 0 ≤ w < r − s. Suppose that F_{w} ≡ F_{r−s} (mod p). Then we have

2^{2^{w}} ≡ 2^{2^{r−s}} (mod p).  (21)

We now use (20). Taking j = w, we obtain 2^{2^{w}} ≡ g^{2^{s+w}t} (mod p) and, taking j = r − s, we get 2^{2^{r−s}} ≡ g^{2^{r}t} (mod p). The last two congruences together with (21) lead to

g^{2^{s+w}t} ≡ g^{2^{r}t} (mod p).  (22)

Because g is a primitive root of p, we have ord_{p}(g) = p − 1. Applying part (ii) of Lemma 8, we now see that (22) is equivalent to

2^{w+s}t ≡ 2^{r}t (mod p − 1).  (23)

Furthermore, t | u implies that there exists a u′ ∈ ℕ such that u = tu′. This means that p − 1 = 2^{r}tu′. Since w < r − s, there exists an l ∈ ℕ such that w + l = r − s. Substituting r = s + w + l and p − 1 = 2^{s+w+l}tu′ into (23), we obtain

2^{w+s}t ≡ 2^{s+w+l}t (mod 2^{s+w+l}tu′).  (24)

From (24) now it follows that 2^{l} ≡ 1 (mod 2^{l}u′), which yields 2^{l} | 2^{l} − 1, a contradiction. Consequently, F_{w} ≢ F_{r−s} (mod p) for every w ∈ {0, …, r − s − 1}. Therefore,

h(p) ≥ #{0, …, r − s − 1} = r − s.  (25)

Now we show that there exists an l ∈ ℕ such that

F_{r−s} ≡ F_{r−s+l} (mod p), or equivalently, 2^{2^{r−s}} ≡ 2^{2^{r−s+l}} (mod p).  (26)

Again, applying (20), for j = r − s we obtain 2^{2^{r−s}} ≡ g^{2^{r}t} (mod p) and, for j = r − s + l, we get 2^{2^{r−s+l}} ≡ g^{2^{r+l}t} (mod p). Combining the last two congruences with (26) we get g^{2^{r}t} ≡ g^{2^{r+l}t} (mod p), which is, by part (ii) of Lemma 8, equivalent to 2^{r}t ≡ 2^{r+l}t (mod p−1). Because p − 1 = 2^{r}tu′, it is clear that 2^{l} ≡ 1 (mod u′) and, by part (i) of Lemma 8, we conclude that 2^{l} ≡ 1 (mod u′) holds for every l = c · ord_{u′}(2) where c ∈ ℕ. From (26) now it follows that h(p) ≤ r − s, which together with (25) proves (ii).

We prove (iii). First, taking l = ord_{u′}(2) in (26), we obtain

F_{r−s} ≡ F_{r−s+ord_{u′}(2)} (mod p),

which means that ord_{u′}(2) is the length of a period of (F_{n} mod p)_{n=0}^{∞}. Applying Lemma 6, we now get k(p) | ord_{u′}(2), and thus there exists a c ∈ ℕ such that k(p) = ord_{u′}(2)/c. Suppose that c ≠ 1. Then we have F_{r−s} ≡ F_{r−s+ord_{u′}(2)/c} (mod p), or equivalently,

2^{2^{r−s}} ≡ 2^{2^{r−s+ord_{u′} (2)/c}} (mod p).  (27)

Again, using (20), we find that (27) is equivalent to g^{2^{r}t} ≡ g^{2^{r+ord_{u′} (2)/c}t} (mod p) and, by part (ii) of Lemma 8, we get

2^{r}t ≡ 2^{r+ord_{u′}(2)/c}t (mod p − 1).  (28)

As p − 1 = 2^{r}tu′, (28) implies 2^{ord_{u′}(2)/c} ≡ 1 (mod u′). Hence, by part (i) of Lemma 8, we obtain ord_{u′}(2) | ord_{u′}(2)/c, which is a contradiction with c ≠ 1. This proves (iii).

Example 16. Let p = 41. Then p − 1 = 2^{3} · 5. Hence, r = 3 and u = 5. Next, we have ord_{41}(2) = 20 = 2^{2} · 5, and thus (p − 1)/ ord_{p}(2) = 2. By Proposition 11 we now obtain ind_{g}(2) = 2 for some primitive root g of 41 and, by direct calculation, we can find that ind_{g}(2) = 2 if and only if g ∈ {17, 24}. Since ind_{g}(2) = 2, we have s = 1, t = 1, and u′ = u/t = 5. By part (ii) of Theorem 15, we now get h(41) = r − s = 2 and, from part (iii) of Theorem 15, we obtain k(41) = ord_{5}(2) = 4. Finally, direct calculation verifies that

(F_{n} mod 41)_{n=0}^{∞} = (3, 5, 17, 11, 19, 38, 17, 11, 19, 38, …).

The following Lemma 17 is well-known.

Lemma 17. Let n ∈ ℕ ∪ {0} and let p be an odd prime. Then the Fermat number F_{n} is divisible by p if and only if ord_{p}(2) = 2^{n+1}.

A proof of Lemma 17 can be found, for example, in [4, p. 37].

Let F = {3, 5, 17, 257, 641, 65537, 114689, …} be the set of all primes p such that p is a divisor of some Fermat number F_{n}, where n ∈ ℕ ∪ {0}. Since every Fermat number F_{n} is divisible by at least one prime p and every two Fermat numbers are coprime by Goldbach theorem [4, p. 33], F is the infinite set.

Proposition 18. Let p be a prime, p ≠ 2. Then p ∈ F if and only if k(p) = 1.

Proof. Let p − 1 = 2^{r}u where r, u ∈ ℕ and let 2 ∤ u.

First, assume that p ∈ F. Then, by Lemma 17, ord_{p}(2) = 2^{q} for some q ∈ ℕ and, by part (i) of Lemma 8, we get q ≤ r. Hence,

\frac{p − 1}{ord_{p}(2)} = 2^{r−q}u.  (29)

On the other hand, by Corollary 14, there exist uniquely determined s ∈ ℕ ∪ {0} and t ∈ ℕ such that 0 ≤ s ≤ r, t | u and 2^{s}t = ind_{g}(2) for some primitive root g of p. Applying (10), we now obtain

\frac{p − 1}{ord_{p}(2)} = ind_{g}(2) = 2^{s}t.

This, along with (29), yields 2^{r−q}u = 2^{s}t. Since 2 ∤ u and 2 ∤ t, we have u = t. Hence, u/t = 1 and, by part (iii) of Theorem 15, we get k(p) = 1.

Conversely, let us assume that k(p) = 1. Then, by part (iii) of Theorem 15, we have ord_{u′}(2) = 1, which implies u′ = 1. As u′ = u/t, we have u = t and, by Corollary 14, ind_{g}(2) = 2^{s}u for some s ∈ ℕ ∪ {0} where 0 ≤ s ≤ r. Next, applying (10), we obtain

ord_{p}(2) = \frac{p − 1}{ind_{g}(2)} = \frac{2^{r}u}{2^{s}u} = 2^{r−s}.  (30)

Suppose now that r − s = 0. Then, by (30), ord_{p}(2) = 1 which yields 2 ≡ 1 (mod p), a contradiction. Hence, r − s ∈ ℕ and, r − s − 1 ∈ ℕ ∪ {0}. Applying Lemma 17 to (30) we now get p | F_{r−s−1}, which means that p ∈ F.

Example 19. Let p = 641. Then p − 1 = 2^{7} · 5. Hence, r = 7 and, u = 5. Since ord_{641}(2) = 2^{6}, by Lemma 17 we have 641 | F_{5}. As (p − 1)/ ord_{p}(2) = 10, by (10), we obtain ind_{g}(2) = 10 for some primitive root g of 641 and direct calculation verifies that ind_{g}(2) = 10 if and only if g ∈ {96, 108, 299, 304, 337, 342, 533, 545}. Hence, s = 1, t = 5 and u′ = u/t = 1. Applying part (ii) and (iii) of Theorem 15, we now get h(641) = r − s = 6 and k(641) = ord_{1}(2) = 1. Finally, we can verify that

(F_{n} mod 641)_{n=0}^{∞} = (3, 5, 17, 257, 155, 0, 2, 2, 2, 2, 2, …).

4 A simpler formulation of Aigner’s theorem

In this section we find a simpler formulation of Aigner’s result presented as Theorem 1. We show that the numbers h(p) and k(p) can be determined without resorting to the theory of primitive roots and indices. Our considerations are based only on the concept of a multiplicative order and its properties.

Theorem 20. Let p be a prime, p ≠ 2 and let ord_{p}(2) = 2^{v}w where v ∈ ℕ ∪ {0}, w ∈ ℕ and, 2 ∤ w. Then we have

(i) h(p) = v.

(ii) k(p) = ord_{w}(2).

Proof. We prove (i). First we show that

F_{v} ≡ F_{v+ord_{w}(2)} (mod p).  (31)

Since ord_{p}(2) = 2^{v}w, from part (i) of Definition 7, we get

2^{ord_{w}(2)} ≡ 1 (mod \frac{ord_{p}(2)}{2^{v}}) .  (32)

By multiplying (32) by 2^{v}, we receive 2^{v+ord_{w}(2)} ≡ 2^{v} (mod ord_{p}(2)), which is, by part (ii) of Lemma 8, equivalent to 2^{2^{v+ordw(2)}} ≡ 2^{2^{v}} (mod p). Hence, (31) follows.

Next, applying Lemma 6 to (31), we obtain v ≡ v + ord_{w}(2) (mod k(p)), which yields h(p) ≤ v and k(p) | ord_{w}(2). Specifically, by taking v = 0 in h(p) ≤ v, we get h(p) = 0. Let v ≠ 0 and let t ∈ {0, …, v −1}. Suppose now that F_{t} ≡ F_{v} (mod p). Then 2^{2^{t}} ≡ 2^{2^{v}} (mod p) and, using part (ii) of Lemma 8, we obtain 2^{t} ≡ 2^{v} (mod ord_{p}(2)). Since ord_{p}(2) = 2^{v}w we have 2^{v}w | 2^{t}(2^{v−t} − 1), which is a contradiction with v > t. Hence, F_{t} ≢ F_{v} (mod p) for every t ∈ {0, …, v − 1}. This means that h(p) ≥ #{0, …, v − 1} = v, which along with h(p) ≤ v, proves (i).

We prove (ii). By (31), ord_{w}(2) is the length of the period of (F_{n} mod p)_{n=0}^{∞} and, by Lemma 6, we have k(p) | ord_{w}(2). Therefore, there exists an s ∈ ℕ such that k(p) = ord_{w}(2)/s. Suppose that s ≠ 1. From F_{v} ≡ F_{v+k(p)} (mod p) now it follows that 2^{2^{v}} ≡ 2^{2^{v+ordw(2)/s}} (mod p) and, by part (ii) of Lemma 8, we obtain

2^{v} ≡ 2^{v+ord_{w}(2)/s} (mod ord_{p}(2)).

This, together with ord_{p}(2) = 2^{v}w, yields 2^{ord_{w}(2)/s} ≡ 1 (mod w). Applying part (i) of Lemma 8, we now get ord_{w}(2) | ord_{w}(2)/s, which is a contradiction. Hence, we have s = 1 and the desired result follows.

5 Some new results concerning the numbers h(p)

In this section, we take a closer look at the properties of the numbers h(p) and show that part (i) of Theorem 20 can be refined substantially. We start by recalling some known properties of the quadratic character of 2.

Theorem 21. Let p be a prime, p ≠ 2. Then we have

(\frac{2}{p}) ≡ 2^{\frac{p−1}{2}} (mod p)  (33)

and,

(\frac{2}{p}) = (−1)^{\frac{p^{2}−1}{8}} = \begin{cases}1, if p ≡ 1, 7 (mod 8); \\ −1, if p ≡ 3, 5 (mod 8). \end{cases}  (34)

A proof of (33) can be found, for example, in the books [2, p. 176] or [6, p. 418] and, for a proof of (34), see [2, p. 180] or [6, p. 422].

Theorem 22. For every prime p, (i)–(iii) hold.

(i) If p ≡ 7 (mod 8), then 2 ∤ ord_{p}(2). Consequently, h(p) = 0.

(ii) If p ≡ 3 (mod 8), then 2 ∥ ord_{p}(2). Consequently, h(p) = 1.

(iii) If p ≡ 5 (mod 8), then 4 ∥ ord_{p}(2). Consequently, h(p) = 2.

Proof. We prove (i). If p ≡ 7 (mod 8), then p = 8α + 7 for an α ∈ ℕ ∪ {0}. Hence, 2^{(p−1)/2} = 2^{4α+3}. On the other hand, by Theorem 21, 2^{(p−1)/2} ≡ 1 (mod p). This means that 2^{4α+3} ≡ 1 (mod p). By part (i) of Lemma 8, we now obtain ord_{p}(2) | 4α + 3. Hence, 2 ∤ ord_{p}(2). Finally, applying part (i) of Theorem 20, we get h(p) = 0.

We prove (ii). If p ≡ 3 (mod 8), then p = 8α + 3 for an α ∈ ℕ ∪ {0}. Hence, 2^{(p−1)/2} = 2^{4α+1}. On the other hand, by Theorem 21, 2^{(p−1)/2} ≡ −1 (mod p). This means that 2^{4α+1} ≡ −1 (mod p). Let ord_{p}(2) = u. Suppose now that 2 ∤ u. Then, by part (i) of Lemma 8, u | p − 1 = 2(4α + 1). This means that u | 4α + 1. Therefore, there exists a t ∈ ℕ such that 4α +1 = tu. Hence, 2^{4α+1} = (2^{u})^{t} ≡ 1^{t} ≡ 1 (mod p), which is a contradiction. Thus, we have 2 | u, which, along with u | 2(4α + 1), yields 2 ∥ ord_{p}(2). Applying part (i) of Theorem 20, we now obtain h(p) = 1.

We prove (iii). If p ≡ 5 (mod 8), then p = 8α + 5 for an α ∈ ℕ ∪ {0}. Hence, 2^{(p−1)/2} = 2^{4α+2}. On the other hand, by Theorem 21, we have 2^{(p−1)/2} ≡ −1 (mod p). This means that 2^{4α+2} ≡ −1 (mod p). Let ord_{p}(2) = u. Suppose now that 4 ∤ u. Then, by part (i) of Lemma 8, u | p − 1 = 4(2α + 1) and u | 2α + 1 follows. Therefore, there exists a t ∈ ℕ such that 2α + 1 = tu. Hence, 2^{4α+2} = (2^{u})^{2t} ≡ 1^{2t} ≡ 1 (mod p), which is a contradiction. Thus, 4 | u, which, along with u | 4(2α+1), yields 4 ∥ ord_{p}(2). Applying part (i) of Theorem 20, we now obtain h(p) = 2.

The case of primes p ≡ 1 (mod 8) solves Theorem 23.

Theorem 23. For every v ∈ ℕ ∪ {0}, there exists at least one prime p ≡ 1 (mod 8) such that h(p) = v.

Proof. Let us divide the proof into two parts. First, we show that the conclusion of Theorem 23 is true for every v ∈ {0, 1, 2}. Direct calculation verifies that (i)–(iii) hold.

(i) If p = 73, then p ≡ 1 (mod 8) and h(73) = 0.

(ii) If p = 281, then p ≡ 1 (mod 8) and h(281) = 1.

(iii) If p = 41, then p ≡ 1 (mod 8) and h(41) = 2.

The values of the primes p ≡ 1 (mod 8) shown in (i)–(iii) are the least values for which the equality h(p) = v occurs. Secondly, we prove that Theorem 23 also applies for every v ∈ ℕ ∪ {0}, v ≥ 3. Let p be a prime such that p | F_{v−1} where v ≥ 3. Then, by Lemma 17, ord_{p}(2) = 2^{v}. This, along with part (i) of Theorem 20, yields h(p) = v. Now it is clear from Theorem 22 that p = 2 or p ≡ 1 (mod 8). Since h(2) = 0, we have p ≡ 1 (mod 8), as required.

We conclude our study of Fermat numbers by presenting the tables of h(p) and k(p) for all primes p < 1000. The tables are shown in the Appendix.

6 Acknowledgment

The author thanks the anonymous referee for carefully reading the manuscript.

A Appendix: Tables of the values of h(p) and k(p) for p < 1000

\begin{matrix}p & h(p) & k(p) & p & h(p) & k(p) & p & h(p) & k(p) \\ 2 & 0 & 1 & 3 & 1 & 1 & 5 & 2 & 1 \\ 7 & 0 & 2 & 11 & 1 & 4 & 13 & 2 & 2 \\ 17 & 3 & 1 & 19 & 1 & 6 & 23 & 0 & 10 \\ 29 & 2 & 3 & 31 & 0 & 4 & 37 & 2 & 6 \\ 41 & 2 & 4 & 43 & 1 & 3 & 47 & 0 & 11 \\ 53 & 2 & 12 & 59 & 1 & 28 & 61 & 2 & 4 \\ 67 & 1 & 10 & 71 & 0 & 12 & 73 & 0 & 6 \\ 79 & 0 & 12 & 83 & 1 & 20 & 89 & 0 & 10 \\ 97 & 4 & 2 & 101 & 2 & 20 & 103 & 0 & 8 \\ 107 & 1 & 52 & 109 & 2 & 6 & 113 & 2 & 3 \\ 127 & 0 & 3 & 131 & 1 & 12 & 137 & 2 & 8 \\ 139 & 1 & 22 & 149 & 2 & 36 & 151 & 0 & 4 \\ 157 & 2 & 12 & 163 & 1 & 54 & 167 & 0 & 82 \end{matrix}

\begin{matrix}p & h(p) & k(p) & p & h(p) & k(p) & p & h(p) & k(p) \\ 173 & 2 & 14 & 179 & 1 & 11 & 181 & 2 & 12 \\ 191 & 0 & 36 & 193 & 5 & 2 & 197 & 2 & 21 \\ 199 & 0 & 30 & 211 & 1 & 12 & 223 & 0 & 36 \\ 227 & 1 & 28 & 229 & 2 & 18 & 233 & 0 & 28 \\ 239 & 0 & 24 & 241 & 3 & 2 & 251 & 1 & 20 \\ 257 & 4 & 1 & 263 & 0 & 130 & 269 & 2 & 66 \\ 271 & 0 & 36 & 277 & 2 & 11 & 281 & 1 & 12 \\ 283 & 1 & 23 & 293 & 2 & 9 & 307 & 1 & 8 \\ 311 & 0 & 20 & 313 & 2 & 12 & 317 & 2 & 39 \\ 331 & 1 & 4 & 337 & 0 & 6 & 347 & 1 & 172 \\ 349 & 2 & 28 & 353 & 3 & 10 & 359 & 0 & 178 \\ 367 & 0 & 60 & 373 & 2 & 10 & 379 & 1 & 18 \\ 383 & 0 & 95 & 389 & 2 & 48 & 397 & 2 & 10 \\ 401 & 3 & 20 & 409 & 2 & 8 & 419 & 1 & 90 \\ 421 & 2 & 12 & 431 & 0 & 14 & 433 & 3 & 6 \\ 439 & 0 & 9 & 443 & 1 & 24 & 449 & 5 & 3 \\ 457 & 2 & 18 & 461 & 2 & 44 & 463 & 0 & 30 \\ 467 & 1 & 29 & 479 & 0 & 119 & 487 & 0 & 162 \\ 491 & 1 & 84 & 499 & 1 & 82 & 503 & 0 & 50 \\ 509 & 2 & 7 & 521 & 2 & 12 & 523 & 1 & 84 \\ 541 & 2 & 36 & 547 & 1 & 12 & 557 & 2 & 138 \\ 563 & 1 & 70 & 569 & 2 & 35 & 571 & 1 & 18 \\ 577 & 4 & 6 & 587 & 1 & 292 & 593 & 2 & 36 \\ 599 & 0 & 132 & 601 & 0 & 20 & 607 & 0 & 100 \\ 613 & 2 & 24 & 617 & 1 & 30 & 619 & 1 & 102 \\ 631 & 0 & 12 & 641 & 6 & 1 & 643 & 1 & 106 \\ 647 & 0 & 72 & 653 & 2 & 162 & 659 & 1 & 69 \\ 661 & 2 & 20 & 673 & 4 & 2 & 677 & 2 & 156 \\ 683 & 1 & 10 & 691 & 1 & 44 & 701 & 2 & 60 \\ 709 & 2 & 58 & 719 & 0 & 179 & 727 & 0 & 110 \\ 733 & 2 & 60 & 739 & 1 & 20 & 743 & 0 & 156 \\ 751 & 0 & 100 & 757 & 2 & 18 & 761 & 2 & 36 \\ 769 & 7 & 2 & 773 & 2 & 96 & 787 & 1 & 130 \\ 797 & 2 & 99 & 809 & 2 & 100 & 811 & 1 & 36 \\ 821 & 2 & 20 & 823 & 0 & 68 & 827 & 1 & 174 \\ 829 & 2 & 66 & 839 & 0 & 418 & 853 & 2 & 70 \\ 857 & 2 & 106 & 859 & 1 & 60 & 863 & 0 & 43 \\ 877 & 2 & 18 & 881 & 0 & 20 & 883 & 1 & 42 \\ 887 & 0 & 442 & 907 & 1 & 30 & 911 & 0 & 12 \\ 919 & 0 & 24 & 929 & 4 & 28 & 937 & 0 & 12 \\ 941 & 2 & 92 & 947 & 1 & 70 & 953 & 2 & 8 \\ 967 & 0 & 66 & 971 & 1 & 48 & 977 & 3 & 60 \\ 983 & 0 & 490 & 991 & 0 & 60 & 997 & 2 & 82 \end{matrix}

14

References

[1] A. Aigner, Über Primzahlen, nach denen (fast) alle Fermatschen Zahlen quadratische Nichtreste sind, Monatsh. Math. 101 (1986), 85–93.

[2] D. M. Burton, Elementary Number Theory, 7th edition, McGraw-Hill, 2011.

[3] E. Deza, Mersenne Numbers and Fermat Numbers, Selected Chapters of Number Theory: Special Numbers, World Scientific, 2021.

[4] M. Křížek, F. Luca, and L. Somer, 17 Lectures on Fermat Numbers, From Number Theory to Geometry, Canadian Mathematical Society, Springer, 2001.

[5] B. Rittaud and A. Heeffer, The pigeonhole principle, two centuries before Dirichlet, Math. Intell. 36 (2014), 27–29.

[6] K. H. Rosen, Elementary Number Theory and Its Applications, Sixth Edition, Addison-Wesley, 2011.

[7] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, available at

   https://oeis.org, 2024.

[8] I. M. Vinogradov, Elements of Number Theory, Dover Publications, 1954.

2020 Mathematics Subject Classification: Primary 11B50; Secondary 11B83, 11A41. Keywords: Fermat number, modular periodicity, pre-period, primitive period.

(Concerned with sequences \underline{A000215} and \underline{A102742}.)

Received June 18 2024; revised version received April 29 2025. Published in Journal of Integer Sequences, December 15 2025.

Return to Journal of Integer Sequences home page.