🔢 mathematics

Sophie Germain Primes and the Totient of Fibonacci Numbers

This paper investigates the set of residue classes modulo the Pisano period for which a prime $q$ divides the Euler totient of Fibonacci numbers, proving that for Sophie Germain primes satisfying specific divisibility conditions, this set forms a nonempty arithmetic progression with odd cardinality, while establishing a converse relationship that links the existence of such sets to the primality of $2q+1$ .

Original authors: Aradhya Goel (Indian Institute of Technology, Kanpur)

Published 2026-04-21

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Aradhya Goel (Indian Institute of Technology, Kanpur)

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery involving two famous number families: the Fibonacci numbers (a sequence where each number is the sum of the two before it: 1, 1, 2, 3, 5, 8, 13...) and the Sophie Germain primes (a special club of prime numbers where, if you double the number and add one, you get another prime).

This paper is a mathematical investigation into how these two families interact, specifically looking at a property called the Euler Totient function (which counts how many numbers "play nice" with a given number).

Here is the story of the paper, broken down into simple concepts and analogies.

1. The Mystery: The "Divisibility Club"

The author, Aradhya Goel, is studying a specific group of numbers called $S(q)$ .

The Setup: Imagine you have a special prime number, $q$ . You look at the Fibonacci numbers and ask: "For which positions in the sequence does the Totient function of that Fibonacci number get divided evenly by $q$ ?"
The Pattern: Fibonacci numbers repeat their remainders in a cycle (like the hands of a clock). This cycle length is called the Pisano period.
The Question: If you pick a specific "time" on this clock (a residue class), does every Fibonacci number at that time have a Totient divisible by $q$ ?
The Discovery: The set $S(q)$ is the collection of all those "times" on the clock where the divisibility rule holds true.

2. The Big Reveal: The "Double-and-Add-One" Key

The paper proves a stunning connection: The set $S(q)$ is not empty (meaning the pattern exists) if and only if $q$ is a Sophie Germain prime AND a specific condition is met.

Think of it like a lock and a key:

The Lock: The Fibonacci sequence's behavior modulo $q$ .
The Key: The number $p = 2q + 1$ .
The Rule: If $q$ is a Sophie Germain prime (so $p$ is also prime), and if the "rank" of $p$ in the Fibonacci sequence divides the cycle length of $q$ , then the "Divisibility Club" ( $S(q)$ ) opens up.

The "Uniqueness" Twist:
The author proves that if this club opens, the only key that fits is the one where you double $q$ and add 1. You can't use $3q+1$ , $4q+1$ , or any other multiple. It's exclusively the "Double-and-Add-One" rule. This was verified for thousands of numbers, and the author believes it's true for all numbers.

3. The Shape of the Solution: A Perfect Line

When the club is open, the "times" on the clock ( $S(q)$ ) aren't scattered randomly. They form a perfect arithmetic progression.

Analogy: Imagine a clock face with 100 hours. If the club is open, the valid hours might be 0, 25, 50, and 75. They are equally spaced.
The paper calculates exactly how many valid hours there are and proves that for most large Sophie Germain primes, this count is an odd number.

4. The "Magic Number" Constraint

The paper finds a very strict rule for which Sophie Germain primes can unlock this club.

If $q$ is a large enough Sophie Germain prime that unlocks the club, $q$ must leave a remainder of 8 when divided by 15.
Analogy: Imagine a bouncer at a club. Even if you have a VIP pass (being a Sophie Germain prime), the bouncer checks your ID. If your ID number doesn't end in a specific pattern (specifically, if it's not $8 \pmod{15}$ ), you get turned away.
This is a huge restriction. Out of all possible prime numbers, only a tiny fraction satisfy this specific "8 mod 15" rule.

5. The Grand Conjecture: A Two-Way Street

The author makes a bold guess (a conjecture):

Current Proof: If $q$ is a Sophie Germain prime with the right properties, then the club $S(q)$ exists.
The Conjecture: If the club $S(q)$ exists, then $q$ must be a Sophie Germain prime.
Why it matters: If this is true, it means the existence of this specific Fibonacci pattern is a perfect fingerprint for Sophie Germain primes. It creates a bridge between two seemingly unrelated areas of math.

6. The "What If" Scenario

