🔢 mathematics

Product of powers of distinct primes as sums of Fibonacci numbers

This paper investigates the Diophantine equation $F_n+F_m=p^xq^y$ for distinct primes $p$ and $q$ , identifying all pairs $(q,p)$ with $q\le \min\{1000,p\}$ that admit at least two distinct solutions in positive integers.

Original authors: Herbert Batte, Florian Luca, Volker Ziegler

Published 2026-02-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Herbert Batte, Florian Luca, Volker Ziegler

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 have a magical machine that spits out numbers in a very specific pattern: 0, 1, 1, 2, 3, 5, 8, 13, 21... This is the famous Fibonacci sequence. You can get the next number by adding the two previous ones together.

Now, imagine you have a different machine that only spits out "pure" numbers made by multiplying prime numbers (like 2, 3, 5, 7, 11, etc.) together. For example, $12$ is $2^2 \times 3$ , and $18$ is $2 \times 3^2$ .

The Big Question:
The authors of this paper asked a tricky puzzle: Can you add two Fibonacci numbers together to get a number that is made of only two specific prime numbers?

For instance, can $F_n + F_m$ equal something like $2^x \times 3^y$ ? Or $7^x \times 19^y$ ?

They wanted to know: How many times can this happen?

Does it happen once?
Does it happen twice?
Or does it happen a million times?

The Detective Work: How They Solved It

The authors, Herbert Batte, Florian Luca, and Volker Ziegler, acted like mathematical detectives. They didn't just guess; they used a massive toolkit of advanced math to hunt down the answer. Here is how they did it, broken down into simple steps:

1. The "Fence" (Setting the Boundaries)

First, they realized that if the Fibonacci numbers get too huge, the equation breaks. It's like trying to fit a giant elephant into a tiny car.

They used a powerful mathematical tool called Baker's Method (think of it as a super-precise ruler) to prove that the Fibonacci numbers involved couldn't be infinitely large.
They calculated a "fence" around the problem. They proved that if a solution exists, the Fibonacci numbers must be smaller than a number with hundreds of digits.
Analogy: Imagine you are looking for a lost coin in a field. The field is huge, but you know for a fact the coin is somewhere within the first 100 meters. You don't need to search the whole country.

2. The "Squeeze" (Shrinking the Search)

Even with a fence of 100 meters, searching every inch is too hard for a computer. So, they used a technique called LLL Reduction (named after the three mathematicians who invented it).

Analogy: Imagine you have a giant, tangled ball of yarn. You want to find a specific knot. The LLL algorithm is like a magical hand that instantly untangles the yarn and shrinks the ball down to the size of a marble, making the knot easy to spot.
They used this to shrink their "fence" from hundreds of digits down to numbers small enough for a computer to check in a reasonable amount of time.

3. The "Fingerprint" (Checking the Candidates)

Once they had a small list of possible numbers, they wrote a computer program (using a tool called SageMath) to check every single possibility.

They looked at every pair of Fibonacci numbers that added up to a number made of two primes.
They checked if that sum appeared more than once with different powers of the primes.

The Big Discovery

After all this heavy lifting, they found the answer.

Most pairs of primes never work more than once.
If you pick two random primes (say, 13 and 17), you will almost never find two different ways to add Fibonacci numbers to get a result made only of 13s and 17s.

However, there are exactly 6 special "VIP" pairs of primes where this magic happens twice (or more):

3 and 2
5 and 2
7 and 2
7 and 3
17 and 2
19 and 2

For these specific pairs, the authors listed every single time it happens.

Example: For the pair 3 and 2, the sum $F_4 + F_4$ (which is $3+3=6$ ) is $3^1 \times 2^1$ . But so is $F_5 + F_1$ ( $5+1=6$ ). That's two different ways to get the same "prime-only" number!

Why Does This Matter?

You might ask, "Who cares if $F_n + F_m$ equals $3^x 2^y$ ?"

