Integers 9(2009), 375–400
DOI 10.1515/INTEG.2009.031 © de Gruyter 2009
.Fn/DFm
Florian Luca and Florin Nicolae
Abstract. We show that 1,2and 3are the only Fibonacci numbers whose Euler functions
are also Fibonacci numbers.
Keywords. Fibonacci numbers, Euler function.
AMS classification. 11B39, 11N36.
1 Introduction
The Fibonacci sequence .Fn/n0is given by F0D0,F1D1and FnC2DFnC1CFn
for all n0. For a positive integer mwe let .m/ be the Euler function of m. We
prove the following result:
Theorem 1. The only positive integers nsuch that .Fn/DFmfor some positive
integer mare nD1; 2; 3 or 4.
Recall that if we put ˛D.1 Cp5/=2 and ˇD.1 p5/=2, then
FnD˛nˇn
˛ˇfor nD0; 1; : : : :
This is sometimes called the Binet formula. We also put .Ln/n0for the companion
Lucas sequence of the Fibonacci sequence given by L0D2,L1D1and LnC2D
LnC1CLnfor all n0. The Binet formula for the Lucas numbers is
LnD˛nCˇnfor nD0; 1; : : : :
There are many relations between the Fibonacci and the Lucas numbers, such as
L2
n5F 2
nD4.1/n;(1)
or F2n DFnLn, as well as several others which we will mention when they will
be needed. We refer the reader to Chapter 5 in [6], or to Ron Knott’s web-site on
Fibonacci numbers [5] for such formulae.
During the preparation of this paper, the first author was supported in part by Grant SEP-CONACyT 46755.
Brought to you by | Technische Universität Berlin
Authenticated
Download Date | 10/1/18 10:34 AM
376 Florian Luca and Florin Nicolae
2 A Bird’s-eye View to the Proof of Theorem 1
We start with a computation showing that there are no other solutions than the obvious
ones up to n256. Thus, we may assume that n > 256. Next we show that any
potential solution is very large, at least as large as 31059. Let kbe the number of
distinct prime factors of Fn. Then 2k1j.Fn/DFm. Since the power of 2in
a Fibonacci number is small, it follows that kis small. Since Fndoes not have too
many prime factors, we get that nmis small. This implies that gcd.Fn; Fm/is
also small. Next we bound iteratively the prime factors of Fn. As a byproduct of this
calculation, we get a lower bound for kin terms of n. Since all odd prime factors of
Fnare congruent to 1modulo 4when nis odd, this lower bound on kcompared with
the fact that 4k1jFmare sufficient to get a contradiction when nis odd. Hence it
suffices to deal with the case when nis even. Writing nD21n0with n0odd, one
proves that 21jnm, therefore the power of 2in nis small. Next, we bound
`Dnm. The bound on `together with a recent calculation of McIntosh and
Roettger [10] dealing with a conjecture of Ward about the exponent of apparition of
a prime in the Fibonacci sequence shows that if one writes nDU V , where Uand
Vare coprime, all primes dividing Udivide m, and no prime dividing Vdivides m,
then U`. Thus, Uis small. Next, we use sieve methods to show that the minimal
prime factor p1of Vis also small. McIntosh and Roettger’s calculation together with
the Primitive Divisor Theorem now implies that n0Dp1, therefore nis a power of 2
times a small prime, and the upper bounds for nare lower than the lower bounds for
nobtained previously, which finishes the proof. The entire proof is computer aided
and several small calculations are involved at each step.
3 Proof of Theorem 1
We shall assume that n>2and we shall write
FnDp˛1
1p˛k
k;
where p1< < pkare distinct primes and ˛1; : : : ; ˛kare positive integers. Since
Fn> 1, it follows that m<n.
3.1 The Small Values of n
A MATHEMATICA code confirmed that the only solutions of the equation
.Fn/DFm(2)
in positive integers mn256 have n2 ¹1; 2; 3; 4º. From now on, we assume
that n > 256. We next show that 4jFm. Assuming that this is not so, we would get
that 4−.Fn/. Thus, Fn2 ¹1; 2; 4; p; 2pºwith some prime p3 .mod 4/ and
Brought to you by | Technische Universität Berlin
Authenticated
Download Date | 10/1/18 10:34 AM
.Fn/DFm377
some positive integer . Since n257, it follows that Fn2 ¹p; 2pº. Results from
[2] and [3] show that > 1 is impossible in this range for n. Let us now assume that
D1. If FnDp, then
FmD.Fn/D.p/ Dp1DFn1;
which leads to 1DFnFmFnFn1DFn2F255, which is a contradiction.
If FnD2p, then
FmD.Fn/D.2p/ Dp1D.Fn2/=2;
therefore 2DFn2Fm. If mDn1, we then get 2DFn2Fn1DFn2Fn1D
Fn3< 0, which is impossible, while if mn2, we then get 2DFn2Fm
Fn2Fn2DFn1Fn2DFn3F254, which is again impossible. Hence,
4jFm. In particular, 6jm. It follows from the results from [7] that .Fn/F.n/.
Thus
m.n/ n
elog log nC2:50637= log log n;
where the second inequality above is inequality (3.42) on page 72 in [13]. Here, is
Euler’s constant. Since e< 1:782, and the inequality
n
1:782 log log nC2:50637= log log n> 50
holds for all n256, we get that m50. Put `Dnm. Since mis even, we have
that ˇm> 0, therefore
Fn
FmD˛nˇn
˛mˇm>˛n1
˛mD˛`1
˛m> ˛`1010;(3)
where we used the fact that ˛50 < 3:55319 1011 < 1010. We distinguish the
following cases.
Case 1. gcd.n; 6/ D1.
In this case `1, therefore inequality (3) gives
Fn
Fm
> ˛ 1010 > 1:61803:
For each positive integer s, let z.s/ be the smallest positive integer tsuch that sjFt.
It is known that this exists and sjFnif and only if z.s/ jn. This is also referred to
as the order of apparition of nin the Fibonacci sequence. Since nis coprime to 6, it
follows that Fnis divisible only by primes psuch that gcd.z.p/; 6/ D1. Among the
first 1000 primes, there are precisely 212 of them with this property. They are
P1D ¹5; 13; 37; 73; : : : ; 7873; 7901º:
Brought to you by | Technische Universität Berlin
Authenticated
Download Date | 10/1/18 10:34 AM
378 Florian Luca and Florin Nicolae
In our case, the following holds:
k
Y
iD111
pi1
DFn
Fm
> 1:61803:
Writing qjfor the jth prime number in P1, we checked with MATHEMATICA that the
smallest ssuch that s
Y
jD111
qj1
> 1:61803
is sD99. Thus, k99. Since nis odd and every prime factor pof Fnis also
odd, reducing relation (1) modulo p, we get L2
n 4 .mod p/ for all pDpiand
iD1; : : : ; k. Thus, pi1 .mod 4/ for all iD1; : : : ; k. Hence, 4kjQk
iD1.pi1/ j
.Fn/DFm, therefore 22k jFm. So, z.22k/jm. Since z.2s/D32s2for all
s3, we get that 322k2jm. In particular,
n322k232196 > 3 1059:(4)
Case 2. 2knand gcd.n; 3/ D1.
In this case, since mis also even, we have that `Dnmis even. Hence, `2,
and Fn
Fm
> ˛21010 > 2:61803:
If pis any prime factor of Fn, then, as in Case 1 above, we get that z.p/ is coprime
to 3and is not a multiple of 4. There are 1235 primes pamong the first 3000 of them
with this property. They are
P2D ¹5; 11; 13; 29; : : : ; 27397; 27431º;
and
Y
q2P211
q1
D2:3756 : : : < 2:61803 < Fn
Fm
:
This shows that k > 1235. Since piis odd for all iD1; : : : ; k, we get that 2kj
.Fn/DFm, therefore z.2k/jm. Thus,
n>m32k2321234 > 8 10371:(5)
Case 3. 3jnand gcd.n; 2/ D1.
In this case, since 3jm, we get that `3, therefore
Fn
Fm
> ˛31010 > 4:23606:
Brought to you by | Technische Universität Berlin
Authenticated
Download Date | 10/1/18 10:34 AM
.Fn/DFm379
All prime factors pof Fnhave z.p/ odd. There are 1005 primes among the first 3000
of them with this property. They are
P3D ¹2; 5; 13; 17; : : : ; 27397; 27437º:
Since
Y
q2P311
q1
< 4:12239 < 4:23606 < Fn
Fm
;
we get that k1006. Since piis odd for all iD2; : : : ; k, we get that 2k1j.Fn/j
Fm, therefore z.2k1/jm. Thus,
n>m32k3321003 > 2 10302:(6)
Case 4. 4jnand gcd.n; 3/ D1.
Write nD4n0. Since n > 256, it follows that n0> 64. Note that
F4n0DF2n0L2n0DFn0Ln0L2n0:
Since L2
n05F 2
n0D ˙4, and L2n0DL2
n0˙2, it follows that the three numbers
Fn0,Ln0, and L2n0have disjoint sets of odd prime factors. The sequence .Ls/s0
is periodic modulo 8with period 12. Listing its first twelve members, one sees that
Lsis never a multiple of 8. Thus, there exist two distinct odd primes q1jLn0and
q2jL2n0. A result of McDaniel [9] says that if s > 48, then Fshas a prime factor
p1 .mod 4/. Let us give a quick proof of this fact. If shas a prime factor r5,
then FrjFsand every prime factor pof Fris odd (because Fris even only when
3jr). Reducing equation (1) with nDrmodulo p, we get L2
r 4 .mod p/, so
p1 .mod 4/. Thus, it remains to deal with the case when sD2a3bfor some
nonnegative integers aand b. Since 4481 jF64,769 jF96,17 jF9, and 4481,769,
and 17 are all primes congruent to 1modulo 4, it follows easily that the largest ssuch
that Fshas no prime factor p1 .mod 4/ is
F48 D2632723 47 1103:
Since n0> 64 > 48, it follows that Fn0has a prime factor q31 .mod 4/. Now
q1q2q3jFn, therefore 16 j.q11/.q21/.q31/ j.Fn/jFm, showing that
z.16/ jm. Thus, 12 jm. Since we now know that both nand mare multiples of 4,
we get that `4. Hence,
Fn
Fm
> ˛41010 > 6:8541:
The prime factors pof Fnhave z.p/ coprime to 3. There are 1856 such primes p
among the first 3000, and they are
P4D ¹3; 5; 7; 11; : : : ; 27431; 27449º:
Brought to you by | Technische Universität Berlin
Authenticated
Download Date | 10/1/18 10:34 AM
380 Florian Luca and Florin Nicolae
Since
Y
q2P311
q1
< 5:30404 < 6:8541 < Fn
Fm
;
we get that k1857. Since 2kj.Fn/DFm, we deduce that z.2k/jm. Thus,
n>m32k2321855 > 7 10558:(7)
Case 5. 6jn.
In this case, `6, therefore
Fn
Fm
> ˛61010 > 17:9442:
If qistands for the ith prime, then we checked that the smallest ssuch that
s
Y
iD111
qi1
> 17:9442
is sD2624. Thus, k2624. We now get that 2k1j.Fn/DFm, therefore
n>mz.2k1/D32k3322621 > 2 10789:(8)
To summarize, from inequalities (4), (5), (6), (7) and (8), we have that n>31059.
3.2 Bounding `in Terms of n
We saw in the preceding section that k99. We start by bounding kfrom above.
Since nis large, McDaniel’s result shows that Fnhas at least one prime factor p1
.mod 4/. Since at least k1of the prime factors of Fnare odd, and at least one of
them is congruent to 1modulo 4, we get that 2kj.Fn/DFm. Thus, 32k2jm.
We now get that
n>m32k2;
therefore
k < k.n/ WD log n
log 2C2log 3
log 2:
Let qjbe the jth prime number. Inequality (3.13) on page 69 in [13] shows that in
our range we have
qk< q.n/ WD k.n/.log k.n/ Clog log k.n//:
Now clearly
Fm
FnD
k
Y
iD111
piY
2pq.n/ 11
p>1
elog q.n/ 1C1=.2.log q.n//2/;
Brought to you by | Technische Universität Berlin
Authenticated
Download Date | 10/1/18 10:34 AM
.Fn/DFm381
where the last inequality is inequality (3.29) on page 70 in [13]. That inequality is
valid only for q.n/ 286, which is fulfilled for us since n31059. Therefore,
k.n/ 197 and q.n/ > 1368 > 286. We thus get that
elog q.n/ Ce
2log q.n/ >Fn
FmD˛nˇn
˛mˇm>˛n1
˛m:
In the above inequality, we used the fact that mis even, and therefore ˇm> 0. Thus,
e.log q.n//.1 Cı/ > ˛nm;
where
ıWD 1
2.log q.n//2Ce
˛mlog q.n/:
Since q.n/ > 1368,m50 and e< 0:562, we get that ı < 0:0096. Thus,
nm < log.e.1 Cı//
log ˛Clog log q.n/
log ˛:
We now take a closer look at q.n/. We show that
q.n/ < .k.n/ 2Clog 3= log 2/1:4:
For this, it suffices that the inequality
k.n/.log k.n/ Clog log k.n// < .k.n/ 2Clog 3= log 2/1:4
holds in our range for n. We checked with MATHEMATICA that the last inequality
above is fulfilled whenever k.n/ > 90, which is true in our range for n. Since k.n/
2Clog 3= log 2Dlog n= log 2, we deduce by taking logarithms above that
log q.n/ 1:4 log.log n= log 2/;
leading to
log log q.n/ log 1:4 Clog.log log nlog log 2/
Dlog 1:4 Clog log log nClog 1log log 2
log log n
<log log log nClog 1:4 log log 2
log log n;
where in the above chain of inequalities we used the fact that the inequality log.1 C
x/ < x holds for all real numbers x > 1,x¤0. We thus get that
nm < 1
log ˛log.e1:0096/ Clog 1:4 log log 2
log log nClog log log n
log ˛
< 2:075 Clog log log n
log ˛;
where we used the fact that n>31059. We record this for future use as follows.
Brought to you by | Technische Universität Berlin
Authenticated
Download Date | 10/1/18 10:34 AM
382 Florian Luca and Florin Nicolae
Lemma 2. If n>4, then n>31059 and
nm < 2:075 Clog log log n
log ˛:
3.3 Bounding the Primes pifor iD1; : : : ; k
Here, we follow a similar plan of attack as the proof of Theorem 3 in [12]. Write
FnDp1pkA; where ADp˛11
1p˛k1
k:(9)
Clearly, Aj.Fn/, therefore AjFm. Since also AjFn, we get that Ajgcd.Fn; Fm/.
Now gcd.Fn; Fm/DFgcd.n;m/ jFnm, because gcd.n; m/ jnm. Since the
inequality Fs˛s1holds for all positive integers s, it follows that
AFnm˛nm1< ˛1:075 log log n; (10)
where the last inequality follows from Lemma 2. We next bound the primes pifor
iD1; : : : ; k. We write
k
Y
1D111
piD.Fn/
FnDFm
Fn
;
therefore
1
k
Y
iD111
piD1Fm
FnDFnFm
FnFnFn1
FnDFn2
Fn
:
Using the inequality
1.1x1/.1xs/x1CCxsvalid for all xi2Œ0; 1; i D1; : : : ; s; (11)
we get
Fn2
Fn1
k
Y
iD111
pi
k
X
iD1
1
pi
<k
p1
;
therefore
p1< k Fn
Fn2< 3k; (12)
where we used the fact that Fn< 3Fn2. (This last inequality is equivalent to Fn1C
Fn2< 3Fn2, or Fn1< 2Fn2, or Fn2CFn3< 2Fn2, or Fn3< Fn2,
which is certainly true in our range for n.) We now show by induction on the index
i2 ¹1; : : : ; kº, that if we put
uiWD
i
Y
jD1
pj;
Brought to you by | Technische Universität Berlin
Authenticated
Download Date | 10/1/18 10:34 AM
.Fn/DFm383
then
ui< .2˛3:075.log log n/k/.3i1/=2:(13)
For iD1, this becomes
p1< 2˛3:075.log log n/k
which is implied by estimate (12) and the fact that for n > 3 1059 we have the
estimate 2˛3:075 log log n > 43 > 3. We now assume that i2 ¹1; : : : ; k 1ºand that
the estimate (13) is fulfilled, and we shall prove estimate (13) for ireplaced by iC1.
We have
k
Y
jDiC111
pjDp1pi
.p11/ .pi1/ Fm
FnDp1pi
.p11/ .pi1/ ˛mˇm
˛nˇn;
which we rewrite as
1
k
Y
jDiC111
pjD1p1pi
.p11/ .pi1/ ˛mˇm
˛nˇn
D˛m..p11/ .pi1/˛nmp1pi/
.p11/ .pi1/.˛nˇn/
Cˇm.p1piˇnm.p11/ .pi1//
.p11/ .pi1/.˛nˇn/
DW XCYI
where
XWD ˛m..p11/ .pi1/˛nmp1pi/
.p11/ .pi1/.˛nˇn/;
YWD ˇm.p1piˇnm.p11/ .pi1//
.p11/ .pi1/.˛nˇn/:
Since mis even and jˇj< 1, we see easily that Y0. Furthermore, since nm>0,
ˇD ˛1, and no power of ˛with positive integer exponent is a rational number, it
follows that XY ¤0. Thus, Y > 0. Let us suppose first that X < 0. Then
1
k
Y
jDiC111
pi< Y < 2p1pi
˛m.p11/ .pi1/.˛nˇn/
<2Fn
.Fn/.˛mˇm/.˛nˇn/D2
5F 2
m
:
Brought to you by | Technische Universität Berlin
Authenticated
Download Date | 10/1/18 10:34 AM
384 Florian Luca and Florin Nicolae
Since the left hand side of the above inequality is a positive rational number whose
denominator divides piC1pkjFn, it follows that this number is at least as large
as 1=Fn. Hence,
1
Fn
<2
5F 2
m
;
giving
F2
m<2
5Fn:
Since the inequalities ˛s2Fs˛s1hold for all s2, we get
˛2m4F2
m<2
5Fn2
5˛n1;
therefore
2m < 3 Clog.2=5/
log ˛Cn:
Using Lemma 2, we have
m>n2:075 log log log n
log ˛:
Combining these inequalities, we get
n < 7:15 Clog.2=5/
log ˛C2log log log n
log ˛< 5:25 C2log log log n
log ˛;
which is impossible in our range for n. Hence, the only chance is that X > 0. Since
also Y > 0, we get that
1
k
Y
jDiC111
pj> X:
Now note that
..p11/ .pi1/˛nmp1pi/..p11/ .pi1/ˇnmp1pi/
is a nonzero integer (by Galois theory since ˇis the conjugate of ˛), therefore its
absolute value is 1. Since the absolute value of the second factor is certainly <
2p1piand the first factor is positive (because X > 0), we get that
.p11/ .pi1/˛nmp1pi>1
2p1pi
:
Hence,
1
k
Y
jDiC111
pj> X > ˛m
2.p1pi/2.˛nˇn/>˛mˇm
2u2
i.˛nˇn/DFm
2u2
iFn
;
Brought to you by | Technische Universität Berlin
Authenticated
Download Date | 10/1/18 10:34 AM
.Fn/DFm385
which combined with inequality (11) leads to
Fm
2u2
iFn
< 1
k
Y
jDiC111
pj<
k
X
jDiC1
1
pj
<k
piC1
:
Thus,
piC1< 2ku2
iFn
Fm:
However, Fn
Fm
< ˛nmC1< ˛3:075 log log n;
by Lemma 2. Hence,
piC1< .2˛3:075klog log n/u2
i;
and multiplying both sides of the above inequality by uiwe get
uiC1< .2˛3:075klog log n/u3
i:
Using the induction hypothesis (13), we get
uiC1< .2˛3:075klog log n/1C3.3i1/=2 D.2˛3:075klog log n/.3iC11/=2;
which is precisely inequality (13) with ireplaced by iC1. This finishes the induction
proof and shows that estimate (13) holds indeed for all iD1; : : : ; k. In particular,
p1pkDuk< .2˛3:075klog log n/.3k1/=2;
which together with formula (9) and estimate (10) gives
FnDp1pkA < .2˛3:075klog log n/1C.3k1/=2 D.2˛3:075klog log n/.3kC1/=2:
Since Fn> ˛n2, we get
.n 2/ log ˛ < .3kC1/
2log.2˛3:075klog log n/:
Assume first that k2˛3:075 log log n. We then get that
.n 2/ log ˛ < .32˛3:075 log log nC1/ log.2˛3:075 log log n/;
which implies that n < 1016. This is false because n>31059. Thus, k >
2˛3:075 log log n, therefore we get
.n 2/ log ˛ < .3kC1/ log k:
Brought to you by | Technische Universität Berlin
Authenticated
Download Date | 10/1/18 10:34 AM
386 Florian Luca and Florin Nicolae
We also have that
kk.n/ log n
log 2C2log 3
log 2<log n
log 2C0:42:
Hence
3kC1 > .n 2/ log ˛
log.log n= log 2C0:42/;
so that
k > K.n/ WD 1
log 3log .n 2/ log ˛
log.log n= log 2C0:42/ 1:
3.4 The Case When nis Odd
Assume that nis odd. Then every odd prime factor piof Fnis congruent to 1modulo
4. Thus, 4k1j.Fn/DFm, therefore z.22k2/jm. So
n>mz.22k2/D322k4;
leading to
kL.n/ WD 2Clog.n=3/
2log 2:
Since also k > K.n/, we get that
1
log 3log .n 2/ log ˛
log.log n= log 2C0:42/ 1< 2 Clog.n=3/
2log 2:
This inequality gives n<5106, which is impossible since n>31059. This shows
that the case n > 4 and odd is impossible, therefore nhas to be even. Returning now
to estimates (5), (7), and (8), we also get that n>810371.
3.5 Bounding `
We write nD21n0, where n0is odd and 11. We start by bounding 1. Clearly,
11. If 12, then
F21DL2L211:
The numbers L2jare all odd for jD1; : : : ; 11, and since L2iDL2
2i1˙2
holds for all i2, it follows easily that L2i ˙2 .mod L2j/for all 1j < i.
This shows that gcd.L2i; L2j/D1for all 1j < i. In particular, F21is divisible
by at least 11distinct primes which are all odd. So, 211j.Fn/DFm. Thus,
assuming that 13, we get that 3213jm. Hence, 213divides both mand n,
so it also divides nm. This argument combined with Lemma 2 shows that,
218.n m/ < 16:6 C8log log log n
log ˛;
Brought to you by | Technische Universität Berlin
Authenticated
Download Date | 10/1/18 10:34 AM
.Fn/DFm387
and the last inequality above is true for 1< 3 as well. In particular, if n0D1, we
then get that
nD2116:6 C8log log log n
log ˛;
leading to n < 18, which is false. Thus n0> 1, therefore nhas odd prime factors.
We deduce more. Write mD21m0, where m0is odd. We have already seen that
1k2K.n/ 2. We now show that 1> 1. Assume that this is not so.
Then 11, therefore 21jnm. Hence,
1log.n m/
log 2<log.2:075 Clog log log n= log ˛/
log 2;
where the last inequality follows from Lemma 2. We therefore get the inequality
K.n/ 2 < log.2:075 Clog log log n= log ˛/
log 2;
leading to n < 258, which is impossible. Thus, 1> 1. We next rework a bit the
relation .Fn/DFmto deduce a certain inequality relating `to the prime factors of
Fn. Write
Fn
FmDFn
.Fn/DY
pjFn1C1
p1:
Note that
Fn
FmD˛nˇn
˛mˇm>˛n1
˛mD˛`11
˛n:
Thus,
`log ˛Clog 11
˛n<log Fn
FmDX
pjFn
log 1C1
p1
<X
pjFn
1
p1;(14)
where in the last inequality above we used the fact that log.1Cx/ < x holds for x > 0.
Next, we note that since the inequality log.1 x/ > 2x holds for all x2.0; 1=2/,
we have that
log 11
˛n>2
˛100 >1010:
Thus,
`log ˛1010 <X
pjFn
1
pC1CS.n/;
Brought to you by | Technische Universität Berlin
Authenticated
Download Date | 10/1/18 10:34 AM
388 Florian Luca and Florin Nicolae
where we put
S.n/ WD X
pjFn1
p11
pC1:
We next bound S.n/. Clearly,
S.n/ < X
pjFn
p<100 1
p11
pC1C2X
p101
1
p.p 1/
<X
pjFn
p<100 1
p11
pC1C0:05:
We distinguish three cases.
Case 1. 2knand gcd.n; 3/ D1.
Here, the prime factors of Fnbelong to P2and the only such below 100 are
5; 11; 13; 29; 37; 59; 71; 73; 89; 97:
It now follows that
S.n/ < 0:168:
Hence,
`log ˛0:168 1010 <X
pjFn
1
pC1:
Since `2, and
`log ˛0:168 1010
`log ˛2log ˛0:168 1010
2log ˛> 0:82;
we get that
0:82` log ˛ < X
pjFn
1
pC1:(15)
Case 2. 4jnand gcd.n; 3/ D1.
In this case, if pjFn, then p2P4. There are 16 primes below 100 in P4, and
using them we get the upper bound
S.n/ < X
p2P4
p<100 1
p11
pC1C0:05 < 0:463:
Since also 4jm, we get that `4. Hence,
`log ˛0:463 1010 <X
pjFn
1
pC1;
Brought to you by | Technische Universität Berlin
Authenticated
Download Date | 10/1/18 10:34 AM
.Fn/DFm389
and since `4, and
`log ˛0:463 1010
`log ˛4log ˛0:463 1010
4log ˛> 0:75;
we get that
0:75` log ˛ < X
pjFn
1
pC1:(16)
Case 3. 6jn.
In this case,
S.n/ < X
p21
p11
pC1< 1:15;
and `6. Thus,
`log ˛1:15 1010 <X
pjFn
1
pC1;
and since
`log ˛1:15 1010
`log ˛6log ˛1:15 1010
6log ˛> 0:6;
we get that
0:6` log ˛ < X
pjFn
1
pC1:(17)
From (15), (16) and (17), we get that
0:6` log ˛ < X
pjFn
1
pC1:
We now write
nD
u
Y
iD1
ri
i;
where 2Dr1< < ruare prime numbers and 1; : : : ; uare positive integers. We
organize the prime factors of Fnaccording to their order of apparition in the Fibonacci
sequence. Clearly, for each pjFn, we have that z.p/ Ddfor some divisor dof
n. Furthermore, d > 2, since F1DF2D1. If pis a prime with z.p/ Dd, then
p ˙1 .mod d/, except when pDdD5. Let QdD ¹pWz.p/ Ddºand let
`dD#Qd. Then
.d 1/`dY
p2Qd
pFd< ˛d1;
Brought to you by | Technische Universität Berlin
Authenticated
Download Date | 10/1/18 10:34 AM
390 Florian Luca and Florin Nicolae
therefore
`d<.d 1/ log ˛
log.d 1/ <dlog ˛
log d(18)
for all d3. Indeed, the last inequality above follows for d4because the
function t= log tis increasing for t3, while for dD3it follows because `3D1 <
3.log ˛/= log 3. Now note that
X
pjFn
1
pC1DX
djn
d>2 X
p2Qd
1
pC1:
Since all primes p2Qdsatisfy p ˙1 .mod d/ for all d¤5, we get easily that
QdWD X
p2Qd
1
pC12X
`b`d=2cC1
1
d`
2
d 1CZdlog ˛=.2 log d/C1
1
d`
`!
2
dlog ed log ˛
2log dCe;
for d¤5. Since the inequality
ed log ˛
2log dCe < d
holds for all d5, we deduce that the inequality
Qd<2log d
d
holds for all d6. The same inequality also holds for d2 ¹3; 4; 5ºsince
Q3D1
3<2log 3
3; Q4D1
4<2log 4
4;and Q5D1
6<2log 5
5:
Hence,
X
pjFn
1
pC1DX
djn
d>2
Qd< 2 X
djn
log d
d:
Let us put logxDmax¹log x; 1º. We next show that the function defined on the
set of positive integers and given by f .a/ D2logafor a > 1 and f .1/ D1is
submultiplicative; i.e.,
f .ab/ f .a/f .b/ holds for all positive integers a; b:
Brought to you by | Technische Universität Berlin
Authenticated
Download Date | 10/1/18 10:34 AM
.Fn/DFm391
The above inequality is clear if one of aand bis 1. If both a,bare 3, then
f .ab/ D2log.ab/ D2log aC2log b < 4 log alog bDf .a/f .b/;
because both 2log aand 2log bexceed 2. Finally, assume that one of aand bis 2.
Say aD2and b2. Then the desired inequality is
f .ab/ D2log.2b/ D2log 2C2log b < 4 log b;
which is obviously true. Using the submultiplicativity of the function f, we have
0:6` log ˛ < X
djn
f .d/
dY
rjn1CX
ˇ1
f .rˇ/
rˇ:
The contribution of the prime rD2in the last product above is
1C2
2C2log 4
4C2log 8
8C D 2log 2C.log 2/ 1C2
2C3
4C
D2log 2C4log 2D2C3log 2 < 4:08:
The contribution of an odd prime number rin the above product is
1C2log r
r1C2
rC3
r2C< 1 C2r log r
.r 1/2:
Since 0:6=4:08 > 0:14, we get that
0:14` log ˛ < Y
rjn
r>2 1C2r log r
.r 1/2:(19)
Taking logarithms and using again the fact that log.1 Cx/ < x holds for all positive
real numbers x, we get
log `Clog.0:14 log ˛/ < X
rjn
r>2
log 1C2r log r
.r 1/2<X
rjn
r>2
2r log r
.r 1/2:
Separating the prime 3and using the fact that r=.r 1/2< 1:6=r for r5, we get
that
log `Clog.0:14 log ˛/ < 3log 3
2C3:2 X
rjn
r5
log r
r:(20)
We are now finally ready to bound `. Assume that ` > 108. Let !be the number
of prime factors of `and let q1< q2< be the increasing sequence of all prime
Brought to you by | Technische Universität Berlin
Authenticated
Download Date | 10/1/18 10:34 AM
392 Florian Luca and Florin Nicolae
numbers. All prime factors r5of neither divide gcd.n; m/, therefore `, or divide
nbut not m. Thus,
X
rjn
r5
log r
rX
5qq!C2
log q
qCX
rjn
r−m
log r
rWD S1CS2:(21)
In what follows, we bound S1and S2separately. To bound S1, note that in order to
maximize S1as a function of `, we may assume that `is not a multiple of 6. By the
Stirling formula, we then have
6` .! C2/Š > !C2
e!C2
;
leading to
.! C2/.log.! C2/ 1/ < log.6`/:
Hence, 2.! C2/.log.! C2/ 1/ < 2 log.6`/. Assume first that
2.! C2/.log.! C2/ 1/ < .! C2/.log.! C2/ Clog log.! C2//:
Then
log.! C2/ < 2 Clog log.! C2/;
leading to !21. In this case,
S1X
5q83
log q
q< 2:56:
Assume next that ! > 21. Then
2log.6`/ > 2.!C2/.log.!C2/1/ .!C2/.log.!C2/Clog log.!C2// > q!C2;
where the last inequality is inequality (3.13) on page 69 in [13] (valid for all !6,
which is our case). Since ` > 108, we have that 2log.6`/ > 40 > 32, so formula
(3.23) on page 70 in [13] shows that
S1<X
5qq!C2
log q
q<X
5q2log.6`/
log r
r
<log.2 log.6`// log 2
2log 3
31:33 C1
log.2 log.6`//
<log log.6`/ 1:07 < log log.6`/ 0:44;
where the last inequality is valid for ` > 108. Since log log.6`/ 0:44 > 2:56 holds
for ` > 108, it follows that in both cases we have
S1log log.6`/ 0:44: (22)
Brought to you by | Technische Universität Berlin
Authenticated
Download Date | 10/1/18 10:34 AM
.Fn/DFm393
We now bound S2. For this, observe that if 5jn, then 10 jn. Hence, 11 j55 D
F10 jFn. Thus, 10 j.Fn/DFm, leading to 5jFm, so 5jm. This shows that the
smallest prime that can participate in S2is 7(recall that 6jm). Let t3, and let
Itbe the set of primes in the interval Œ2t; 2tC1which divide nbut not m. Let ntbe
the number of elements in It. Assume that nt1for some t. Let pbe a prime in
It. Then nhas at least 2nt1squarefree divisors d, such that each one of them is a
multiple of p, and such that furthermore each one of them is divisible only by primes
q2It. For each one of these divisors d, since 2d jn, we have that LdjF2d jFn.
Since dis odd and d > 7, we get, by the Primitive Divisor Theorem (see [4]), that
Ldhas a primitive prime factor pd. Clearly, pd ˙1 .mod d/, so, in particular,
pdis odd. Reducing relation (1) modulo pd, we get that 5F 2
d 4 .mod pd/,
therefore .5=pd/D1. So, .pd=5/ D1by the Quadratic Reciprocity Law. It now
follows that z.pd/Ddjpd1, showing that pjdjpd1j.Fn/. Since the
primitive prime factors pdare distinct as druns over the divisors of ncomposed only
of primes q2It, it follows that the exponent of pin .Fn/is at least 2nt1. On the
other hand, since p−m, it follows that this exponent is at most the exponent of pin
Fz.p/. Now z.p/ jpC, where 2 ¹˙1º, because t3. Hence, writing apfor the
exponent of pin Fz.p/, we get that
papjFz.p/ jFpCDF.pC/=2L.pC/=2:
Relation (1) shows that gcd.F.pC/=2; L.pC/=2/j2. Since pis odd, we get that
papjF.pC/=2;or papjL.pC/=2:
In the first case, we have that
papF.pC1/=2 < ˛.p1/=2;
therefore
ap<.p 1/ log ˛
2log p<.p C1/ log ˛
2log p:(23)
In the second case, we arrive at the same conclusion in the following way. If D 1,
then since Ls< ˛sC1for all s1, we have
papL.p1/=2 < ˛.pC1/=2;
leading again to estimate (23). When D1and .p C1/=2 is odd, then
papL.pC1/=2 D˛.pC1/=2 Cˇ.pC1/=2 < ˛.pC1/=2;
leading again to estimate (23). Finally, assume that D1and .p C1/=2 is even. If
L.pC1/=2 ¤pap, then
papL.pC1/=2
2<˛.pC1/=2 C1
2< ˛.pC1/=2;
Brought to you by | Technische Universität Berlin
Authenticated
Download Date | 10/1/18 10:34 AM
394 Florian Luca and Florin Nicolae
leading again to (23). It remains to deal with the case L.pC1/=2 Dpap. Since p > 7,
it follows easily that L.pC1/=2 > p. Hence, ap> 1, and therefore L.pC1/=2 is a
perfect power of exponent > 1, and this is impossible by the main result from [3].
Thus, we have showed that estimate (23) holds for all p > 7. We thus get that
2nt1ap.p C1/ log ˛
2log p<2tC1log ˛
2log.2tC11/;(24)
where for the last inequality we used the fact that p2tC11together with the
fact that the function .s C1/=.2 log s/ is increasing for s7. We now show that
ntt2. Indeed, if not, then ntt1, which together with inequality (24) leads
to
2t2<2tC1log ˛
2log.2tC11/;
therefore
log.2tC11/ < 4 log ˛;
which is false for t3. Hence, ntt2holds for all t3. Since the function
log s=s is decreasing for s3, we get that
S2log 7
7CX
t3
.t 2/ log.2t/
2t<log 7
7C.log 2/ X
t3
t.t 2/
2t:
One computes easily that
X
t3
t.t 2/
2tD1;
therefore
S2<log 7
7Clog 2: (25)
Estimates (20), (21), (22) and (25) lead to
log ` < 3:2 log log.6`/
C3log 3
2log.0:14 log ˛/ C3:2 log 7
7Clog 20:44;
therefore
log ` < 3:2 log log.6`/ C6:05:
The above inequality leads to `<4106.
Brought to you by | Technische Universität Berlin
Authenticated
Download Date | 10/1/18 10:34 AM
.Fn/DFm395
3.6 Bounding `Even Better
Now let us write
nDUV; where UDY
1iu
rijm
ri
i;and VDY
1iu
ri−m
ri
i:
Let ibe such that rijU. Put rWD riand WD i. We have already seen that rj`
if iD1because r1D2. So, assume that ris odd. Suppose first that r5. Then
Lrıdivides Fnfor ıD1; 2; : : : ; . Each of Lrıhas a primitive prime factor which
is congruent to 1modulo rı. Thus .Fn/is divisible by r1C2CCDr.C1/=2.
Since r < 1014, a calculation of McIntosh and Roettger (see [1] and [10]) shows that
rkFz.r/ in this range confirming thus a conjecture of Wall [14]. Thus, r.C1/=21
divides m. If 2, then . C1/=2 1, showing that rjgcd.n; m/. This is
also obviously true if D1as well. Hence, if r > 3, then rjgcd.n; m/ j`. Assume
now that rD3. Then Lrıdivides Fnand has a primitive prime factor congruent to 1
modulo rıfor all ı2. It now follows that 3.C1/=21divides .Fn/, therefore if
2, then 3.C1/=22divides m. Now . C1/=2 2holds for all 3.
This shows that 3j`if 3. This is also true if D1. If D2and there exists
another odd prime q > 3 dividing n, then also L3q divides Fnand L3q has a primitive
prime divisor which is congruent to 1modulo 3. Since 19 jL9jFn, we get that 33
divides .Fn/DFm, therefore 9jm. Thus 3j`unless D2and n0D9. In this
last case we have nD219 < 3` < 12106, contradicting the fact that n>810371.
Thus, in all cases Uj`. Furthermore, since n>810371 and `<4106, we get that
V > 1. We now look at V. Assume that Vhas wprimes in it with w1. Let p17
be the smallest prime factor of V. Then Vhas 2w1odd divisors dall divisible by
p1. Since LdjFnfor all such divisors d, and since for each one of these divisors d
the number Ldhas a primitive divisor pd1 .mod d/, we get that the power of p1
in .Fn/is at least 2w1. Since p1−m, it follows that 2w1ap1, where ap1is the
exponent of p1in Fz.p1/. It was shown in the preceding section that the inequality
ap1.p1C1/.log ˛/=.2 log p1/ < .p1C1/=.4 log p1/holds for all p1> 7 because
log ˛ < 1=2. This is also true for p1D7because a7D1 < .7 C1/=.4 log 7/. We
thus get that 2w< .p1C1/=.2 log p1/, therefore
w < log.p1C1/ log.2 log p1/
log 2:
We now return to inequality (19) and use the observation that the function rlog r=.r
1/2is decreasing for r7, to get that
0:14` log ˛Y
rj`
r>21C2r log r
.r 1/21C2p1log p1
.p11/2.log.p1C1/log.2 log p1//= log 2
:
Brought to you by | Technische Universität Berlin
Authenticated
Download Date | 10/1/18 10:34 AM
396 Florian Luca and Florin Nicolae
We can now give a better bound on `. The product of the first 8primes is > 9106> `,
and the function .r log r/=.r1/2is decreasing for r3. Furthermore, the maximum
of the function
1C2p1log p1
.p11/2.log.p1C1/log.2 log p1//= log 2
as p17runs over primes is < 1:8. Thus,
0:14` log ˛Y
3q17 1C2r log r
.r 1/21:8 51:68;
leading to `766. The product of the first five primes exceeds 766, so that
0:14` log ˛Y
3q71C2r log r
.r 1/21:8 < 16:82;
yielding `248. Thus, U`248.
We can now see the light at the end of the tunnel. Namely, we shall show that
p1< 1014. Assume that we have proved that. Suppose that nis divisible by p1q,
where qis some other prime factor (which might be p1itself). Since p17, it
follows that both Lp1and Lp1qhave primitive prime factors which are both congruent
to 1modulo p1. This shows that p2
1j.Fn/, so p2
1jFm. By McIntosh’s calculation,
we get that p1jm, which is impossible. Thus, n0Dp1, therefore nD21p1
`p1< 248 1014, contradicting the fact that n>810371. Thus, it remains to bound
p1.
3.7 Bounding p1
Returning to inequality (14), we have
`log ˛1010 < ` log ˛Clog 11
˛n<X
pjFn
1
p1
X
pjFU
1
p1CX
pjFn
p−FU
1
p1:
Since Uj`, a calculation with MATHEMATICA shows that the inequality
`log ˛1010 X
pjFU
1
p10:3145`
Brought to you by | Technische Universität Berlin
Authenticated
Download Date | 10/1/18 10:34 AM
.Fn/DFm397
holds for all even `248. Thus,
0:3145` X
pjFn
p−FU
1
p1:
We now assume that p1> 1014 and we shall get a contradiction. Note that the above
sum is
X
pjFn
p−FU
1
p1DX
d1jUX
d2jV
d2>1
Qd1d2;
where, as in Section 3.5, we have
QdDX
p2Qd
1
p1:
Since p ˙1 .mod d/, and dp1> 1014, it follows p=.p 1/ < 0:3145=0:3144
for all pjFnbut p−FU. Thus we get that
0:3144` X
d1jUX
d2jV
d2>1
1
p:(26)
Let dDd1d2. We saw that the inequality `dD#Qd< d log ˛= log dholds for
all our d(see inequality (18)). Our primes p2Qdhave the property that p ˙1
.mod d/. By the large sieve inequality of Montgomery and Vaughan [11], we have
that if we write .tIa; b/ for the number of primes pa .mod b/ which do not
exceed t, then the inequality
.tIa; b/ 2t
.b/ log.t=b/
holds uniformly for ab < t, with coprime aand b. The calculation from page 12
in [8], shows that
X
p2Qd
3d<p<d2
1
p<4
.d/ log dC4log log d
.d/ :
For the remaining primes in Qdbut not in .3d; d2/we have that
X
p2Qd
p62.3d;d2/
1
p<1
d1C1
dC1C1
2d 1C1
2d C1C1
3d 1C`d
d2
<10
3.d/ Clog ˛
dlog d:
Brought to you by | Technische Universität Berlin
Authenticated
Download Date | 10/1/18 10:34 AM
398 Florian Luca and Florin Nicolae
We thus get that
Qd<4log log d
.d/ 1C1
.log d/ log log dC10
12 log log dClog ˛
.log d/ log log d
<5:02 log log d
.d/ :
Since d1jU, we get that d1248. Since d2> 1, we get that d2p1> 1014.
Hence, d1d2< d1:2
2holds uniformly in d1and d2, therefore
Qd<5:02 log.1:2 log d2/
.d1/.d2/:
Let .V / be the number of divisors d2of V. Of them, .V=p1/are multiples of p1,
and for each one of these, Ld2has a primitive prime factor pd2which in particular is
congruent to 1modulo p1. Hence, the exponent of p1in .Fn/is at least .V=p1/.
Since p1−m, we get that
.V=p1/ap1.p1C1/ log ˛
2log p1
;
leading to
.V / 2.V=p1/.p1C1/ log ˛
log p1
:
Now
V
.V / Y
pjV1C1
p11C1
p11.V /
1C1
p11.p1C1/ log ˛= log p1
< 1:02;
where the last inequality holds because p1> 1014. Thus, the inequality
1
.d2/V
.V /1
d21:02
d2
holds for all divisors d2of V. We therefore get that
Qd.5:02 1:02/ log.1:2 log d2/
d2.d1/<5:13 log.1:2 log d2/
d2.d1/:
The function log.1:2 log s/=s is decreasing for s > 1014, showing that the inequality
Qd5:13 log.1:2 log p1/
p11
.d1/
Brought to you by | Technische Universität Berlin
Authenticated
Download Date | 10/1/18 10:34 AM
.Fn/DFm399
holds for all divisors dof nwhich do not divide U. Thus,
X
pjFn
p−FU
1
p5:13.V / log.1:2 log p1/
p1X
d1j`
1
.d1/
<5:13.p1C1/.log ˛/ log.1:2 log p1/
p1log p1
h.`/;
where
h.`/ DX
d1j`
1
.d1/X
d1j`
.d1/D`:
Thus, comparing the last bound above with inequality (26), we get
p1log p1
.p1C1/ log.1:2 log p1/<5:13 log ˛
0:3144 :
The above inequality implies that p1< 9 1011 < 1014, which is the desired contra-
diction. Theorem 1 is therefore proved.
References
[1] V. Andreji´
c, On Fibonacci powers, Univ. Beograd Publ. Elektrotehn. Fak. Sec. Mat. 17
(2006), 38–44.
[2] Y. Bugeaud, M. Mignotte and S. Siksek, Sur les nombres de Fibonacci de la forme qkyp,
C. R. Acad. Sci. Paris 339 (2004), 327–330.
[3] Y. Bugeaud, M. Mignotte and S. Siksek, Classical and modular approaches to exponen-
tial Diophantine equations I. Fibonacci and Lucas perfect powers, Annals of Mathemat-
ics 163 (2006), 969–1018.
[4] R. D. Carmichael, On the numerical factors of the arithmetic forms ˛n˙ˇn,Ann.
Math. (2) 15 (1913), 30–70.
[5] R. Knott, Fibonacci Numbers and the Golden Section,http://www.mcs.surrey.ac.
uk/Personal/R.Knott/Fibonacci/.
[6] T. Koshy, Fibonacci and Lucas Numbers with Applications, Wiley-Interscience, New
York, 2001.
[7] F. Luca, Euler indicators of Lucas sequences, Bull. Mat. Soc. Mat. Roumaine 40 (1997),
no. 88, 151–163.
[8] F. Luca, Fibonacci numbers with the Lehmer property, Bull. Polish Acad. Sci. Math. 55
(2007), 7–15.
[9] W. McDaniel, On Fibonacci and Pell Numbers of the Form kx2,The Fibonacci Quart.
40 (2002), 41–42.
Brought to you by | Technische Universität Berlin
Authenticated
Download Date | 10/1/18 10:34 AM
400 Florian Luca and Florin Nicolae
[10] R. J. McIntosh and E. L. Roettger, A search for Fibonacci–Wiefrich and Wolsenholme
primes, Math. Comp. 76 (2007), no. 260, 2087–2094.
[11] H. L. Montgomery and R. C. Vaughan, The large sieve, Mathematika 20 (1973), 119–
134.
[12] C. Pomerance, On composite nfor which .n/ jn1, II, Pacific J. Math. 69 (1977),
177–186.
[13] J. B. Rosser and L. Schoenfeld, Approximate formulas for some functions of prime num-
bers, Illinois J. of Math. 6(1962), 64- ˝
U94.
[14] D. D. Wall, Fibonacci series modulo m,Amer. Math. Monthly 67 (1960), 525–532.
Received September 19, 2008; accepted April 6, 2009.
Author information
Florian Luca, Instituto de Matemáticas UNAM, Ap. Postal 61-3 (Xangari) C.P. 58089,
Morelia, Michoacán, Mexico.
E-mail: [email protected]
Florin Nicolae, Institut für Mathematik, Technische Universität Berlin, MA 8-1, Straße des
17. Juni 136, 10623 Berlin, Germany and Institute of Mathematics of the Romanian
Academy, P. O. BOX 1-764, RO-014700 Bucharest, Romania.
E-mail: [email protected]
Brought to you by | Technische Universität Berlin
Authenticated
Download Date | 10/1/18 10:34 AM