The paper concludes with a fascinating implication:

If there are infinitely many Sophie Germain primes (a famous unsolved problem in math), then there are infinitely many primes $q$ that satisfy this very specific Fibonacci condition: $(2q + 1)$ divides the Fibonacci number at the end of the cycle.
This turns a problem about prime numbers into a problem about the Fibonacci sequence, and vice versa.

Summary in a Nutshell

The paper shows that Sophie Germain primes are the "secret keys" that unlock a specific, repeating pattern in the Fibonacci sequence.

If you have the right key ( $q$ is Sophie Germain), you get a perfect, evenly spaced pattern of numbers ( $S(q)$ ).
The pattern only works if the key number $q$ follows a strict rule (it must be $8 \pmod{15}$ ).
The author suspects that only these keys work, meaning if you see this pattern, you know for sure you are dealing with a Sophie Germain prime.

The author has checked this logic against 50,000 numbers, and it holds up perfectly every time. It's a beautiful example of how different branches of number theory (primes, sequences, and divisibility) are secretly dancing to the same rhythm.

1. Problem Statement and Motivation

The paper investigates the arithmetic properties of Fibonacci numbers ( $F_m$ ) in relation to Euler's totient function ( $\phi$ ) and Sophie Germain primes. Specifically, the author defines a set $S(q)$ for an odd prime $q$ :
$S(q) = \{ r \pmod{\pi(q)} : q \mid \phi(F_m) \text{ for all } m \equiv r \pmod{\pi(q)} \}$
where $\pi(q)$ is the Pisano period (the period of Fibonacci numbers modulo $q$ ).

The central problem is to characterize the conditions under which $S(q)$ is non-empty. The paper explores the deep connection between the non-emptiness of $S(q)$ and the property of $q$ being a Sophie Germain prime (a prime $q$ such that $p = 2q + 1$ is also prime). The study aims to determine if the divisibility condition $q \mid \phi(F_m)$ for an entire residue class forces $q$ to be a Sophie Germain prime and if the witnessing prime factor must be $2q+1$ .

2. Methodology

The author employs a combination of:

Algebraic Number Theory: Utilizing properties of Lucas sequences, rank of apparition ( $z(p)$ ), and Pisano periods ( $\pi(q)$ ). Key tools include the characteristic polynomial of the Fibonacci recurrence, properties of the Legendre symbol $\left(\frac{5}{p}\right)$ , and the structure of finite fields $\mathbb{F}_p$ and $\mathbb{F}_{p^2}$ .
Divisibility Analysis: Rigorous analysis of the divisibility relations between $z(p)$ , $\pi(q)$ , and $p-1$ or $p+1$ based on quadratic reciprocity.
Computational Verification: Extensive numerical checks for primes $q \le 50,000$ to verify conjectures, factorize Fibonacci numbers up to $F_{999}$ (using Brillhart–Montgomery–Silverman tables), and test specific ranges of parameters.
Generalization: Extending results from Fibonacci numbers ( $U_n(1, -1)$ ) to arbitrary Lucas sequences $U_n(P, Q)$ with non-square discriminant.

3. Key Contributions and Theoretical Results

A. Characterization of $S(q)$

Sufficient Condition (Theorem 3.1 & 4.1): If there exists a prime $p \equiv 1 \pmod q$ such that the rank of apparition $z(p)$ divides the Pisano period $\pi(q)$ , then $S(q)$ is non-empty. Specifically, if $q$ is a Sophie Germain prime and $z(2q+1) \mid \pi(q)$ , then $S(q) \neq \emptyset$ .
Uniqueness of the Witnessing Prime (Theorem 4.2): The paper proves that if a prime $p = kq + 1$ satisfies $z(p) \mid \pi(q)$ , then for $k \le 31$ (and computationally up to $k=100$ ), it must be that $k=2$ . Thus, $p = 2q + 1$ . This implies that the only primes capable of "witnessing" the divisibility condition in this context are those associated with Sophie Germain primes.
Structure of $S(q)$ (Theorem 5.1): When $q$ is a Sophie Germain prime and $z(2q+1) \mid \pi(q)$ , $S(q)$ forms a non-empty arithmetic progression in $\mathbb{Z}/\pi(q)\mathbb{Z}$ with common difference $z(2q+1)$ . The cardinality is $|S(q)| = \pi(q)/z(2q+1)$ .

