Results Math          (2023) 78:116 
Online First
c© 2023 The Author(s)

https://doi.org/10.1007/s00025-023-01871-0 Results in Mathematics

Additive Diophantine Equations with Binary
Recurrences, S-Units and Several Factorials

Attila Bérczes, Lajos Hajdu, Florian Luca , and István Pink

Abstract. There are many results in the literature concerning linear com-
binations of factorials among terms of linear recurrence sequences. Re-
cently, Grossman and Luca provided effective bounds for such terms of
binary recurrence sequences. In this paper we show that under certain
conditions, even the greatest prime divisor of un − a1m1! − · · · − akmk!
tends to infinity, in an effective way. We give some applications of this
result, as well.

Mathematics Subject Classification. 11B37, 11D61.

Keywords. Greatest prime factor, baker’s method, binary recurrence
sequence.

1. Introduction

An integer sequence {un}n≥0 = {un(r, w, u0, u1)}n≥0 is a binary linear recur-
rence if the recurrence relation

un = run−1 + wun−2 (n ≥ 2) (1.1)

holds, where r, w ∈ Z\{0} and u0, u1 are integers not both zero. The polyno-
mial f(x) = x2−rx−w attached to recurrence (1.1) is called the characteristic
polynomial of the sequence {un}n≥0. We denote the discriminant of f by Δ
and assume that Δ �= 0. Let α and β be the roots of f with the convention
that |α| ≥ |β|. Putting

c =
u1 − u0β

α − β
and d =

u0α − u1

α − β
(1.2)

Research supported in part by the Eötvös Loránd Research Network (ELKH), by the NKFIH
Grants 128088 and 130909, and the Projects EFOP-3.6.1-16-2016-00022 co-financed by the
European Union and the European Social Fund.

0123456789().: V,-vol  

http://crossmark.crossref.org/dialog/?doi=10.1007/s00025-023-01871-0&domain=pdf
http://orcid.org/0000-0003-1321-4422


  116 Page 2 of 32 A. Bérczes et al. Results Math

it is well-known that the formula

un = cαn + dβn holds for all n ≥ 0. (1.3)

For later use we fix the notation

Y := max{|u0|, |u1|, |r|, |w|}. (1.4)

The sequence {un}n≥0 is called non-degenerate, if cdαβ �= 0 and α/β is not a
root of unity. Taking r = w = u1 = 1, u0 = 0 the sequence {un}n≥0 becomes
the classical Fibonacci sequence usually denoted by {Fn}n≥0 for which α =
(1 +

√
5)/2 and β = (1 − √

5)/2. Grossman and Luca [2] showed that for fixed
positive integers A and k, the Diophantine equation

un =
k∑

i=1

aimi! with |ai| ≤ A (1.5)

implies that
n ≤ c1, (1.6)

where c1 = c1(k,A) is an effectively computable constant depending only on
k and A. Taking A = 1 and k = 2, it was shown in the same paper that
F12 = 4! + 5! is the largest Fibonacci number which is a sum or difference of
two factorials. Further, in [1], it was shown that F7 = 1!+3!+3! is the largest
Fibonacci number which is a sum of three factorials.

Let S = {p1, . . . , pl} be a finite set of primes labelled p1 < · · · < pl and
P = pl(= max{p1, . . . , pl}). We denote by S the set of all positive integers
whose prime factors are all in S. In particular, 0 �∈ S but 1 ∈ S . In [3], the
problem of representing un as a sum between a factorial and an element from
S was considered. Namely, it was proven that for given integers A,B, the
equation

un = Am! + Bs in n,m ∈ Z and s ∈ S

implies that n ≤ c2 holds for all solutions n which are non-trivial (see the
terminology of that paper for nontrivial; for example, when un = 2n + 1, the
solution with m1 = 1, s = 2n for any n when S = {2} is trivial). Here, c2 is an
explicit constant depending only on A,B, S and the sequence u = {un}n≥0.
As a numerical application, in [3] it was shown that F24 = 8! + 253371 is the
largest Fibonacci number of the form Fn = ±m! ± 2a3b5c7d; thus the largest
solution when u = {Fn}n≥0, A = B = 1 and S = {2, 3, 5, 7}.

2. Our Results

For an integer m denote by P (m) the greatest prime factor of m with the
convention that P (0) = P (±1) = 1. As before, {un}n≥0 is a non-degenerate
binary recurrence sequence. Further, let k ≥ 1 and A ≥ 1 be fixed positive
integers.



Additive Diophantine Equations with Binary Recurrences Page 3 of 32   116 

In view of Theorem 1 of Grossman and Luca [2] (see (1.5) and (1.6)) we have
that un −∑k

i=1 aimi! �= 0 for all integers a1, . . . , ak with |ai| ≤ A for i =
1, . . . , k, whenever n > c1. Therefore, it is natural to examine the parameter

P

(
un −

k∑

i=1

aimi!

)
. (2.1)

In this paper, we study the quantity (2.1) when u has Δ > 0 and w = ±1.
Without loss of generality (or, replacing A by kA if needed) we assume that
the unknowns mi (i = 1, . . . , k) satisfy

m1 > m2 > · · · > mk ≥ 1. (2.2)

Our main result below implies that

P

(
un −

k∑

i=1

aimi!

)
→ ∞ as n → ∞

in an effective way. Namely, we have the following result.

Theorem 2.1. Let {un}n≥0 be a non-degenerate binary sequence with Δ > 0
and w = ±1. Assume that |ai| ≤ A for i = 1, . . . , k and the unknowns mi

satisfy (2.2). Put c3 := 16(Y + 2) log(Y + 2), c4 := 5.6 · 1017 log2(Y + 2) and
let n1 := n1(k) be the largest integer solution of the inequality

n < 2.08 · (log(4(A + 1)) + 21.6c4 log2 n
)k

.

Then

P

(
un −

k∑

i=1

aimi!

)
> c5(n), (2.3)

whenever n > c6, where

c5(n) :=
( n

2.08

) 1
3k+3

(
log(4A)

8
+ 2.7c4 log2 n

)− 1
3

and

c6 := max{c3, n1}.

As a direct consequence of Theorem 2.1, we have the following result.

Theorem 2.2. Let {un}n≥0 be a non-degenerate binary sequence with Δ > 0
and w = ±1 and let S = {p1, . . . , pl} be a finite set of primes. Put P :=
max{p1, . . . , pl}. We denote by S the set of all rational integers whose prime
factors are all in S. Further, let k ≥ 1 and A ≥ 1 be fixed positive integers.
Consider the Diophantine equation

un = a1m1! + · · · + akmk! + bs, max{|a1|, |a2|, . . . , |ak|, |b|} ≤ A (2.4)

in integer unknowns (m1,m2, . . . ,mk, s) satisfying s ∈ S and (2.2). Then

n ≤ c7 := max{c6, c8}, (2.5)



  116 Page 4 of 32 A. Bérczes et al. Results Math

where c6 and c4 are defined in the statement of Theorem 2.1 and

c8 := max
{

22k+2 c9 log2k+2
(
(2k + 2)2k+2 c9

)
, (4e2)2k+2

}

with

c9 := 2.08 · (max{P,A})3k+3 · (2c4 log(4A))k+1.

Finally, to show the strength of our above result we completely solve a
simple equation of the above shape.

Theorem 2.3. Let {Fn}n≥0 denote the Fibonacci sequence and S := {2, 3, 5, 7}.
Denote by S the set of all positive integers which have no prime factor outside
of S. Then all solutions of the equation

Fn = m1! + m2! + s in n,m1,m2, s ∈ N,m1 > m2, s ∈ S (2.6)

are given by

[n,m1,m2, s] ∈ {[5, 2, 1, 2], [6, 2, 1, 5], [6, 3, 1, 1], [7, 2, 1, 10], [7, 3, 1, 6], [7, 3, 2, 5],

[8, 2, 1, 18], [8, 3, 1, 14], [9, 3, 1, 27], [9, 4, 1, 9], [9, 4, 2, 8], [9, 4, 3, 4],

[10, 3, 1, 48], [10, 4, 1, 30], [10, 4, 3, 25], [11, 4, 1, 64], [11, 3, 2, 81],

[11, 4, 2, 63], [12, 5, 3, 18], [13, 5, 1, 112], [13, 3, 2, 225], [14, 5, 1, 256],

[16, 3, 1, 980], [16, 6, 4, 243], [16, 6, 5, 147], [17, 6, 2, 875],

[20, 7, 4, 1701], [24, 8, 7, 1008], [25, 4, 1, 75000], [25, 7, 1, 69984]} .

3. Linear Forms in p-Adic Logarithms

In this section, we shall present the p-adic version of a lower bound for linear
forms in logarithms of algebraic numbers due to Kunrui Yu [10]. We begin by
recalling some basic notions from algebraic number theory. For an algebraic
number η of degree d over Q, we define the absolute logarithmic height of η by
the formula

h(η) =
1
d

(
log |a0| +

d∑

i=1

log max
(
1, |η(i)|

))
,

where a0 is the leading coefficient of the minimal polynomial of η over Z and
η(i)−s are the conjugates of η in the field of complex numbers.

Let L be an algebraic number field of degree dL and denote by OL the
ring of integers of L. Let π be a prime ideal in OL and denote by eπ the
ramification index of π, and by fπ the residue class degree of π. For the unique
prime number p ∈ Z such that π | pOL, we say that π lies above p. Further, it
is well known that