In the world of mathematics, these puzzles are like training exercises for the brain.

They help us understand the hidden structure of numbers.
They test the limits of our most powerful mathematical tools (like the ones used in cryptography to keep your bank data safe).
It's like solving a Sudoku puzzle: the puzzle itself might not build a bridge, but the logic you use to solve it helps engineers build better bridges.

The Takeaway

This paper is a story of limiting the infinite. The authors took a problem that could theoretically go on forever, built a mathematical fence around it, shrank the search area with a digital sledgehammer, and finally found the tiny, rare islands where the magic happens.

They proved that while the universe of numbers is vast and chaotic, there are very strict rules governing how Fibonacci numbers and prime numbers can dance together. And for almost every pair of partners, they only dance together once. Only six special pairs get to dance twice.

1. Problem Statement

The paper investigates the Diophantine equation:
$F_n + F_m = p^x q^y$
where:

$F_n$ and $F_m$ are Fibonacci numbers with indices $n \ge m \ge 0$ .
$p$ and $q$ are fixed distinct prime numbers.
$x$ and $y$ are positive integers ( $xy \neq 0$ ).
The case $n=2$ or $m=2$ is disregarded because $F_1 = F_2 = 1$ , which creates trivial ambiguities in the representation.

The primary objective is to determine all pairs of distinct primes $(q, p)$ with $q \le \min\{1000, p\}$ such that the equation admits at least two distinct solutions in terms of the exponent pairs $(x, y)$ (and their corresponding indices $n, m$ ).

2. Methodology

The authors employ a combination of advanced number-theoretic tools and computational algorithms to solve the problem. The methodology proceeds in several stages:

A. Theoretical Framework