B. Parity and Congruence Constraints

Legendre Symbols (Theorem 6.1 & Lemma 6.3): For $q > 5$ , if $S(q) \neq \emptyset$ , then $\left(\frac{5}{2q+1}\right) = -1$ and $\left(\frac{5}{q}\right) = -1$ .
Parity (Theorem 6.2): The cardinality $|S(q)|$ is always odd for $q > 5$ .
Modular Constraint (Theorem 7.1): A necessary condition for $S(q) \neq \emptyset$ (with $q > 5$ ) is that $q \equiv 8 \pmod{15}$ . This restricts Sophie Germain primes satisfying the condition to a specific residue class.

C. The Converse Conjecture

Conjecture 4.4: The paper conjectures that $S(q) \neq \emptyset$ implies the existence of a prime $p \equiv 1 \pmod q$ with $z(p) \mid \pi(q)$ .
Implication: If true, this establishes a full equivalence: $S(q) \neq \emptyset$ if and only if $q$ is a Sophie Germain prime and $z(2q+1) \mid \pi(q)$ .
Verification: This conjecture has been verified for all odd primes $q \le 50,000$ . In every case where $S(q) \neq \emptyset$ , the witness was exactly $p = 2q + 1$ .

4. Computational Findings

Density: Among the 669 Sophie Germain primes $q \le 50,000$ , approximately 23.9% satisfy the condition $z(2q+1) \mid \pi(q)$ (i.e., $S(q) \neq \emptyset$ ).
Residue Classes: All verified primes $q > 5$ with $S(q) \neq \emptyset$ satisfy $q \equiv 8 \pmod{15}$ . They split into two classes modulo 60: $q \equiv 23 \pmod{60}$ and $q \equiv 53 \pmod{60}$ .
Cardinality Values: The ratio $\pi(q)/z(2q+1)$ takes values in the set $\{1, 2, 3, 7, 9, 21, 33, 43\}$ , all of which are odd (except for the trivial case $q=5$ ).

5. Generalization to Lucas Sequences

The results are generalized to Lucas sequences $U_n(P, Q)$ with discriminant $D = P^2 - 4Q$ (non-square).

The condition $S(q) \neq \emptyset$ is linked to the rank of apparition $\alpha(2q+1)$ dividing the period $\omega(q)$ .
The congruence constraint generalizes to $q \equiv 2 \pmod 3$ and specific Legendre symbol conditions involving $D$ .
For specific $D$ $D$ values:
- $D=5$ (Fibonacci): $q \equiv 8 \pmod{15}$ .
- $D=8$ (Pell): $q \equiv 5 \pmod{24}$ .
- $D=13$ : $q \pmod{39} \in \{2, 5, 20\}$ .

6. Significance and Implications

Sophie Germain Conjecture Reformulation: The paper provides a purely Fibonacci-theoretic reformulation of the infinitude of Sophie Germain primes. If there are infinitely many Sophie Germain primes, and if the condition $z(2q+1) \mid \pi(q)$ holds for infinitely many of them (computationally supported at ~23.9%), then there are infinitely many primes $q \equiv 8 \pmod{15}$ such that $(2q+1) \mid F_{\pi(q)}$ .
New Arithmetic Constraints: The discovery that $S(q) \neq \emptyset$ forces $q \equiv 8 \pmod{15}$ and $|S(q)|$ to be odd provides new, non-trivial constraints on the distribution of these primes.
Open Problems: The paper identifies several open questions, including a purely algebraic proof for the uniqueness of the witnessing prime (Theorem 4.2) for all $k$ , and a density formula for the 23.9% occurrence rate using Bateman–Horn–Chebotarev heuristics.

Conclusion

This work bridges the gap between the distribution of prime factors in Fibonacci sequences and the existence of Sophie Germain primes. It establishes that the divisibility of $\phi(F_m)$ by a prime $q$ across a full residue class is a strong indicator of $q$ being a Sophie Germain prime, with the witnessing prime factor being exactly $2q+1$ . The results are supported by rigorous algebraic proofs for small cases and extensive computational verification, offering a new perspective on the structure of Fibonacci numbers and their interaction with multiplicative functions.