pOL =
g∏

i=1

πei
i ,



Additive Diophantine Equations with Binary Recurrences Page 5 of 32   116 

where π1, . . . , πg are prime ideals of OL. The prime ideal π is one of the primes
πi, say π1, and its eπ equals e1. The number fπ is the dimension of the finite
field OL/π over its prime field Z/pZ, or, equivalently, can be computed via
the formula # (OL/π) = pfπ . In the special case L = Q we have π = p and
dL = eπ = fπ = 1.

For a non-zero algebraic number γ ∈ L we write νπ(γ) for the exponent
of π in the factorization in prime ideals of the principal fractional ideal γOL.
It is well known that for every non-zero integer j and prime ideal π of OL lying
above the rational prime p we have

νp(j) =
1
eπ

νπ(j). (3.1)

Let η1, . . . , ηl be non-zero algebraic numbers in L and let

Λ =
l∏

i=1

ηdi
i − 1, (3.2)

where d1, . . . , dl ∈ Z.
With the above definitions and notations, Yu [10] proved the following

result.

Lemma 3.1. Let π be a prime ideal in OL lying above the rational prime p with
the convention that π = p and dL = eπ = fπ = 1 if L = Q. Consider the linear
form Λ defined by (3.2) and let

D ≥ max{|d1|, . . . , |dl|, 3}, (3.3)

and
Hj ≥ max{h(αi), log p} (1 ≤ i ≤ l). (3.4)

If Λ �= 0, then

νπ(Λ) ≤ 19(20
√

l + 1dL)2(l+1)el−1
π

pfπ

(fπ log p)2
log(e5ldL)H1 · · · Hl log D.

(3.5)

Following Lenstra, Lenstra and Lovász [5], we recall the definition of an
LLL-reduced basis of a lattice L ⊂ R

n. For a basis {b1, b2, . . . , bn} of the lattice
L the Gram-Schmidt procedure provides an orthogonal basis {b∗

1, b
∗
2, . . . , b

∗
n}

of L with respect to the inner product 〈·, ·〉 of Rn given inductively by

b∗
i = bi −

i−1∑

j=1

μijb
∗
j (1 ≤ i ≤ n), μi,j =

〈bi, b
∗
j 〉

〈b∗
j , b

∗
j 〉

(1 ≤ j < i ≤ n).

We call a basis {b1, b2, . . . , bn} for a lattice L LLL-reduced if

‖μi,j‖ ≤ 1
2

(1 ≤ j < i ≤ n)



  116 Page 6 of 32 A. Bérczes et al. Results Math

and

‖b∗
i + μi,i−1b

∗
i−1‖2 ≥ 3

4
‖b∗

i−1‖2 (1 < i ≤ n),

where ‖.‖ denotes the ordinary Euclidean length.
To reduce the initial upper bounds for the parameters, we shall also need

the following three standard lemmas.

Lemma 3.2. Let b1, . . . , bn be an LLL-reduced basis of a lattice L ⊂ R
n. Then

c6 := ||b1||2/2n−1 is a lower bound for the length of the shortest vector of L.
Proof. This is a simplified version of Theorem 5.9 of [9]. �

Lemma 3.3. Let α1, . . . , αn ∈ R be real numbers and x1, . . . , xn ∈ Z with |xi| ≤
Xi. Put X0 := max Xi, S :=

∑n−1
i=1 X2

i , T := 0.5 + 0.5 ·∑n
i=1 Xi and assume

that
∣∣∣∣∣

n∑

i=1

xiαi

∣∣∣∣∣ ≤ c2 exp {−c5H
q}

holds for some positive real constants c2, c5,H and positive integer q. Let C ≥
(nX0)n and let L denote the lattice of R

n generated by the columns of the
matrix

⎛

⎜⎜⎜⎝

1 . . . 0 0
. . .

0 . . . 1 0
[Cα1] . . . [Cαn−1] [Cαn]

⎞

⎟⎟⎟⎠ ∈ Z
n×n.

Let c6 denote a lower bound on the length of the shortest non-zero vector of
the lattice L. If c26 > T 2 + S then we have either

H ≤ q

√
1
c5

(
log(Cc2) − log

(√
c26 − S − T

))
,

or

x1 = x2 = · · · = xn−1 = 0, xn = − [Cα0]
Cαn

.

Proof. This is Lemma VI.I of [9]. �

Lemma 3.4. Let z ∈ C with |z − 1| ≤ a ∈ (0, 1). Then

| log z| ≤ − log(1 − a)
a

|z − 1|.

Proof. This is Lemma B.2 of [9]. �



Additive Diophantine Equations with Binary Recurrences Page 7 of 32   116 

4. Preliminary Results on Binary Recurrence Sequences

The next lemma contains several known results which are very useful for the
estimates needed in the paper.

Lemma 4.1. Let {un}n≥0 be a non-degenerate binary recurrence sequence given
by (1.3) and let Y defined by (1.4). Then the following hold:

(i) max{h(α), h(β), h(α/β), h(c), h(d), h(c/d)} < 8 log(Y + 2).
(ii) If n > c3 := 16(Y + 2) log(Y + 2) then un �= 0.
(iii) If n > c3 then |un| > |α|n−c10 log n, where c10 := 4 · 1011 log(Y + 2).

Proof. (i) is Lemma 8, (ii) is Lemma 9 and (iii) is Lemma 11 of [3]. �

The following lemma is also well-known (see for instance Lemma 1 of [2])
and it provides a lower bound for the p-adic valuation of factorials.

Lemma 4.2. Let p be a prime number and let m be a positive integer. If m ≥ p,
then νp(m!) > m

2p .

The following lemma is an elementary result due to Pethő and de Weger
[7]. It will be used in the proof of Theorem 2.2. For a proof of Lemma 4.3 we
refer to Appendix B of [9].

Lemma 4.3. Let u, v ≥ 0, h ≥ 1 and x ∈ R be the largest solution of x =
u + v(log x)h. Then

x < max
{

2h(u1/h + v1/h log(hhv))h, 2h(u1/h + 2e2)h
}

.

In the proof of Theorem 2.1 we need an upper bound for the quantity of
the form νp(un − t), where t ∈ Z.

Lemma 4.4. Let {un}n≥0 be a non-degenerate sequence given by (1.3) with
Δ > 0 and w = ±1. Further, let Y defined by (1.4). If n > c3 then for prime
p and integer t with un �= t we have

νp(un − t) <