Binet Formulas and Approximations: The authors utilize the Binet formulas for Fibonacci ( $F_n$ ) and Lucas ( $L_n$ ) numbers involving the golden ratio $\alpha = \frac{1+\sqrt{5}}{2}$ . They establish tight inequalities to approximate $F_n + F_m$ in terms of powers of $\alpha$ .
Linear Forms in Logarithms (Baker's Method): The core theoretical tool is Matveev's theorem (Theorem 2.3), which provides explicit lower bounds for non-zero linear forms in logarithms of algebraic numbers. This is used to derive upper bounds for the variables $n, m, x, y$ .
Primitive Divisor Theorems: Carmichael's theorem and properties of primitive divisors of Fibonacci and Lucas numbers are used to eliminate cases where the prime factorization structure is impossible.
Zeckendorf Representations: The uniqueness of the representation of integers as sums of non-consecutive Fibonacci numbers is used to handle cases where $n=m$ or $n=m+1$ .

B. Reduction Techniques

The initial upper bounds derived from Matveev's theorem are astronomically large (e.g., $n < 10^{352}$ ). To make the problem computationally tractable, the authors apply reduction methods:

Continued Fractions (Legendre's Lemma): Used to reduce bounds for linear forms in two variables.
LLL-Algorithm (Lenstra–Lenstra–Lovász): Used to find short vectors in lattices. This is the primary method for reducing the bounds on $n$ and the differences $d = n-m$ . The authors construct approximation lattices based on the linear forms derived from the Diophantine equation and apply the LLL algorithm to find much tighter bounds (e.g., reducing $n$ from $10^{352}$ to $n < 1000$ ).

C. Computational Search

Once the bounds on $n$ are reduced to a manageable range (typically $n < 2000$ or slightly higher depending on the prime $p$ ), the authors use SageMath to perform exhaustive searches.

They iterate through valid $n, m$ pairs.
They compute $S = F_n + F_m$ .
They check if $S$ can be factored into the form $p^x q^y$ for fixed primes $p, q$ .
Specialized algorithms (using Fermat's Little Theorem and matrix exponentiation for modular arithmetic) are used to efficiently check for prime power factors without full factorization of massive numbers.

3. Key Contributions and Case Analysis

The paper divides the proof into two main cases based on the size of the smaller prime $q$ :

Case 1: Small Primes ( $2 \le q < p \le 1000$ )

The authors establish an absolute bound $n < 2 \cdot 10^{40}$ using Lemma 3.2.
Through iterative LLL reductions, this bound is drastically reduced to $n \le 378$ .
A computer search over this range confirms that only specific pairs $(p, q)$ yield multiple solutions.

Case 2: Large Primes ( $p > 1000$ )

This case is more complex and is split into sub-cases based on $q$ :

Sub-case $q \neq 5$ : The authors analyze the multiplicative independence of terms involving $\alpha$ and $\sqrt{5}$ . They use a refined strategy to check for multiplicative dependencies only for promising candidates, significantly reducing the search space. They prove that for $q \neq 5$ , no new solutions exist beyond those found in the small prime case.
Sub-case $q = 5$ : This requires handling the specific properties of the prime 5 in the Fibonacci sequence (Pisano periods).
- They analyze cases where $m=0$ or $d=n-m$ is even, and where $d$ is odd.
- They derive bounds such as $n < 10^{53}$ and subsequently reduce them using LLL and continued fractions.
- A specialized lifting algorithm based on the periodicity of Fibonacci numbers modulo $5^k$ is used to bound the exponent $y$ .
- Despite the large initial bounds, the LLL reduction combined with the specific structure of the equation for $q=5$ eventually forces $n$ to be very small ( $n \le 21$ ), where no new solutions are found.

4. Main Results

The paper proves Theorem 1.1, which completely classifies the pairs of primes $(p, q)$ with $q \le 1000$ that allow the equation $F_n + F_m = p^x q^y$ to have at least two distinct solutions.

The only such pairs are:
$S = \{(3, 2), (5, 2), (7, 2), (7, 3), (17, 2), (19, 2)\}$

The specific solutions (sums of Fibonacci numbers) for these pairs are:

$(3, 2)$ : $3^x 2^y = F_4+F_4, F_5+F_1, F_7+F_5, F_8+F_4, F_9+F_3, F_{11}+F_{10}, F_{12}+F_0, F_{12}+F_{12}, F_{13}+F_{10}, F_{14}+F_{10}, F_{18}+F_6$ .
$(5, 2)$ : $5^x 2^y = F_5+F_5, F_6+F_3, F_{16}+F_7, F_{17}+F_4$ .
$(7, 2)$ : $7^x 2^y = F_7+F_1, F_{10}+F_1$ .
$(7, 3)$ : $7^x 3^y = F_7+F_6, F_8+F_0, F_{10}+F_6, F_{12}+F_4$ .
$(17, 2)$ : $17^x 2^y = F_8+F_7, F_9+F_0, F_9+F_9, F_{10}+F_7$ .
$(19, 2)$ : $19^x 2^y = F_{10}+F_8, F_{12}+F_6$ .

For all other pairs of primes $(p, q)$ with $q \le 1000$ , the equation has at most one solution in positive integers $x, y$ .

5. Significance

Extension of Previous Work: This paper generalizes previous results by Bravo and Luca (who studied $F_n + F_m = 2^a$ ) and Ziegler (who studied $F_n + F_m = y^a$ ). It moves from single prime powers or perfect powers to products of two distinct prime powers.
Methodological Rigor: The paper demonstrates a sophisticated application of the "Baker-Davenport" method (combining linear forms in logarithms with lattice reduction). The authors successfully handle extremely large initial bounds ( $10^{300+}$ ) and reduce them to computable ranges, showcasing the power of modern Diophantine approximation techniques.
Completeness: By covering the case $q=5$ separately and handling the linear dependence of rows in the matrix of exponents (a rare and difficult scenario), the authors provide a complete and rigorous classification for the specified range of primes.
Computational Number Theory: The work highlights the necessity of combining theoretical bounds with efficient computational algorithms (LLL, modular lifting, primality testing) to solve Diophantine equations involving large numbers.