{
c4p

2 log n, if t = 0;
c4p

2 log n log(4|t|), if t �= 0,
(4.1)

where
c4 = c4(Y ) := 5.6 · 1017 log2(Y + 2). (4.2)

Proof. We have the representation

un = cαn + dβn, (4.3)

where
c =

u1 − u0β

α − β
and d =

u0α − u1

α − β
(4.4)

with cdαβ �= 0 and α/β is not a root of unity. Let L = Q(α). Let p be an
arbitrary but fixed prime and denote by π a prime ideal dividing p in L. Write
eπ and fπ for the ramification index and for the residue class degree of π,



  116 Page 8 of 32 A. Bérczes et al. Results Math

respectively. Since αβ = ±1, it is clear that both of α and β are units in
L = Q(α), and therefore νπ(α) = νπ(β) = 0.

Suppose first that t = 0.
Since νπ(α) = 0, we have by (4.3), (3.1), eπ ≥ 1 and the additive property

of the function νπ, that

νp(un) = νp(un − t) =
1
eπ

νπ (cαn + dβn) ≤ νπ(c) + νπ(Λ), (4.5)

where

Λ =
(−d

c

)(
β

α

)n

− 1. (4.6)

Let us bound the quantities of the right hand side of (4.5). Denote by N (I)
the norm of the ideal I. By (4.4), we clearly have

νπ(c) ≤ νπ(u1 − u0β),

and therefore

pνπ(c) ≤ N (π)νπ(c) ≤ N (π)νπ(u1−u0β) ≤ ∣∣NL/Q (u1 − u0β)
∣∣ ≤ Y 3 + 2Y 2

< (Y + 2)3.

So,

νπ(c) <
3 log(Y + 2)

log p
. (4.7)

We next bound νπ(Λ) from above. If Λ = 0 then un = 0 also holds, which by
our assumption n > c3 and (ii) of Lemma 4.1 leads to a contradiction. Thus,
we may suppose that Λ �= 0. We apply Lemma 3.1 to bound νπ(Λ) on choosing

l = 2, η1 =
−d

c
, η2 =

β

α
, d1 = 1, d2 = n, dL ≤ 2, fπ ≤ 2, eπ ≤ 2,D = n.

By (i) of Lemma 4.1, we can take

H1 = H2 = max{log p, 8 log(Y + 2)}.

Applying Lemma 3.1, we get

νπ(Λ) ≤ 19 · (20
√

3 · 2)6 · 2 log (4e5)
p2

(log p)2
(max{log p, 8 log(Y + 2)})2 log n.

(4.8)
If max{log p, 8 log(Y +2)} = log p we obtain by (4.5), (4.7), (4.8), the fact that
p ≥ 2, Y ≥ 1, n > c3 and some routine calculations that

νp(un) = νp(un − t) < 2.5 · 1013 log(Y + 2)p2 log n,

while if max{log p, 8 log(Y + 2)} = 8 log(Y + 2) we get

νp(un) = νp(un − t) < 3.72 · 1015 log2 (Y + 2)p2 log n,

leading to a sharper upper bound than stated in the case t = 0.



Additive Diophantine Equations with Binary Recurrences Page 9 of 32   116 

Assume next that t �= 0. By β = wα−1 = ±α−1 and (4.3), an easy
calculation gives

un − t = cαn + dβn = cαn(α−nz1 − 1)(α−nz2 − 1), (4.9)

where

z1,2 =
t ± √

t2 − 4wncd

2c
. (4.10)

Recall that L = Q(α) and fix w ∈ {−1, 1} as well as the parity of n. Define
the number field K by

K :=

{
L(

√
t2 + 4cd), if wn = −1;

L(
√

t2 − 4cd), if wn = 1.
(4.11)

It is clear that in both cases dK = [K : Q] ≤ 4. Let p be a prime and let p be
a prime ideal in K dividing p. Write ep and fp for the ramification index and
for the residue class degree of p, respectively. Using (3.1), Eq. (4.9) gives

νp(un − t) =
1
ep

(
νp
(
cαn(α−nz1 − 1)(α−nz2 − 1)

))
. (4.12)

Since α is a unit also in K and ep ≥ 1, by combining (4.12) with the additivity
of the function νp we get

νp(un − t) ≤ νp(c) + νp(α−nz1 − 1) + νp(α−nz2 − 1). (4.13)

Putting Λ1 := α−nz1−1 and Λ2 := α−nz2−1 inequality (4.13) can be rewritten
as

νp(un − t) ≤ νp(c) + νp(Λ1) + νp(Λ2). (4.14)
Since [K : L] ≤ 2 and νp(c) ≤ νp(u1 − u0β) we have

pνp(c) ≤ N (p)νp(c) ≤ N (p)νp(u1−u0β) ≤
( ∣∣NL/Q(u1 − u0β)

∣∣
)2

≤ (Y 3 + 2Y 2)2

< (Y + 2)6,

so

νp(c) <
6 log(Y + 2)

log p
. (4.15)

We next bound νp(Λi) for i = 1, 2. It is clear that Λi = 0 (i = 1, 2) holds
if and only if αn = zi (i = 1, 2), which by (4.9) is equivalent with un = t.
However, this is excluded. Therefore Λi �= 0 for i = 1, 2. Note, that if dK = 4,
the number field K is a biquadratic number field. It is well known that in this
case fp ≤ 2. Hence, it is clear that for p ∈ K we are in one of the following
cases

(fp = 1 and ep ≤ 4) or (fp = 2 and ep ≤ 2). (4.16)
In order to bound νp(Λi) for i = 1, 2 from above we use twice Lemma 3.1 with
the parameters

l = 2, dK ≤ 4, η1 = α, η2 = z1, d1 = −n, d2 = 1,D = n



  116 Page 10 of 32 A. Bérczes et al. Results Math

to bound νp(Λ1) and with

l = 2, dK ≤ 4, η1 = α, η2 = z2, d1 = −n, d2 = 1,D = n

to bound νp(Λ2). By (i) of Lemma 4.1, we have h(α) < 8 log(Y + 2) and
therefore we may choose in both cases

H1 = max{log p, 8 log(Y + 2)}. (4.17)

Further, by combining (4.10) and (i) of Lemma 4.1 with some well-known
properties of the absolute logarithmic height function h(.), we may write for
i = 1, 2 that

h(zi) ≤ h
(
(2c)−1

)
+ h
(
t ±
√

t2 − 4wncd
)

≤ log(4|t|) + 8 log(Y + 2) + h(γ),
(4.18)

where γ =
√

t2 − 4wncd. Since

cd =
±u2

0 + u0u1r − u2
1

Δ
we obtain

γ =
√

t2 − 4wncd =

√
Δt2 − 4wn(±u2

0 + u0u1r − u2
1)

Δ
.

Thus, a straightforward calculation leads to

h(γ) ≤ 1
2

log
(
|Δ|t2 + 4

(
u2
0 + |u0||u1||r| + u2

1

))
. (4.19)

Since Δ > 0, we have |α| > |β|, which together with w = ±1 = αβ implies
that |β| < 1. Further, since α = r − β, we have |α| ≤ |r| + |β| < Y + 1, which
together with Δ = (α − β)2 leads to

|Δ| < (Y + 2)2. (4.20)

Now, the combination of (4.19), (1.4) and (4.20) gives

h(γ) <
1
2

log(Y + 2) +
1
2

log
(
(Y + 2)t2 + 4Y 2

)
,

which since Y < Y + 2, Y ≥ 1, |t| ≥ 1 implies that

h(γ) <
3
2

log(Y + 2) +
1
2

log(4t2) +
1
2

log
(

1 +
1
12

)
. (4.21)

Since
1
2 log(4t2)
log(4|t|) < 1,

we get by (4.18), (4.21), Y ≥ 1 and |t| ≥ 1 that

max{h(z1), h(z2)} < 8.75 log(4|t|) log(Y + 2). (4.22)

Thus, (4.22) shows that we may choose in both cases

H2 = max{log p, 8.75 log(4|t|) log(Y + 2)}. (4.23)



Additive Diophantine Equations with Binary Recurrences Page 11 of 32   116 

By (4.16), we may write

ep
pfp

(fp log p)2
≤ max

{
4p

log2 p
,

p2/2
log2 p

}
≤ 2p2

log2 p
. (4.24)

Applying Lemma 3.1 we get by (4.14), (4.15) and (4.24) that

νp(un − t) ≤ 6 log(Y + 2)
log p

+ 2 · 19(20
√

3 · 4)6 log (8e5) · 2p2

log2 p

×max{log p, 8 log(Y + 2)}max{log p, 8.75 log(Y + 2) log(4|t|)} log n,

which together with p ≥ 2, Y ≥ 1, |t| ≥ 1 and n > c3 ≥ 48 log 3 leads to the
desired upper bound. The proof of Lemma 4.4 is complete. �

The next lemma deals with sums of factorials in binary recurrence se-
quences. This was originally proved by Grossman and Luca (see Theorem 1 of
[2]). For our purposes, we need a totally explicit version of Theorem 1 of [2]
in the case where Δ > 0 and w = ±1.

Lemma 4.5. Let {un}n≥0 be the non-degenerate binary recurrence sequence
given by (1.3) with Δ > 0 and w = ±1. Further, let k ≥ 1 and A ≥ 1 be
fixed positive integers. Consider the equation

un = a1m1! + · · · + akmk! where |ai| ≤ A (1 ≤ i ≤ k) (4.25)

in integer unknowns (n,m1, . . . ,mk) with

m1 > m2 > · · · > mk ≥ 1. (4.26)

Then we have n ≤ min(c3, n0), where n0 := n0(k) is the largest positive integer
solution of the inequality

n < 2.08 · (log(4A) + 21.6c4 log2 n
)k

.

Proof. If n ≤ c3, then the statement is automatic. So throughout the proof
we shall assume that n > c3. Consider the Eq. (4.25) satisfying assumption
(4.26). We may assume that there is no vanishing subsum on the right hand
side of (4.25); that is, that we have

∑

i∈I⊂{1,2,...,k}
aimi! �= 0 (4.27)

for each non-empty subset I ⊂ {1, 2, . . . , k}. Note, that (4.27) can be assumed
without loss of generality, since otherwise we obtain an equation similar to
(4.25) with fewer terms.

For j = 1, . . . , k put

Nj =
j∑

i=1

ak+1−imk+1−i! (4.28)

We show by induction that

log |4Nj | <
(
log(4A) + 21.6c4 log2 n

)j
. (4.29)



  116 Page 12 of 32 A. Bérczes et al. Results Math

For j = 1 we have |4Nj | = |4akmk!|. Further, since n > c3, by applying Lemma
4.4 with t = 0 and p = 2, we obtain

ν2(un) < 4c4 log n. (4.30)

Further, by (4.26) it is clear that

ν2(un) = ν2(a1m1! + · · · + akmk!) ≥ ν2(mk!).

If mk ≥ 4 ·(4c4 log n) then Lemma 4.2 yields ν2(mk!) > 4c4 log n, contradicting
(4.30). Thus, mk < 4 · (4c4 log n) = 16c4 log n, whence

log |4N1| ≤ log |4ak| + mk log mk < log(4A) + (16c4 log n) log(16c4 log n).
(4.31)

We may assume that n > 16c4, since otherwise we obtain n ≤ 16c4, which
is better than the stated inequality. Since for n > c3(≥ 48 log 3) one has
log log n/ log n < 0.35 we may write by (4.31) that

log |4N1| < log(4A) + 21.6c4 log2 n. (4.32)

Suppose now, that (4.29) holds for some 1 ≤ j < k. By rewriting (4.25)
in the form

un − Nj = ak−jmk−j ! + · · · + a1m1!, (4.33)
we easily see by (4.27) that the right hand side of (4.33) is nonzero and hence
un �= Nj . Further, by (4.27) Nj �= 0 also holds. Therefore, we may apply
Lemma 4.4 with p = 2 and t = Nj . We obtain that

ν2(un − Nj) < 4c4 log(|4Nj |) log n. (4.34)

Further, by (4.26) it is clear that

ν2(un − Nj) = ν2(a1m1! + · · · + ak−jmk−j !) ≥ ν2(mk−j !).

If mk−j ≥ 4 · 4c4 log(|4Nj |) log n then Lemma 4.2 yields

ν2(mk−j !) > 4c4 log(|4Nj |) log n,

contradicting (4.34). Thus, mk−j < 16c4 log(|4Nj |) log n, whence

log |4ak−jmk−j | < log(4A) + (16c4 log(|4Nj |) log n) log(16c4 log(|4Nj |) log n).
(4.35)

We may assume that n > 16c4 log(|4Nj |). Indeed, if n ≤ 16c4 log(|4Nj |), we
then get by (4.29) that

n < 16c4
(
log(4A) + 21.6c4 log2 n

)j
.

Further, since j ≤ k − 1 the above inequality implies that

n < 16c4
(
log(4A) + 21.6c4 log2 n

)k−1
,

which is better than the stated bound for n. Since for n > c3(≥ 48 log 3) one
has log log n/ log n < 0.35 we may write by n > 16c4 log(|4Nj |) and (4.35) that

log |4ak−jmk−j | < log(4A) + 21.6c4 log(|4Nj |) log2 n. (4.36)



Additive Diophantine Equations with Binary Recurrences Page 13 of 32   116 

It is clear that

4Nj+1 = 4Nj + 4ak−jmk−j !,

and hence

|4Nj+1| ≤ |4Nj | + |4ak−jmk−j !|.
Thus,

|4Nj+1| < |4Nj | + exp{log(4A) + 21.6c4 log(|4Nj |) log2 n},

which is equivalent to

|4Nj+1| < |4Nj | + 4A|4Nj |21.6c4 log2 n. (4.37)

Now, (4.37) implies that

|4Nj+1| ≤ |4Nj | + 4A|4Nj |21.6c4 log2 n,

which leads to

log |4Nj+1| < log(4A) + 21.6c4 log2 n log |4Nj |
+ log

(
1 +

1
4A|4Nj |21.6c4(log2 n)−1

)
. (4.38)

Since A ≥ 1, |Nj | ≥ 1 and 21.6c4(log2 n) − 1 ≥ 1 one has

log
(

1 +
1

4A|4Nj |21.6c4(log2 n)−1

)
< 0.1,

which by (4.38) yields

log |4Nj+1| < log(4A) + 21.6c4 log2 n log |4Nj | + 0.1. (4.39)

The combination of (4.29) and (4.39) gives

log |4Nj+1| < log(4A) + 21.6c4 log2 n(log(4A) + 21.6c4 log2 n)j + 0.1. (4.40)

Finally, since

log(4A) + 21.6c4 log2 n(log(4A) + 21.6c4 log2 n)j

< (log(4A) + 21.6c4 log2 n)j+1 − 1,

we obtain by (4.40) that

log |4Nj+1| <
(
log(4A) + 21.6c4 log2 n

)j+1
, (4.41)

finishing the induction.
Recall that by assumption n > c3, which guarantees that un �= 0. The

above inductive argument together with (iii) of Lemma 4.1 shows that

log 4 + (n − c10 log n) log |α| < log(4|un|) = log |4Nk|
<
(
log(4A) + 21.6c4 log2 n

)k
,



  116 Page 14 of 32 A. Bérczes et al. Results Math

whence

n <
(
log(4A) + 21.6c4 log2 n

)k
(

1
log |α| +

c10 log n
(
log(4A) + 21.6c4 log2 n

)k

)

which together with n > c3, log(4A) > 0, |α| ≥ (1 +
√

5)/2, k ≥ 1 and the
definitions of c10 and c4 implies

n < 2.08 · (log(4A) + 21.6c4 log2 n
)k

. (4.42)

The lemma is proved. �

5. Proof of Theorem 2.1

Proof of Theorem 2.1. Suppose that

n > c6 = max{c3, n1}. (5.1)

Since n1 ≥ n0, Lemma 4.5 implies that

un − (a1m1! + · · · + akmk!) �= 0.

Thus, we may write

un = a1m1! + · · · + akmk! + s, (5.2)

where s �= 0 is some integer, |ai| ≤ A and

m1 > m2 > . . . > mk ≥ 1. (5.3)

We let P := P (s). By employing an inductive argument similar to the one
applied in Lemma 4.5, we derive an explicit upper bound for n in terms of
P,A, k and Y in equation (5.2), leading to an explicit lower bound for P and
therefore also for P (un − (a1m1! + · · · + akmk!)).

We may assume without loss of generality that there is no vanishing
subsum on the right hand side of (5.2), that is that

∑

i∈I⊂{1,2,...,k}
aimi! + δs �= 0 (5.4)

holds for each non-empty subset I ⊂ {1, 2, . . . , k} and each δ ∈ {0, 1}. Indeed,
if there is an index set I ⊂ {1, 2, . . . , k} and δ ∈ {0, 1} such that

∑

i∈I⊂{1,2,...,k}
aimi! + δs = 0,

then (5.2) implies that
⎧
⎪⎪⎪⎨

⎪⎪⎪⎩

un =
∑

i∈{1,2,...,k}\I

aimi! + s, if δ = 0,

un =
∑

i∈{1,2,...,k}\I

aimi!, if δ = 1.
(5.5)



Additive Diophantine Equations with Binary Recurrences Page 15 of 32   116 

Now, (5.5) shows that for δ = 1 we obtain an equation similar to (4.25) which
for n > n0 cannot happen, while for δ = 0 we get an equation similar to (5.2)
with fewer terms.

If |s| = mi! for some i = 1, . . . , k, then (5.2) leads to an equation of the
form

un = a1m1! + · · · + ai−1mi−1! + (ai ± 1)mi! + ai+1mi+1 + · · · + akmk!,

which by Lemma 4.5 gives n ≤ n1, which is a contradiction in view of (5.1).
Put mk+1 := 0 and let m0 be such that max{|s|,m1!} < m0!. By (5.1),

there exists an index 0 ≤ i0 ≤ k such that

mk+1−i0 ! < |s| < mk+1−i0−1!, (5.6)

and for i = 1, . . . , k + 1 we put

ti =

⎧
⎪⎨

⎪⎩

ak+1−imk+1−i!, if i ≤ i0,

s, if i = i0 + 1,

a(k+1)−(i−1)m(k+1)−(i−1)!, if i ≥ i0 + 2.

(5.7)

For j = 1, . . . , k + 1, we set

Nj :=
j∑

i=1

ti. (5.8)

We show by induction on j that for 1 ≤ j ≤ k + 1

log |4Nj | <
(
log(4A) + 2.7c4P

3 log2 n
)j

. (5.9)

For j = 1 we easily see that

N1 = t1 =

{
s, if |s| < mk!,
akmk!, if |s| > mk!.

Case 1. |s| < mk!.
In this case N1 = s. Recall that P = max{p : p | s}. By (5.1), we have

that un �= 0 and therefore by applying Lemma 4.4 with t = 0 and with each
prime factor p | s, we obtain νp(un) < c4p

2 log n, which yields

νp(un) < c4P
2 log n (p | s). (5.10)

On using (5.3) for every prime p we infer that

νp(a1m1! + · · · + akmk!) ≥ νp(mk!). (5.11)

If mk ≥ 2P (c4P 2 log n) = 2c4P 3 log n, then Lemma 4.2 and p ≤ P show that

νp(mk!) >
mk

2p
≥ c4P

2 log n

holds for every p | s, which by (5.2), (5.10) and (5.11) forces

νp(un) = νp(s) (5.12)



  116 Page 16 of 32 A. Bérczes et al. Results Math

to hold for every p | s. Thus, (5.12) and (5.10) imply

log(|s|) =
∑

p|s
νp(s) log p =

∑

p|s
νp(un) log p < c4P

2(log n)π(P ) log P.

Since π(P ) < 2P/log P (see Corollary 1 in [8]), the above inequality leads to

log(4|N1|) = log(4|s|) < log 4 + 2c4P 3 log n. (5.13)

Suppose now that mk < 2c4P
3 log n. Then since mk! ≤ mmk

k , we may write

log(|4mk!|) < log 4 + (2c4P 3 log n) log(2c4P 3 log n). (5.14)

If n < 2c4P
3, then P > n1/3(2c4)−1/3, which is a sharper lower bound for P

than stated. Therefore, we may assume that n ≥ 2c4P
3 which combined with

(5.14) and with log log n/ log n < 0.35 which holds for n > n1, we get

log(|4mk!|) < log 4 + 2.7c4P
3 log2 n. (5.15)

Since log(|4N1|) = log(|4s|), we obtain from |s| < mk! and (5.15) that

log(|4N1|) < log 4 + 2.7c4P
3 log2 n. (5.16)

Case 2. |s| > mk!.
In this case, N1 = akmk!. If mk ≥ 2c4P

3 log n then using the same
argument as in Case 1, we get that log(4|s|) < log 4 + 2c4P 3 log n, which
together with mk! < |s| and |ak| ≤ A implies that

log(|4N1|) = log(|4akmk!|) < log(|4aks|) < log(4A) + 2c4P 3 log n. (5.17)

Assume now that mk < 2c4P
3 log n. Then by the argument applied in the

corresponding part of Case 1, we obtain

log(|4N1|) = log(|4akmk!|) < log(4A) + 2.7c4P
3 log2 n. (5.18)

Finally, (5.13), (5.16), (5.17) and (5.18) show that in fact the bound occurring
in (5.18) is appropriate for all cases proving the assertion for j = 1.

Assume now that (5.9) holds for some 1 ≤ j < k + 1. Rewrite (5.2) as

un − Nj = a1m1! + · · · + a�m�! + δs, (5.19)

where δ ∈ {0, 1} and 
 := 
(δ, j, k) = k + 1 − j − δ. It is clear that Nj+1 =
Nj + tj+1, where

tj+1 =

{
a�m�!, if (δ = 0) or (δ = 1 and |s| > m�!),
s, if δ = 1 and |s| < m�!.

(5.20)

Further, Nj �= 0 and un −Nj �= 0 hold in view of (5.4). Thus, we apply Lemma
4.4 with t = Nj to obtain νp(un − Nj) < c4p

2 log(|4Nj |) log n, for every prime
p. If p | s then p ≤ P , so

νp(un − Nj) < c4P
2 log(|4Nj |) log n. (5.21)

Using (5.3), we get that

νp(a1m1! + · · · + a�m�!) ≥ νp(m�!). (5.22)



Additive Diophantine Equations with Binary Recurrences Page 17 of 32   116 

We wish to estimate log |4tj+1|. To do so, we split the proof into three cases
according to the value of tj+1 (see 5.20).

Assume first that δ = 1 and |s| < m�!.
Then tj+1 = s. If m� ≥ 2P (c4P 2 log(|4Nj |) log n) = 2c4P 3 log(|4Nj |) log n
then Lemma 4.2 and p ≤ P shows that

νp(m�!) >
m�

2p
≥ c4P

2 log(|4Nj |) log n (p | s),

which by (5.19), (5.21) and (5.22) forces

νp(un − Nj) = νp(s) (p | s). (5.23)

Thus, (5.21) and p ≤ P imply

log(|s|) =
∑

p|s
νp(s) log p =

∑

p|s
νp(un − Nj) log p

< c4P
2 log(|4Nj |)(log n)π(P ) log P.

Since π(P ) < 2P/ log P , the above inequality leads to

log(|4tj+1|) = log(4|s|) < log 4 + 2c4P 3 log(|4Nj |) log n. (5.24)

Suppose now that m� < 2c4P
3 log(|4Nj |) log n. Then, by the same argument

as in the corresponding part of the case j = 1, we obtain

log(4m�!) < log 4 + (2c4P 3 log(|4Nj |) log n) log(2c4P 3 log(|4Nj |) log n).
(5.25)

If n < 2c4P
3 log(|4Nj |) then (5.9); i.e., the induction hypothesis and j ≤ k

yield

n < 2c4P
3(log(4A) + 2.7c4P

3 log2 n)k < (log(4A) + 2.7c4P
3 log2 n)k+1,

which leads to a sharper lower bound for P than stated. Therefore, we may
assume that n ≥ 2c4P

3 log(|4Nj |), which by (5.25), |s| < m�! and log(log n)/
log n < 0.35 gives

log(|4tj+1|) = log(4|s|) < log(4m�!) < log 4 + 2.7c4P
3 log(|4Nj |) log2 n.

(5.26)
Suppose now that δ = 1 and |s| > m�!.

In this case, we have tj+1 = a�m�!. If m� ≥ 2c4P
3 log(|4Nj |) log n, then by

the same argument as in the corresponding part of the previous case, we obtain
that log(|4s|) is “small” (by “small” we mean a quantity bounded polynomially
in both P and log n), that is

log(|4s|) < log 4 + 2c4P 3 log(|4Nj |) log n,

which by |4a�s| > |4a�m�!| gives

log(|4tj+1|) = log(4a�m�!) < log(|4a�s|) < log(4A) + 2c4P 3 log(|4Nj |) log n.
(5.27)



  116 Page 18 of 32 A. Bérczes et al. Results Math

Assume now that m� < 2c4P
3 log(|4Nj |) log n. By the same argument as in

the corresponding part of the previous case, we obtain that log(|4a�m�!|) is
“small”, that is

log(|4tj+1|) = log(4a�m�!) < log(4A) + 2.7c4P
3 log(|4Nj |) log2 n. (5.28)

Finally, suppose that δ = 0. Then it is straightforward that tj+1 = a�m�!.
We apply Lemma 4.4 with t = Nj and with some prime p1 | s. We get

νp1(un − Nj) < c4P
2 log(|4Nj |) log n. (5.29)

By (5.3) and (5.19) (with δ = 0) it is clear that for p1 (actually for each prime
p | s), we have

νp1(un − Nj) ≥ νp1(m�!). (5.30)
If m� ≥ 2c4P

3 log(|4Nj |) log n then Lemma 4.2 and p1 ≤ P shows that

νp1(m�!) > c4P
2 log(|4Nj |) log n,

which is a contradiction in view of (5.29) and (5.30). Therefore, we may suppose
that m� < 2c4P

3 log(|4Nj |) log n. By the same argument as in the correspond-
ing part of the previous case, we obtain that log(|4a�m�!|) is “small”, that
is

log(|4tj+1|) = log(4a�m�!) < log(4A) + 2.7c4P
3 log(|4Nj |) log2 n. (5.31)

Now (5.24), (5.26), (5.27), (5.28) and (5.29) show that in fact the bound oc-
curring in (5.29) is appropriate for all cases proving that

log(|4tj+1|) < log(4A) + 2.7c4P
3 log(|4Nj |) log2 n. (5.32)

Since Nj+1 = Nj + tj+1, we obtain by (5.32) and the triangle inequality that

|4Nj+1| < |4Nj | + exp{log(4A) + 2.7c4P
3 log(|4Nj |) log2 n},

whence
|4Nj+1| < |4Nj | + 4A|4Nj |2.7c4P 3 log2 n. (5.33)

Inequality (5.33) leads to

log |4Nj+1| < log(4A) + 2.7c4P
3 log(|4Nj |) log2 n

+ log
(

1 +
1

4A|4Nj |2.7c4P 3 log2 n−1

)
,

which by A ≥ 1, |Nj | ≥ 1, P ≥ 2, n > n1 and c4 ≥ 5.6 · 1017 log2 3 yields

log |4Nj+1| < log(4A) + 2.7c4P
3 log(|4Nj |) log2 n + 0.1. (5.34)

Further, by the combination of (5.34) with the inductive hypothesis (5.9),
we infer that

log |4Nj+1| < log(4A)+2.7c4P
3 log2 n(log(4A)+2.7c4P

3 log2 n)j+0.1. (5.35)

Since for every u, v ∈ R with u > 1, v > 1 and every integer j ≥ 1 one has
u + v(u + v)j < (u + v)j+1 − 1, we get by (5.35)

log(4A) + 2.7c4P
3 log2 n(log(4A) + 2.7c4P

3 log2 n)j + 0.1



Additive Diophantine Equations with Binary Recurrences Page 19 of 32   116 

< (log(4A) + 2.7c4P
3 log2 n)j+1 − 0.9,

whence
log |4Nj+1| <

(
log(4A) + 2.7c4P

3 log2 n
)j+1

, (5.36)
finishing the induction.
Recall that n > c6 = max{n1, c3}, which guarantees that un �= 0. The above
inductive argument together with (iii) of Lemma 4.1 shows that

log 4 + (n − c10 log n) log |α| < log(4|un|) = log |4Nk+1|
<
(
log(4A) + 2.7c4P

3 log2 n
)k+1

,

leading to

n <
(
log(4A) + 2.7c4P

3 log2 n
)k+1

(
1

log |α| +
c10 log n

(
log(4A) + 2.7c4P 3 log2 n

)k+1

)

which since n > c3, log(4A) > 0, |α| ≥ (1 +
√

5)/2, k ≥ 1 and the definitions of
c10 and c4 implies that

n < 2.08 · (log(4A) + 2.7c4P
3 log2 n

)k+1
. (5.37)

Finally, (5.37) and P ≥ 2 yield

n < 2.08 · P 3k+3

(
log(4A)

8
+ 2.7c4 log2 n

)k+1

, (5.38)

which is equivalent to

P >
( n

2.08

) 1
3k+3

(
log(4A)

8
+ 2.7c4 log2 n

)−1/3

. (5.39)

The theorem is proved. �

Remark. For the equation

Fn = m1! + m2! + 2a3b5c7d,

where Fn is the Fibonacci sequence, we may use (5.38) (or (5.39)) with k =
2, A = 1, P = 7, Y = 1, c4 = 5.6 · 1017 log2(Y + 2) = 5.6 · 1017 log2 3 to obtain

n < 2 · 1076 (< 1080). (5.40)

6. Proof of Theorem 2.2

Proof. It is enough to show that assumption n > c6 implies n < c8 yielding
the desired upper bound (2.5); i.e., n ≤ max{c6, c8} = c7.

Suppose that n > c6 and rewrite Eq. (2.4) in the form

un −
k∑

i=1

aimi! = bs. (6.1)



  116 Page 20 of 32 A. Bérczes et al. Results Math

We investigate the quantity P
(
un −∑k

i=1 aimi!
)
; i.e., the greatest prime di-

visor of un −∑k
i=1 aimi!. On one hand, by (6.1) we have

P

(
un −

k∑

i=1

aimi!

)
= P (bs) ≤ max{P,A}. (6.2)

On the other hand, since n > c6, Theorem 2.1 gives

P (bs) = P

(
un −

k∑

i=1

aimi!

)
> c5(n), (6.3)

where c5(n) is defined in the statement of Theorem 2.1. Now, the combination
of (6.2) and (6.3) yields

n < 2.08 · (max{P,A})3k+3

(
log(4A)

8
+ 2.7 c4 log2 n

)k+1

. (6.4)

By A ≥ 1, n > c6 and the definition of c4 we easily see that
1

8 · 2.7 · c4 log2 n
+

1
log(4A)

< 0.74,

which together with (6.4) yields

n < c9 · log2k+2 n, (6.5)

with

c9 := 2.08 · (max{P,A})3k+3 · (2c4 log(4A))k+1.

Finally, by applying Lemma 4.3 to (6.5) with the parameters

x = n, u = 0, v = c9, h = 2k + 2,

we obtain that n < c8, where

c8 := max
{

22k+2 c9 log2k+2
(
(2k + 2)2k+2 c9

)
, (4e2)2k+2

}
.

The theorem is proved. �

7. Preliminary Results on Fibonacci and Lucas Numbers

The recurrence sequence {Fn}n≥0 defined by

F0 := 0, F1 := 1;Fn := Fn−1 + Fn−2 (n ≥ 2)

is called the Fibonacci sequence, and the elements belonging to this sequence
are called Fibonacci numbers. The recurrence sequence Ln given by

L0 := 2, L1 := 1;Ln := Ln−1 + Ln−2 (n ≥ 2)

is called the companion sequence of the Fibonacci sequence, and the elements
belonging to this sequence are called Lucas numbers. We have α = (1+

√
5)/2

and β = (1 − √
5)/2 for the above sequences.



Additive Diophantine Equations with Binary Recurrences Page 21 of 32   116 

In this section we collect results about Fibonacci and Lucas numbers
which are needed in the proof of Theorem 2.3.

Lemma 7.1. Let Fn denote the nth Fibonacci number.
(1) 2 | Fn ⇐⇒ 3 | n;
(2) for k ≥ 2 we have 2k | Fn ⇐⇒ 3 · 2k−2 | n;
(3) 3k | Fn ⇐⇒ 4 · 3k−1 | n;
(4) 5k | Fn ⇐⇒ 5k | n;
(5) 7k | Fn ⇐⇒ 8 · 7k−1 | n;
(6) 11k | Fn ⇐⇒ 10 · 11k−1 | n;
(7) 13k | Fn ⇐⇒ 7 · 13k−1 | n;
(8) 17k | Fn ⇐⇒ 9 · 17k−1 | n;
(9) 19k | Fn ⇐⇒ 18 · 19k−1 | n;

(10) 29k | Fn ⇐⇒ 14 · 29k−1 | n.

Proof. This is a simple consequence of the Main Theorem, Lemma 1 and
Lemma 2 of [4]. �

Lemma 7.2. Let Ln denote the nth Lucas number. Then

ν2(Ln) ≤ 2.

Proof. This is a simple consequence of Lemma 2 of [4]. �

Lemma 7.3. Let N be a positive integer not of the form Fm for some positive
integer m. Then for all positive integers n ≥ 3 one has

ν2(Fn − N) < 1730 log(6N2)max{10, log n}2.
Proof. This is Lemma 1 of [1]. �

Lemma 7.4. Let n ≥ 0 be an integer and m ∈ {3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 18}.
Assume that

30! | Fn − Fm.

Then the the parity of n and m must be the same.

Proof. We have the following cases to consider:
• if m = 3 then Fn ≡ 2 (mod 8) which by Lemma 7.1 implies that n ≡ ±3

(mod 12);
• if m = 4 then 3 | Fn which by Lemma 7.1 implies 4 | n;
• if m = 5 then 5 | Fn, which by Lemma 7.1 implies 5 | n. If n would

be even, then by 10 | n we would get 11 | Fn and since 11 | 30! this
contradicts the fact Fm = 5, consequently n must be odd;

• if m = 6 then we have 8 | Fn which by Lemma 7.1 implies 6 | n;
• if m = 7 then we have 13 | Fn which by Lemma 7.1 implies 7 | n and

if n would be even, then we would have 14 | n implying 29 | Fn which
together with Fm = 13 contradicts 30! | Fn − Fm;

• if m = 8 then we have 7 | Fn which by Lemma 7.1 implies 8 | n;



  116 Page 22 of 32 A. Bérczes et al. Results Math

• if m = 9 then we have 17 | Fn which by Lemma 7.1 implies 9 | n and
if n would be even, then we would have 18 | n implying 19 | Fn which
together with Fm = 34 contradicts 30! | Fn − Fm;

• if m = 10 then we have 11 | Fn which by Lemma 7.1 implies 10 | n;
• if m = 12 then we have 16 | Fn which by Lemma 7.1 implies 12 | n;
• if m = 14 then we have 29 | Fn which by Lemma 7.1 implies 14 | n;
• if m = 18 then we have 8 | Fn which by Lemma 7.1 implies 6 | n.

Thus, we have proved that the parity of n and m must be the same. �

Lemma 7.5. Let m ≤ n be two nonnegative integers such that m ≡ n (mod 2).
Let δ := (−1)(m−n)/2. Then,

Fn − Fm = F(n−δm)/2L(n+δm)/2.

Proof. See Lemma 2 of [6]. �

Lemma 7.6. Let Fn denote the Fibonacci sequence.
(i) Assume that (p, k) ∈ {(2, 267), (3, 168), (5, 114), (7, 95)} and let m2 be an
integer with 1 ≤ m2 ≤ 600. Then the congruence

Fn ≡ m2! (mod pk)

has no solutions in integers 4 ≤ n ≤ 1077.
(ii) Assume that (p, k) ∈ {(2, 56), (3, 36), (5, 26), (7, 21)} and let m2 be an in-
teger with 1 ≤ m2 ≤ 600. Then the congruence

Fn ≡ m2! (mod pk)

has no solutions in integers 4 ≤ n ≤ 1015.

Proof. (i) The problem is finite since all parameters and unknowns in the
congruence are bounded. However, a direct computation is not possible
due to the size of the range of n. Thus, we used the constructive method
indicated below. For given m2 and p we first we solved the congruence

Fn ≡ m2! (mod p)

by checking all values of 0 ≤ n ≤ π(p), where π(p) denotes the pth Pisano-
period. Then we worked inductively. If the solutions of the congruence

Fn ≡ m2! (mod pu)

are s1, . . . , st modulo π(p)pu−1 then the solutions of the congruence

Fn ≡ m2! (mod pu+1) (7.1)

must be among si + jπ(p)pu−1 (i = 1, . . . , t, j = 0, 1, . . . , p − 1) modulo
π(p)pu. Here one must be careful again, since computing the Fibonacci
number of index si + jπ(p)pu−1 after a while is not possible, so instead
we computed recursively the values αsi+jπ(p)pu

(mod Iu) and βsi+jπ(p)pu

(mod Iu) where α and β are the roots of the companion polynomial of the
Fibonacci sequence and Iu denotes the ideal of the ring of integers of Q(α)



Additive Diophantine Equations with Binary Recurrences Page 23 of 32   116 

generated by pu for u = 1, . . . , k. Clearly as αs
i (mod Iu) and αjπ(p)pu−1

(mod Iu) were already computed in the previous step, we only raised
αjπ(p)pu−1

(mod Iu) to power p and multiplied the result by αs
i (mod Iu)

to obtain αsi+jπ(p)pu

(mod Iu), and did the same for β. This procedure
worked fast, and we could check the congruence

αsi+jπ(p)pu − βsi+jπ(p)pu ≡ (α − β)m2! (mod Iu+1)

to decide whether si + jπ(p)pu−1 is a solution of (7.1) or not. The above
algorithm programmed in Magma proved our assertion for given m2, p, k
in under a few seconds.

(ii) The very same algorithm proves this statement in even less running
time. �

8. Proof of Theorem 2.3

Proof. By (5.40) we infer that for any solution of the equation (2.6) we must
have

n ≤ 1077.

We will split the analysis into cases.

Case I. Assume m1! ≥ √
Fn.

Then we have
Fn ≤ (m1!)2 (8.1)

and we further split our treatment of Case I. into subcases:

Case I(1). Assume m1 ≤ 104.
Then we have

m1! < (m1)m1 ≤ 104·104 ,

and by (8.1) we obtain

Fn < (m1!)2 < 108·104 , so n < 3.828 · 105.

By Lemma 7.1, we have

ν2(Fn) ≤ 2 + ν2(n/3) ≤ 2 + log2
n

3
≤ 2 + log2

3.828 · 105

3
< 19,

ν3(Fn) ≤ 1 + ν3(n/4) ≤ 1 + log3
n

4
≤ 1 + log3

3.828 · 105

4
< 12,

ν5(Fn) ≤ ν5(n) ≤ log5 n ≤ log5(3.828 · 105) < 8,

ν7(Fn) ≤ 1 + ν7(n/8) ≤ 1 + log7
n

8
≤ 1 + log7

3.828 · 105

8
< 7.

Case I(1)(i). Assume m2 ≥ 49.



  116 Page 24 of 32 A. Bérczes et al. Results Math

Then we clearly have

ν2(m1! + m2!) ≥ 47 > ν2(Fn), ν3(m1! + m2!) ≥ 22 > ν3(Fn),

ν5(m1! + m2!) ≥ 12 > ν5(Fn), ν7(m1! + m2!) ≥ 8 > ν7(Fn).

Thus, Eq. (2.6) implies

ν2(s) = ν2(Fn), ν3(s) = ν3(Fn),

ν5(s) = ν5(Fn), ν7(s) = ν7(Fn).
(8.2)

Now we compute the list L of all values

m1! + m2! for 49 ≤ m2 < m1 ≤ 104

and we check for each 1 ≤ n ≤ 3.828 · 105 whether Fn − s ∈ L, where

s = 2ν2(Fn)3ν3(Fn)5ν5(Fn)7ν7(Fn).

Since the size of L and the number of values for Fn is large, and also the values
with which we need to do arithmetic are too large, instead of checking equality
we check congruences

Fn − s ≡ m1! + m2! (mod p)

for p = 20011, 20021, 20023. Denote the list L mod p by Lp. First for every
u = 0, 1, . . . , 20010 we collected all indices i such that L20011[i] = u in a
list Ju. Then for the smallest positive residue u ≡ Fn − s (mod 20011) and
for all indices j in J [u] we checked if L20021[j] ≡ Fn − s (mod 20021) and
L20023[j] ≡ Fn − s (mod 20023) holds. If for all j in J [u] one of the above
congruences was false, then we excluded n from the list of possible solutions
(at least in this case). The computation took 1085 s on an Intel Xeon W-2245
3.90GHz CPU processor and the only values for n which were not excluded
by this procedure were n = 198489, 228652, 375659. Then, as explained above,
s = 2ν2(Fn)3ν3(Fn)5ν5(Fn)7ν7(Fn) is fixed and we computed the value Fn − s. If
Fn − s = m1! + m2! with m1 > m2, then m1! is the largest factorial which is
smaller than Fn − s, and we checked that Fn − s − m1! is not a factorial, thus
excluding that value of n, too. In the three remaining cases we obtained the
following data:

n s m1

198489 2 11444
228652 3 12987
375659 1 20271

and we conclude that none of the values n = 198489, 228652, 375659 is a
solution in this case.

Case I(1)(ii). Assume 1 ≤ m2 ≤ 48 and m1 ≥ 56.



Additive Diophantine Equations with Binary Recurrences Page 25 of 32   116 

Then we additionally have m1 − m2 ≥ 8 which clearly implies

νp(m1! + m2!) = νp(m2!) for p ∈ S.

Thus, whenever for every p ∈ S either νp(m2!) �= νp(Fn) or

νp(m2!) = νp(Fn) and
Fn

pνp(Fn)
�≡ m2!

pνp(m2!)
(mod p),

then we must have

νp(s) = min(νp(m2!), νp(Fn)) for p ∈ S.

Thus, s is explicitly given. So, we compute Fn − s and exclude all such values
of n for which Fn − s is not the sum of two factorials, as we did it in Case
I(1)(i). There are 1338980 cases when the pairs (n,m2) do not fulfill the above
conditions. For each such pair (n,m2) we compute for each p ∈ S the value
νp(Fn − m2!) and we see that

νp(Fn − m2!) < νp(56!) < νp(m1!),

which implies that

νp(s) = νp(Fn − m2!) for p ∈ S.

Thus, also in these cases s is explicitly given, and then we compute Fn −s and
exclude all such values of n for which Fn −s is not the sum of two factorials, as
we did it in Case I(1)(i). There are only 3 cases where the above procedure does
not work, namely (n,m2) = (1, 1), (2, 1), (3, 2), when we do have Fn = m2!,
which clearly cannot lead to a solution. The computation of this case took
2018 s on a Intel Xeon W-2245 3.90 GHz CPU processor.

Case I(1)(iii). Assume 1 ≤ m2 ≤ 48 and m1 ≤ 55.
Then

m1! ≤ 5555

and by (8.1) we obtain

Fn ≤ (m1!)2 ≤ 55110, so n < 920.

Now for n < 920, 1 ≤ m2 ≤ 48 and m2 < m1 ≤ 55 we check whether

Fn − m1! − m2! ∈ S ,

and if yes, then we have found a solution of our equation. Altogether, we
found the solutions listed in Theorem 2.3. This case had a running time of a
few seconds. (Clearly, one could also check for the condition Fn ≤ (m1!)2 if
interested only on the solutions belonging to Case I.)
Case I(2). Assume m1 > 104.

In this case we still have (8.1) (i.e. Fn ≤ (m1!)2) since we are in a subcase
of Case I. Further, recall that by (5.40) all solutions of the Eq. (2.6) have

n ≤ 1077. (8.3)



  116 Page 26 of 32 A. Bérczes et al. Results Math

This together with Lemma 7.1 shows that

ν2(Fn) ≤ 2 + ν2(n/3) ≤ 2 + log2
n

3
≤ 2 + log2

1077

3
< 257,

ν3(Fn) ≤ 1 + ν3(n/4) ≤ 1 + log3
n

4
≤ 1 + log3

1077

4
< 162,

ν5(Fn) ≤ ν5(n) ≤ log5 n ≤ log5(1077) < 111,

ν7(Fn) ≤ 1 + ν7(n/8) ≤ 1 + log7
n

8
≤ 1 + log7

1077

8
< 92.

Case I(2)(i). Assume m1 > 104 and m2 ≥ 600.
Then we have

ν2(m1! + m2!) ≥ 596 > ν2(Fn), ν3(m1! + m2!) ≥ 297 > ν3(Fn),

ν5(m1! + m2!) ≥ 148 > ν5(Fn), ν7(m1! + m2!) ≥ 98 > ν7(Fn).
(8.4)

This proves that we again have (8.2) implying that

s ≤ 225731625111792.

Using Lemma 7.3, we obtain

ν2(Fn − s) < 1730 log(6s2) log2 n ≤ 1730 log(2515332552227184) log2(1077)
< 1010.9.

This gives
m2

2
+

m2

4
+

m2

8
≤ ν2(m2!) = ν2(Fn − s) = 1010.9.

Thus, m2 ≤ 8
7 · 1010.9 < 1011 and

m2! ≤ mm2
2 ≤ (1011)10

11
< 1011·1011 .

Hence,

m2! + s ≤ 1011·1011 + 225731625111792 < 2 · 1011·1011 .

Now we use again Lemma 7.3 to obtain

ν2(Fn − (s + m2!)) < 1730 log(6(s + m2!)2) log n

≤ 1730 log(6 · 4 · 1022∗1011) log2(1077) < 1020.45,

and consequently
m1

2
< ν2(m1!) = ν2(Fn − (s + m2!)) < 1020.45.

We get m1 < 2 · 1020.45 < 1020.8 and this implies

m1! ≤ mm1
1 ≤ (1020.8)10

20.8
< 1020.8·1020.8

< 1010
22.12

.

Now we get

Fn = m1! + m2! + s ≤ 1010
22.12

+ 1011·1011 + 225731625111792 < 2 · 1010
22.12

,



Additive Diophantine Equations with Binary Recurrences Page 27 of 32   116 

so

n < 1023.

We repeat the above procedure. Using Lemma 7.1, this shows that

ν2(Fn) ≤ 2 + ν2(n/3) ≤ 2 + log2
n

3
≤ 2 + log2

1023

3
< 77,

ν3(Fn) ≤ 1 + ν3(n/4) ≤ 1 + log3
n

4
≤ 1 + log3

1023

4
< 48,

ν5(Fn) ≤ ν5(n) ≤ log5 n ≤ log5(1023) < 33,

ν7(Fn) ≤ 1 + ν7(n/8) ≤ 1 + log7
n

8
≤ 1 + log7

1023

8
< 28.

By the assumption m2 ≥ 600 we get again (8.4) so equations (8.2) hold im-
plying that

ν2(s) < 77, ν3(s) < 48,

ν5(s) < 33, ν7(s) < 28.
(8.5)

Now using a short computer program we consider the equation

Fn = m1! + m2! + s

modulo primes between 100 and 600. For each such prime p we have

Fn ≡ s (mod p)

and the computer search shows that this congruence is fulfilled simultaneously
for all primes between 100 and 600 if and only if

s ∈ {1, 2, 3, 5, 8, 21, 144}.

That is, we must have

s = Fm for m = 1, 2, 3, 4, 5, 6, 8, 12.

Now our Eq. (2.6) takes the form

Fn − Fm = m1! + m2! (8.6)

with m = 1, 2, 3, 4, 5, 6, 8, 12. By Lemma 7.4, in Eq. (8.6) the parity of n and
m must be the same. So, we can use Lemma 7.5 and we obtain

F(n−δm)/2L(n+δm)/2 = m1! + m2!,

where δ = ±1. Recall that since m2 ≥ 600, we have

ν2(m1! + m2!) ≥ 596,

and since ν2(Lk) ≤ 2 (see Lemma 7.2), we obtain that

ν2(F(n−δm)/2) ≥ 594.

However, this shows that

n ≥ 3 · 2592 > 1077,



  116 Page 28 of 32 A. Bérczes et al. Results Math

which contradicts (8.3). So, we have shown that in Case I(2)(i) our equation
has no solution.

Case I(2)(ii) Assume that m1 > 104 and m2 < 600.
Now we show that in this case

ν2(s) < 267, ν3(s) < 168,

ν5(s) < 114, ν7(s) < 95.
(8.7)

For if not assume for example that ν2(s) ≥ 267. Consider the Eq. (2.6) as a
congruence modulo 2267. Thus we obtain that for any solution of (2.6) fulfilling
the conditions of this subcase we have

Fn ≡ m2! (mod 2267).

However, by Lemma 7.6 (i), this has no solutions with 4 ≤ n ≤ 1077. But
solutions with n > 1077 do not exist at all, and since m1 is large n < 4 also
cannot happen in this case. So we conclude that if there exists a solution in
the present subcase, then it must have ν2(s) < 267. A similar reasoning proves
the other inequalities of (8.7).

Now since s ≤ 226731685114795 we may use again the ideas implemented
in Case I(2)(i). We have

m2! + s ≤ 600! + 226731685114795 ≤ 101410

and using again Lemma 7.3 we obtain

ν2(Fn − (s + m2!)) < 1730 log(6(s + m2!)2) log2 n

≤ 1730 log(6 · 102820) log2(1077) < 1011.55.

Consequently,
m1

2
< ν2(m1!) = ν2(Fn − (s + m2!)) < 1011.55,

so we get m1 < 2 · 1011.55 < 1012. This implies

m1! ≤ mm1
1 ≤ (1012)10

12
< 1012·1012 < 1010

13.1
.

Now we conclude by

Fn = m1! + m2! + s ≤ 1010
13.1

+ 600! + 226731685114795 < 2 · 1010
13.1

,

so

n < 1015.

Using Lemma 7.6 (ii) the same way as we used its statement (i) at the beginning
of this case, we obtain that

ν2(s) < 56, ν3(s) < 36,

ν5(s) < 26, ν7(s) < 21.
(8.8)



Additive Diophantine Equations with Binary Recurrences Page 29 of 32   116 

Now using a short computer program as in Case I(2)(i) we considered the
equation

Fn = m1! + m2! + s

modulo primes between 100 and 800. For each such prime p we have

Fn ≡ m2! + s (mod p)

and the computer search shows that this congruence is fulfilled simultaneously
for all primes between 100 and 800 if and only if

m2! + s ∈ {2, 3, 5, 8, 13, 21, 34, 55, 144, 377, 2584}.

That is, we must have

m2! + s = Fm for m = 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 18.

The running time for this computation was 112 s on a Intel Xeon W-2245
3.90GHz CPU processor.

Now our Eq. (2.6) takes the form

Fn − Fm = m1! (8.9)

with m = 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 18. By Lemma 7.4, in Eq. (8.9) the parity
of n and m must be the same. So, we can use Lemma 7.5 and we obtain

F(n−δm)/2L(n+δm)/2 = m1!,

where δ = ±1. Recall that by m1 ≥ 104 we have

ν2(m1!) ≥ 9995,

and since by Lemma 7.2 we have ν2(Lk) ≤ 2, we obtain that

ν2(F(n−δm)/2) ≥ 9993.

However, this shows that

n ≥ 3 · 29993 > 1077,

which contradicts (8.3). So we have shown that in Case I(2)(i) our equation
has no solution.

Case II. We assume m1! ≤ √
Fn.

Then from Eq. (2.6) with the notation s = 2a3b5c7d we obtain

1 − 2a3b
√

5
2c+1

7dα−n = (
√

5 · m1! +
√

5 · m2! + α−n)α−n (8.10)

and by the condition of Case II we have
∣∣∣1 − 2a3b

√
5
2c+1

7dα−n
∣∣∣ <
(
2
√

5
√

Fn + α−n
)

α−n ≤

≤
(
2 4
√

5α
n
2 + α−n

)
α−n ≤ 4

α
n
2

.
(8.11)



  116 Page 30 of 32 A. Bérczes et al. Results Math

We clearly may assume that n > 10, so 4/αn/2 < 0.4. Now using Lemma 3.4
we infer that

|a log 2 + b log 3 + (2c + 1) log
√
5 + d log 7 − n logα| <

− log 0.6

0.4
· 4 · α− n

2 <
6

α
n
2

.

The conditions of Lemma 3.3 are fulfilled with

n = 5, α1 = log 2, α2 = log 3, α3 = log
√

5, α4 = log 7, α5 = log α,

and

x1 = a, x2 = b, x3 = 2c + 1, x4 = d, x5 = −n, X = 2 · 1070 + 1,

c2 = 6, c5 = 0.5 · log α, H = 1070, q = 1.

Choosing C = 10400 and using the LLL-algorithm implemented in Magma we
obtain an LLL-reduced basis of L. By Lemma 3.2 we get a lower bound c6 for
the length of the shortest vector of L. Finally, Lemma 3.3 provides the upper
bound H ≤ 3077. Now using Lemma 3.3 with

H = 3078, X0 = 2 · 3078 + 1, C = 1028

by the above procedure we infer that H ≤ 219. Now we use once more Lemma
3.3 with H = 220, X0 = 2 · 220 + 1, C = 1024, and by the above procedure we
get

H ≤ 199.

This shows that n < 200 and consequently, m2 < m1 < 36. So to conclude the
proof of our theorem for all natural numbers n < 200 and m2 < m1 < 36 with
Fn − m1! − m2! > 0 we check whether there exist a, b, c, d ∈ N such that

Fn − m1! − m2! = 2a3b5c7d,

and we get exactly the solutions listed in Theorem 2.3. (Clearly, one could also
check the condition Fn > (m1!)2 if interested only in the solutions belonging
to Case II). �

Acknowledgements

We thank the anonymous referee for comments which improved the quality of
our manuscript.

Author contributions All authors contributed to this research.

Funding Open access funding provided by University of the Witwatersrand.
The research of Authors A.B., L.H. and I. P. was supported in part by the
Eőtvős Loránd Research Network (ELKH), by the NKFIH Grants 128088 and



Additive Diophantine Equations with Binary Recurrences Page 31 of 32   116 

130909, and the Projects EFOP-3.6.1-16-2016-00022 cofinanced by the Euro-
pean Union and the European Social Fund.

Declarations
Conflict of interest The authors have no relevant financial or non-financial
interests to disclose.

Open Access. This article is licensed under a Creative Commons Attribution 4.0
International License, which permits use, sharing, adaptation, distribution and re-
production in any medium or format, as long as you give appropriate credit to the
original author(s) and the source, provide a link to the Creative Commons licence,
and indicate if changes were made. The images or other third party material in
this article are included in the article’s Creative Commons licence, unless indicated
otherwise in a credit line to the material. If material is not included in the article’s
Creative Commons licence and your intended use is not permitted by statutory regu-
lation or exceeds the permitted use, you will need to obtain permission directly from
the copyright holder. To view a copy of this licence, visit http://creativecommons.
org/licenses/by/4.0/.

References

[1] Bollman, M., Hernández, S.H., Luca, F.: Fibonacci numbers which are sums of
three factorials. Publ. Math. Debrecen 77, 211–224 (2010)

[2] Grossman, G., Luca, F.: Sums of factorials in binary recurrence sequences. J.
Number Theory 93, 87–107 (2002)

[3] Gúzman Sanchez, S., Luca, F.: Linear combinations of factorials and S-units in
a binary recurrence sequence. Ann. Math. Qué. 38, 169–188 (2014)

[4] Lengyel, T.: The order of the Fibonacci and Lucas numbers. Fibonacci Quart.
33, 234–239 (1995)

[5] Lenstra, A.K., Lenstra, H.W., Jr., Lovász, L.: Factoring polynomials with ratio-
nal coefficients. Math. Ann. 261(4), 515–534 (1982)

[6] Luca, F., Szalay, L.: Fibonacci numbers of the form pa±pb+1. Fibonacci Quart.
45(2007), 98–103 (2008)

[7] Pethö, A., de Weger, B.M.M.: Products of prime powers in binary recur-
rence sequences. I. The hyperbolic case, with an application to the generalized
Ramanujan-Nagell equation. Math. Comp 47, 713–727 (1986)

[8] Rosser, J.B., Schoenfeld, L.: Approximate formulas for some functions of prime
numbers. Illinois J. Math. 6, 64–94 (1962)

[9] Smart, N.P.: The Algorithmic Resolution of Diophantine Equations, London
Mathematical Society Student Texts, vol. 41. Cambridge University Press, Cam-
bridge (1998)

[10] Yu, K.: p-adic logarithmic forms and group varieties. II. Acta Arith. 89, 337–378
(1999)

http://creativecommons.org/licenses/by/4.0/
http://creativecommons.org/licenses/by/4.0/


  116 Page 32 of 32 A. Bérczes et al. Results Math

Attila Bérczes and István Pink
Institute of Mathematics
University of Debrecen
P.O. Box 400, Debrecen 4010
Hungary
e-mail: berczesa@science.unideb.hu;

pinki@science.unideb.hu

Lajos Hajdu
ELKH-DE Equations, Functions, Curves and Their Applications Research Group
Institute of Mathematics
University of Debrecen
P.O. Box 400, Debrecen 4010
Hungary
e-mail: hajdul@science.unideb.hu

Florian Luca
School of Maths
Wits University
Private Bag 3, Wits 2050
South Africa
e-mail: florian.luca@wits.ac.za

and

Centro de Ciencias Matemáticas
UNAM
Morelia
Mexico

Received: November 3, 2022.

Accepted: February 16, 2023.

Publisher’s Note Springer Nature remains neutral with regard to jurisdic-
tional claims in published maps and institutional affiliations.


	Additive Diophantine Equations with Binary Recurrences, mathcalS-Units and Several Factorials
	Abstract
	1. Introduction
	2. Our Results
	3. Linear Forms in p-Adic Logarithms
	4. Preliminary Results on Binary Recurrence Sequences
	5. Proof of Theorem 2.1
	6. Proof of Theorem 2.2
	7. Preliminary Results on Fibonacci and Lucas Numbers
	8. Proof of Theorem 2.3
	Acknowledgements
	References