On the Euler Function of Fibonacci Numbers

Florian Luca Instituto de Matemáticas

Universidad Nacional Autonoma de México

C.P. 58089, Morelia, Michoacán

México

fluca@matmor.unam.mx

V. Janitzio Mejía Huguet Departamento de Ciencias Básicas

Universidad Autónoma Metropolitana-Azcapotzalco

Av. San Pablo #180 Col. Reynosa Tamaulipas

C. P. 02200, Azcapotzalco DF

México

vjanitzio@gmail.com

Florin Nicolae Institut für Mathematik

Technische Universität Berlin MA 8-1, Strasse des 17 Juni 136

D-10623 Berlin

Germany

nicolae@math.tu-berlin.de

and

Institute of Mathematics

Romanian Academy

P.O. Box 1-764, RO-014700, Bucharest Romania

Abstract

In this paper, we show that for any positive integer k, the set

\{(\frac{ϕ(F_{n+1})}{ϕ(F_{n})}, \frac{ϕ(F_{n+2})}{ϕ(F_{n})}, …, \frac{ϕ(F_{n+k})}{ϕ(F_{n})}) : n ≥ 1\}

is dense in ℝ_{≥0}^{k}, where ϕ(m) is the Euler function of the positive integer m and F_{n} is the nth Fibonacci number.

1 Introduction

Let (F_{n})_{n≥1} be the Fibonacci sequence given by F_{1} = F_{2} = 1 and F_{n+2} = F_{n+1} + F_{n} for all n ≥ 1. Recently, there has been some interest in investigating values of classical arithmetic functions with Fibonacci numbers. For a positive integer m, we put ϕ(m) for the Euler function of m which counts the number of positive integers less than or equal to m and coprime to m, and σ(m) for the sum of divisors of m.

Luca [6] proved that there is no perfect Fibonacci number; that is, there is no positive integer n such that σ(F_{n}) = 2F_{n}. Luca and Nicolae [10] proved that if ϕ(F_{n}) = F_{m}, then n ∈ {1, 2, 3, 4}. Luca [9] proved that if ϕ(F_{n}) | F_{n} − 1, then F_{n} is prime, confirming in this way that a well-known conjecture of Lehmer holds for the Fibonacci numbers.

It follows from the results from Luca and Shparlinski [12] that the asymptotic

\frac{1}{x} ∑_{n≤x} (\frac{ϕ(F_{n})}{F_{n}})^{k} = Γ_{k} + O_{k} (\frac{(log x)^{k}}{x} )

holds for all positive integers k as x → ∞ with some positive constant Γ_{k}. In particular, the function ϕ(F_{n})/F_{n} has a distribution function. That is, for every real number z, the asymptotic density of the set of positive integers n such that ϕ(F_{n})/F_{n} < z exists. Luca [7] proved that if we put M_{n} = 2^{n} − 1, then the set {ϕ(M_{n})/M_{n} : n ≥ 1} is dense in [0, 1]. In the same paper, it is said that the same property holds true if one replaces the sequence of Mersenne numbers (M_{n})_{n≥0} by the sequence of Fibonacci numbers (F_{n})_{n≥0}.

In this paper, we revisit values of the Euler function with Fibonacci numbers and prove the following result.

Theorem 1. For every positive integer k, the set

\{(\frac{ϕ(F_{n+1})}{ϕ(F_{n})}, \frac{ϕ(F_{n+2})}{ϕ(F_{n})}, …, \frac{ϕ(F_{n+k})}{ϕ(F_{n})}) : n ≥ 1\}  (1)

is dense in ℝ_{≥0}^{k}.

Theorem 1 remains true when the Euler function ϕ is replaced by the sum of divisors function σ. It also remains true if the sequence of Fibonacci numbers (F_{n})_{n≥0} is replaced by other Lucas sequences such as the sequence of Mersenne numbers (M_{n})_{n≥0}. If the sequence of Fibonacci numbers (F_{n})_{n≥0} is replaced by the sequence of all natural numbers, then the statement that for every positive integer k, the set

\{(\frac{ϕ(n + 1)}{ϕ(n)}, \frac{ϕ(n + 2)}{ϕ(n)}, …, \frac{ϕ(n + k)}{ϕ(n)}) : n ≥ 1\}

is dense in ℝ_{≥0}^{k} is a result of Schinzel of 1955 [13]. More general forms of this result appear in a paper by Erdős and Schinzel of 1960 [3], and in the recent work of Wong [14].

We point out that the similar looking statement that the set

\{(\frac{γ(n + 1)}{γ(n)}, …, \frac{γ(n + k)}{γ(n)}) : n ≥ 1\}

is dense in ℝ_{≥0}^{k}, where γ(m) = ∏_{p|m} p is the square-free kernel of m, or the product of all the distinct primes dividing m, was proved by Luca and Shparlinski [11].

We have the following immediate corollary of Theorem 1.

Corollary 1. For any positive integer k and every permutation (i_{1}, …, i_{k}) of (1, …, k) there exist infinitely many positive integers n such that

ϕ(F_{n+i_{1}}) < ϕ(F_{n+i_{2}}) < ⋯ < ϕ(F_{n+i_{k}}).  (2)

P. Erdős, K. Győry and Z. Papp [2] call two functions f(n) and g(n) defined on the set of positive integers to be independent if for every k ≥ 1 and permutations (i_{1}, …, i_{k}) and (j_{1}, …, j_{k}) of (1, …, k), there exist infinitely many n such that

f(n + i_{1}) < f(n + i_{2}) < ⋯ < f(n + i_{k}),

while

g(n + j_{1}) < g(n + j_{2}) < ⋯ < g(n + j_{k}).

N. Doyon and F. Luca [1] proved that the Euler function ϕ(n) and the Carmichael function λ(n) (also known as the universal exponent modulo n) are independent, while Hernane and Luca [5] proved that the two functions σ(ϕ(n)) and ϕ(σ(n)) are independent. In light of (2), it makes sense to ask if we can pair the function ϕ(F_{n}) independently with some other interesting multiplicative functions. Here are some questions which are left for the reader.

Problem 1.

(i) Are the functions ϕ(F_{n}) and F_{ϕ(n)} independent?

(ii) Are the functions ϕ(F_{n}) and ϕ(M_{n}) independent?

2 Notation

We put α = (1 + \sqrt{5})/2 and β = (1 − \sqrt{5})/2. We let (L_{n})_{n≥1} be the Lucas companion of the Fibonacci sequence given by L_{1} = 1, L_{2} = 3 and L_{n+2} = L_{n+1} + L_{n} for all n ≥ 1. It is well-known that F_{n} and L_{n} can be expressed in terms of α and β as

F_{n} = \frac{α^{n} − β^{n}}{α − β}  and L_{n} = α^{n} + β^{n} for n = 1, 2, ….  (3)

It is also well-known that F_{n} and L_{n} satisfy various relations such as

F_{2n} = F_{n}L_{n} and  L_{n}^{2} − 5F_{n}^{2} = 4(−1)^{n},  (4)

which will be used in the sequel.

Throughout this paper, we use the letters p and q with or without subscripts for prime numbers and ℓ, m and n for positive integers. We write ω(n) for the number of distinct prime factors of the positive integer n and p(n) for the smallest prime factor of n. We write z(n) for the order of apparition of n in the Fibonacci sequence, which is the smallest positive integer k such that n | F_{k}. It is well-known that z(n) exists and that n | F_{m} if and only if z(n) | m. Furthermore, if p is an odd prime, then p | F_{p−(5|p)}, where we write (a|p) for the Legendre symbol of a with respect to p.

We write log x for the natural logarithm, and for an integer k ≥ 1 we write log_{k} x for the recursively defined function given by log_{1} x = max{1, log x} and log_{k} x = max{1, log(log_{k−1} x)} for k ≥ 2. When k = 1 we omit the index of the logarithm. Hence, all logarithms which will appear are ≥ 1. We use the Vinogradov symbols ≪, ≫ and the Landau symbols O and o with their usual meanings. Recall that the statements A ≪ B, B ≫ A and A = O(B) are all equivalent to the fact that the inequality |A| < cB holds with some positive constant c, while A = o(B) means that A/B → 0. The constants implied by these symbols may be absolute or may depend on some other parameters such as k, or a fixed point γ = (γ_{1}, …, γ_{k}) ∈ ℝ_{>0}^{k}, etc. We use x_{0} for a large positive real number. The meaning of “large” might change from a line to the next.

3 Preliminary Results

Lemma 2. Let p ≡ 13 (mod 20) be a prime. Then p | F_{(p+1)/2}.

Proof. This should be well-known but we supply a quick proof of it for completeness. Since p ≡ 3 (mod 5), it follows that (5|p) = −1, therefore p | F_{p+1} = F_{(p+1)/2}L_{(p+1)/2}. Suppose for a contradiction that p ∤ F_{(p+1)/2}. Then p | L_{(p+1)/2}. Reducing the relation

L_{(p+1)/2}^{2} − 5F_{(p+1)/2}^{2} = 4(−1)^{(p+1)/2} = −4

(see (4)) modulo p, we get 5F_{(p+1)/2}^{2} ≡ 4 (mod p), leading to the conclusion that (5|p) = 1, which is a contradiction.

For every positive integer m let P_{m} = {p : z(p) = m}. The following lemma turns out to be useful.

Lemma 3. We have the estimate

∑_{p∈P_{m}} \frac{1}{p} ≪ \frac{log m}{m}.  (5)

Proof. We may assume that m > 5. Since p | F_{p±1}, we get that p ≡ ±1 (mod m) for all p ∈ P_{m}. Thus,

α^{m} > F_{m} ≥ ∏_{p∈P_{m}} p ≥ (m − 1)^{#P_{m}},

leading to #P_{m} ≪ m/ log m.

We split the desired sum at m^{2}. We have

∑_{p∈P_{m}} \frac{1}{p} ≤ ∑_{\begin{matrix}p∈P_{m} \\ p<m^{2} \end{matrix}} \frac{1}{p} + ∑_{\begin{matrix}p∈P_{m} \\ p>m^{2} \end{matrix}} \frac{1}{p} := S_{1} + S_{2}.  (6)

Observe that if p ∈ P_{m} ∩ (1, m^{2}), then p = ±1 + mℓ for some integer ℓ ∈ [1, m]. Thus

S_{1} ≤ ∑_{1≤ℓ≤m} (\frac{1}{−1 + mℓ} + \frac{1}{1 + mℓ}) ≪ \frac{1}{m} ∑_{1≤ℓ≤m} \frac{1}{ℓ} ≪ \frac{log m}{m},  (7)

As for S_{2}, we have that

S_{2} ≤ \frac{#P_{m}}{m^{2}} ≪ \frac{1}{m log m}.  (8)

The desired conclusion now follows at once from estimates (6), (7) and (8). Lemma 4. We have the estimate

∑_{d|m} \frac{log d}{d} ≪ (log_{2} m)^{2}.  (9)

Proof. This is Lemma 2 in Luca [7]. Lemma 5. Let P be the set of all primes p which fulfill the following conditions:

(i) p ≡ 13 (mod 20); (ii) p((p + 1)/2) > log_{2} p; (Here, we recall that p(m) stands for the smallest prime factor

of m.) (iii) p + 1 is square-free. Let P(t) = P ∩ (1, t). Then the estimate

#P(t) ≫ \frac{t}{log t log_{3} t}

holds. Proof. This follows by typographic changes from the proof of Lemma 1 in Luca [7].

4 ϕ(F_{n})/F_{n} is dense in [0, 1] revisited

As we have mentioned in the Introduction, the fact that {ϕ(F_{n})/F_{n} : n ≥ 1} is dense in [0, 1] alluded to in the title of this section was already proved in Luca [7]. Here, we revisit that proof especially since that proof yields a bit more. We follow the arguments from Luca [7] although we slightly change some of the parameters.

We let x be a large positive real number, put y = log_{2} x, z = log x, and P(y, z) = P ∩ (y, z). We let

S = ∑_{p∈P(y,z)} \frac{1}{p}.

We first show that

S > 2 log_{4} x  (10)

holds for x > x_{0}. Indeed, observe that, by Abel’s summation formula, we have

S = ∑_{\begin{matrix}p∈P \\ y<p<z \end{matrix}} \frac{1}{p} = ∫_{y}^{z} \frac{d(#P(t))}{t} = \frac{#P(t)}{t}|_{t=y}^{t=z} + ∫_{y}^{z} \frac{#P(t)}{t^{2}}.

Clearly,

|\frac{#P(t)}{t}|_{t=y}^{t=z}| ≤ \frac{π(y)}{y} = O (\frac{1}{log_{3} x}) .

For large x, by Lemma 5, we have that

#P(t) ≥ \frac{3t}{log t log_{2} t}.

Thus, we get that

S ≥ 3 ∫_{y}^{z} \frac{dt}{t log t log_{2} t} + O (\frac{1}{log_{3} x}) = 3(log_{3} t)|_{t=y}^{t=z} + o(1)
= 3 log_{4} x − 3 log_{5} x + o(1) > 2 log_{4} x

for x > x_{0}.

Next let

N = lcm[(p + 1)/2 : p ∈ P(y, z)].

Observe that N is square-free, so we can write it as N = q_{1}q_{2} ⋯ q_{T}, where q_{1} < q_{2} < ⋯ < q_{T}. Since q_{T} < (z + 1)/2, we have, by the Prime Number Theorem, that N ≤ ∏_{q<(z+1)/2} q < exp((0.5 + o(1))z) as x → ∞. In particular, N < x for x > x_{0}.

We next put n_{0} = 1 and n_{j} = ∏_{i≤j} q_{i} for j = 1, …, T. Let

s_{j} = \frac{ϕ(F_{n_{j}})}{F_{n_{j}}}.

Since n_{0} | n_{1} | n_{2} | ⋯ | n_{T}, we have that

s_{0} ≥ s_{1} ≥ ⋯ ≥ s_{T} .

Obviously, s_{0} = 1. We now look at s_{T}. Observe that, by Lemma 2 and the fact that F_{a} | F_{b} whenever a | b, we get that

p | F_{(p+1)/2} | F_{N} = F_{n_{T}} for all p ∈ P(y, z).

Thus,

s_{T} = \frac{ϕ(F_{n_{T}})}{F_{n_{T}}} = ∏_{p|F_{n_{T}}} (1 − \frac{1}{p}) ≤ ∏_{p∈P(y,z)} (1 − \frac{1}{p})

= exp (− ∑_{p∈P(y,z)} \frac{1}{p} + O (∑_{p} \frac{1}{p^{2}} ))

= exp(−S + O(1)) < exp(−2 log_{4} x + O(1)) < \frac{1}{log_{3} x}

for x > x_{0}, where the last inequality follows from (10).

Next we show that

\frac{s_{j+1}}{s_{j}} = 1 + O (\frac{(log_{5} x)^{2}}{log_{4} x} )  holds for all j = 0, 1, …, T − 1.  (11)

First of all notice that every prime factor p of F_{n_{j}} for some j ≥ 1 has the property that z(p) | n_{j}. In particular, z(p) > log_{2} y = log_{3} z. Since also p ≡ ±1 (mod z(p)), we get that p ≥ (log_{3} z) − 1.

Thus,

\frac{s_{j+1}}{s_{j}} = ∏_{\begin{matrix}p|F_{n_{j+1}} \\ p∤F_{n_{j}} \end{matrix}} (1 − \frac{1}{p}) = ∏_{\begin{matrix}z(p)|n_{j+1} \\ z(p)∤n_{j} \end{matrix}} (1 − \frac{1}{p}) = ∏_{d|n_{j}} ∏_{p∈P_{dq_{j+1}}} (1 − \frac{1}{p})

= exp (− ∑_{d|n_{j}} ∑_{p∈P_{dq_{j+1}}} \frac{1}{p} + O ( ∑_{p≥(log_{3} z)−1} \frac{1}{p^{2}} ))

= exp (O (∑_{d|n_{j}} \frac{log(dq_{j+1})}{dq_{j+1}} + \frac{1}{log_{3} z} )) ,  (12)

where in the last estimate above we used Lemma 3. Now note that

∑_{d|n_{j}} \frac{log(dq_{j+1})}{dq_{j+1}} = \frac{log q_{j+1}}{q_{j+1}} ∑_{d|n_{j}} \frac{1}{d} + \frac{1}{q_{j+1}} ∑_{d|n_{j}} \frac{log d}{d}

≪ \frac{1}{q_{j+1}} (log q_{j+1} log_{2} n_{j} + (log_{2} n_{j})^{2}) ,  (13)

where here we used Lemma 4 together with the well-known estimate

∑_{d|m} \frac{1}{d} = \frac{σ(m)}{m} ≪ log_{2} m

with m = n_{j}. Since the primes q_{1}, …, q_{j+1} are arranged increasingly, we have that

n_{j} ≤ ∏_{q<q_{j+1}} q < exp(2q_{j+1})

for x > x_{0}, therefore log_{2} n_{j} ≪ log q_{j+1}. This last inequality together with inequality (13) yields

∑_{d|n_{j}} \frac{log(dq_{j+1})}{dq_{j+1}} ≪ \frac{(log q_{j+1})^{2}}{q_{j+1}} ≪ \frac{(log_{3} y)^{2}}{log_{2} y} = \frac{(log_{4} z)^{2}}{log_{3} z} .

Inserting the above inequality into inequality (12), we get that

\frac{s_{j+1}}{s_{j}} = exp (O (\frac{(log_{4} z)^{2}}{log_{3} z} )) = 1 + O (\frac{(log_{4} z)^{2}}{log_{3} z} ) = 1 + O (\frac{(log_{5} x)^{2}}{log_{4} x} ) ,

which is precisely inequality (11).

Now it is easy to see that {ϕ(F_{n})/F_{n} : n ≥ 1} is dense in [0, 1] in the following way. Let γ ∈ (0, 1) and ε > 0 arbitrary. Let j ∈ {0, …, T } be maximal such that s_{j} > γ. Since s_{T} = o(1) for large x, it follows that j ≠ T. Let j be maximal with this property. Then s_{j+1} ≤ γ. However,

γ ≥ s_{j+1} = s_{j} (1 + O (\frac{(log_{5} x)^{2}}{log_{4} x} )) > s_{j} − \frac{c(log_{5} x)^{2}}{log_{4} x} ,

where c > 0 is some absolute constant. This shows that

\frac{ϕ(F_{n_{j}})}{F_{n_{j}}} = s_{j} ∈ (γ, γ + c\frac{(log_{5} x)^{2}}{log_{4} x} ) .

Choosing x large enough such that

\frac{c(log_{5} x)^{2}}{log_{4} x} < ε,

we get that ϕ(F_{n_{j}})/F_{n_{j}} ∈ (γ, γ + ε).

This certainly implies that the sequence (ϕ(F_{n})/F_{n})_{n≥1} is dense in (0, 1).

However, notice that we have proved the following stronger statement.

Lemma 6. Let γ ∈ (0, 1). Then for x > x_{0}, there exists a square-free n < x such that p(n) > log_{2} x and such that furthermore

\frac{ϕ(F_{n})}{F_{n}} ∈ (γ, γ + \frac{(log_{5} x)^{3}}{log_{4} x} ) .

Now let i ≥ 1 be fixed and write α_{i} = α^{i} and β_{i} = β^{i}. Look at the sequence

F_{n}^{(i)} = \frac{α_{i}^{n} − β_{i}^{n}}{α_{i} − β_{i}} for all n = 1, 2, ….

Observe that

F_{n}^{(i)} = \frac{α^{in} − β^{in}}{α^{i} − β^{i}} = \frac{F_{ni}}{F_{i}} .

The sequence (F_{n}^{(i)})_{n≥1} shares the same divisibility properties of the sequence of Fibonacci numbers. We record two of them.

Lemma 7. Let i ≥ 1 be fixed.

(i) If a | b, then F_{a}^{(i)} | F_{b}^{(i)}.

(ii) If p is a prime dividing both F_{i} and F_{a}^{(i)}, then p divides a.

(ii) If p ≡ 13 (mod 20) and i and (p + 1)/2 are coprime, then p | F_{(p+1)/2}^{(i)}.

Proof. The first one is obvious and the second one is well-known and easy to prove. To see the third one, note that since p ≡ 13 (mod 20), it follows, by Lemma 2, that p | F_{(p+1)/2} | F_{i(p+1)/2}. Since i and (p + 1)/2 are coprime and z(p) | (p + 1)/2, it follows, in particular, that z(p) does not divide i. Thus, F_{i} is not a multiple of p, so

p | \frac{F_{i(p+1)/2}}{F_{i}} = F_{(p+1)/2}^{(i)}.

Now the arguments that proved Lemma 6 also prove the following result.

Lemma 8. Let i ≥ 1 be fixed and γ ∈ (0, 1). There exists x_{0}(i) depending on i such that for x > x_{0}(i) there exists a square-free n < x with p(n) > log_{2} x and

\frac{ϕ(F_{n}^{(i)})}{F_{n}^{(i)}} ∈ (γ, γ + \frac{(log_{5} x)^{3}}{log_{4} x} ) .

5 The Proof of Theorem 1

We may assume that k ≥ 5. In particular, F_{K} ≥ K for all K ≥ k.

We write f(n) = ϕ(n)/n. First we make some reductions. Observe that

\frac{ϕ(F_{n+i})}{ϕ(F_{n})} = \frac{f(F_{n+i})}{f(F_{n})} · \frac{F_{n+i}}{F_{n}} ,

and

\frac{F_{n+i}}{F_{n}} = α^{i}(1 + o(1)) as n → ∞.

Thus, in order to prove that the set of vectors shown in the statement of Theorem 1 is dense in ℝ_{≥0}^{k}, it suffices to show that the set of vectors

\{(\frac{f(F_{n+1})}{f(F_{n})}, \frac{f(F_{n+2})}{f(F_{n})}, ⋯, \frac{f(F_{n+k})}{f(F_{n})}) : n ≥ 1\}  (14)

is dense in ℝ_{≥0}^{k}.

Next let K = ((k + 1)!)^{2} and choose n = Kn_{0} with some positive integer n_{0}. Then

n + i = Kn_{0} + i = i (\frac{K}{i} n_{0} + 1) := in_{i} for all i = 1, …, k.

Furthermore, note that the numbers n_{i} are coprime with all primes p ≤ k +1 for i = 1, …, k. That is, p(n_{i}) > k + 1 for i = 1, …, k. Assume in fact more, namely that p(n_{i}) > F_{k} for all i = 1, …, k. Then

F_{n+i} = F_{in_{i}} = F_{i} (\frac{F_{in_{i}}}{F_{i}} ) = F_{i}F_{n_{i}}^{(i)}

for all i = 1, …, k. By (ii) of Lemma 7, the prime factors of gcd(F_{i}, F_{n_{i}}^{(i)}) divide n_{i}. Since p(n_{i}) > F_{k} for all i = 1, …, k, it follows that F_{i} and F_{n_{i}}^{(i)} are coprime. Thus, by the multiplicativity of f(n), we get that

f(F_{n+i}) = f(F_{i})f(F_{n_{i}}^{(i)}) for all i = 1, …, k.

Similarly, assuming that p(n_{0}) > F_{K}, we get that F_{n} = F_{K}F_{n_{0}}^{(K)} and

f(F_{n}) = f(F_{K})f(F_{n_{0}}^{(K)}).

With these conventions, the set shown at (14) will be dense in ℝ_{≥0}^{k} provided that the set of vectors

\{(\frac{f(F_{n_{1}})}{f(F_{n_{0}}^{(K)})}, \frac{f(F_{n_{2}}^{(2)})}{f(F_{n_{0}}^{(K)})}, …, \frac{f(F_{n_{k}}^{(k)})}{f(F_{n_{0}}^{(K)})}) : p(n_{0} ⋯ n_{k}) > F_{K}\}  (15)

is dense in ℝ_{≥0}^{k}.

Now let γ = (γ_{1}, …, γ_{k}) ∈ R_{>0}^{k}. Write γ = (δ_{1}/δ_{0}, …, δ_{k}/δ_{0}), where δ_{i} ∈ (0, 1) for i = 1, …, k. It suffices to take δ_{0} = 1/(2Γ), where Γ = max{1, γ_{1}, …, γ_{k}} and δ_{i} = γ_{i}δ_{0} for i = 1, …, k. In order to prove that the set shown at (15) is dense in ℝ_{>0}^{k}, it suffices to exhibit an infinite sequence N of n’s such that

(f(F_{n_{0}}^{(K)}), f(F_{n_{1}}), f(F_{n_{2}}^{(2)}), …, f(F_{n_{k}}^{(k)})) → (δ_{0}, δ_{1}, …, δ_{k})

as n → ∞ in the sequence N.

We shall now explain how to do this. We next fix some arbitrary ε > 0, and recursively choose positive square-free integers m_{0}, m_{1} …, m_{k} satisfying the following properties:

(i) p(m_{0} ⋯ m_{k}) > F_{K};

(ii)

f(F_{m_{0}}^{(K)}) ∈ (δ_{0}, δ_{0} + ε), f(F_{m_{1}}) ∈ (δ_{1}, δ_{1} + ε), … f(F_{m_{k}}^{(k)}) ∈ (δ_{k}, δ_{k} + ε);

(iii) gcd(m_{i}, m_{j}) = 1 for all 0 ≤ i < j ≤ k.

To do this, we proceed as follows. We take a large x > x_{0}(K), such that both inequalities log_{2} x > F_{K} and (log_{5} x)^{3}/(log_{4} x) < ε hold, and choose a square-free positive integer m_{0} < x as in Lemma 8 with i = K and γ = δ_{0}. Such m_{0} will satisfy p(m_{0}) > log_{2} x and

f(F_{m_{0}}^{(K)}) ∈ (δ_{0}, δ_{0} + \frac{(log_{5} x)^{3}}{log_{4} x} ) ⊂ (δ_{0}, δ_{0} + ε).

After having chosen m_{0}, we fix it and take a new x which is larger and such that x > x_{0}(1) and log_{2} x > max{F_{K}, m_{0}}. Applying now Lemma 8 with i = 1 and γ = δ_{1}, we get some square-free positive integer m_{1} < x with p(m_{1}) > log_{2} x > max{F_{K}, m_{0}} such that

f(F_{m_{1}}^{(1)}) ∈ (δ_{1}, δ_{1} + ε).

Note that m_{1} is coprime to m_{0} because p(m_{1}) > m_{0}. Now we take a new x, perhaps larger, such that x > x_{0}(2) and log_{2} x > max{F_{K}, m_{0}, m_{1}}, and apply Lemma 8 with i = 2 and δ = δ_{2} to get some square-free positive integer m_{2} < x such that p(m_{2}) > log_{2} x > max{F_{K}, m_{0}, m_{1}} and

f(F_{m_{2}}^{(2)}) ∈ (δ_{2}, δ_{2} + ε).

Observe that m_{2} is coprime to both m_{0} and m_{1} since p(m_{2}) > max{m_{0}, m_{1}}. Proceeding in this way k times, we end up with some square-free positive integers m_{0}, …, m_{k} satisfying the above three properties.

We now fix these numbers m_{0}, …, m_{k}. Throughout the remaining of this section, the constants implied by the symbols ≫, ≪ and O will depend on k, γ and m_{0}, …, m_{k} (but not on ε).

We start by searching for n_{0} satisfying the following congruences

n_{0} ≡ 0 (mod m_{0}) and (K/i)n_{0} + 1 ≡ 0 (mod m_{i}) for i = 1, …, k.

Since the largest prime factor of K is ≤ k + 1 ≤ K ≤ F_{K} < p(m_{i}) for all i = 1, …, k, it follows that K/i is invertible modulo m_{i}. In particular, the congruence (K/i)n_{0} + 1 ≡ 0 (mod m_{i}) is solvable for n_{0} and puts n_{0} into a certain congruence class N_{0,i} (mod m_{i}). Since m_{0}, …, m_{k} are pairwise coprime, the above system is solvable by the Chinese Remainder Theorem and puts n_{0} into a certain progression N_{0} (mod M), where M = m_{0} ⋯ m_{k}. We assume that N_{0} is the smallest positive integer in this progression. Write

n_{0} = N_{0} + Mℓ.

Then

n_{0} = m_{0} (\frac{N_{0}}{m_{0}} + (\frac{M}{m_{0}} ) ℓ);  (16)
(K/i)n_{0} + 1 = m_{i} (\frac{(K/i)N_{0} + 1}{m_{i}} + (K/i) (\frac{M}{m_{i}} ) ℓ) for i = 1, …, k.  (17)

Put A_{0} = N_{0}/m_{0}, B_{0} = M/m_{0} and for i = 1, …, k put A_{i} = ((K/i)N_{0} + 1)/m_{i} and B_{i} = (K/i)M/m_{i}. It is easy to check that gcd(A_{i}, B_{i}) = 1 for all 0, …, k.

Indeed, say that p | gcd(A_{0}, B_{0}) for some prime p. Then p | m_{i} for some i ∈ {1, …, k}, so that p | (K/i)n_{0}+1. However, we also have that p | n_{0}, and so p | 1 = ((K/i)n_{0}+1)−(K/i)n_{0}, which is impossible.

Assume now that p | gcd(A_{i}, B_{i}) for some i ∈ {1, …, k}. If p | K/i, then p ≤ k + 1, but such primes cannot divide A_{i}. Thus, p | M/m_{i}, and, in particular, p | m_{j} for some j ≠ i. But then p | (K/i)n_{0} + 1 and p | (K/j)n_{0} + 1, therefore p | n_{0}(K/i − K/j) = n_{0}K(j − i)/ij. Clearly, p ∤ n_{0} since p | (K/i)n_{0} + 1. Thus, p | K(i − j)/ij, and so, in particular, p ≤ k + 1. However, p(m_{j}) > F_{K} ≥ K > k + 1, and we obtained a contradiction.

We next see that

Δ = ∏_{0≤i<j≤k}(A_{i}B_{j} − A_{j}B_{i}) ≠ 0.

Indeed, if Δ = 0, then A_{i}B_{j} = A_{j}B_{i} holds for some 0 ≤ i < j ≤ k. Thus, A_{i}/B_{i} = A_{j}/B_{j}, and since both fractions are reduced and with positive denominators, we must have B_{i} = B_{j}. Since all prime factors of m_{i} are > K, this implies m_{i} = m_{j}, which is impossible.

Thus, we have that

n_{0} = m_{0}(A_{0} + B_{0}ℓ) and (K/i)n_{0} + 1 = m_{i}(A_{i} + B_{i}ℓ) for i = 1, …, k,

and the linear forms A_{i} + B_{i}ℓ are primitive and distinct for i = 0, …, k. Next we show that for each prime p, there is ℓ such that none of the above k + 1 forms evaluated in ℓ is zero modulo p. Well, if p ≤ k + 1, this follows because A_{i} + B_{i}ℓ ≡ A_{i} ≢ 0 (mod p) for all i = 0, …, k, while if p > k + 1, then since the degree k + 1 polynomial

∏_{i=0}^{k}(A_{i} + B_{i}x)

is not the zero polynomial modulo p, there must exists a congruence class x ≡ ℓ (mod p) which is not a zero of the above polynomial. Under these conditions, it is known from the Brun sieve (see, for example, Theorem 2.6 on page 85 in H. Halberstam and H. E. Richert [4]), that there exists a constant c > 0 depending on k and the numbers m_{0}, …, m_{k} such that if x > x_{0} (depending on m_{0}, …, m_{k}), then there are ≫ x/(log x)^{k+1} positive integers ℓ < x such that

p(A_{i} + B_{i}ℓ) > x^{c} for all i = 0, …, k.

In particular, ω(A_{i} + B_{i}ℓ) = O(1) holds for all i = 0, …, k, once x sufficiently large. We now take such an ℓ. Observe that

F_{n_{0}}^{(K)} = \frac{F_{Kn_{0}}}{F_{K}} = \frac{F_{Km_{0}}}{F_{K}} · \frac{F_{Km_{0}(A_{0}+B_{0}ℓ)}}{F_{Km_{0}}} .

The first factor on the left is F_{m_{0}}^{(K)}. If there is some prime number dividing both F_{Km_{0}} and F_{Km_{0}(A_{0}+B_{0}ℓ)}/F_{Km_{0}}, then this prime must also divide A_{0} + B_{0}ℓ. This is false for large x since p(A_{0} + B_{0}ℓ) > x^{c} exceeds F_{Km_{0}}. Thus,

f(F_{n_{0}}^{(K)}) = f(F_{m_{0}}^{(K)})f (\frac{F_{Km_{0}(A_{0}+B_{0}ℓ)}}{F_{Km_{0}}} ) .

Let us look at the primes p | F_{Km_{0}(A_{0}+B_{0}ℓ)}/F_{Km_{0}}. Such primes have an index of apparition z(p) dividing Km_{0}(A_{0} + B_{0}ℓ) but not Km_{0}. In particular, z(p) ≥ x^{c}, therefore p ≥ x^{c} − 1. Now by an argument already used in the proof of Lemma 6 and based on Lemma 3, we have that

f (\frac{F_{Km_{0}(A_{0}+B_{0}ℓ)}}{F_{Km_{0}}} ) = ∏_{\begin{matrix}z(p)|Km_{0}(A_{0}+B_{0}ℓ) \\ z(p)∤Km_{0} \end{matrix}}(1 − \frac{1}{p})

= exp (O ( ∑_{\begin{matrix}d|A_{0}+B_{0}ℓ \\ d>1 \end{matrix}} ∑_{d_{1}|Km_{0}} \frac{log(dd_{1})}{dd_{1}} + ∑_{p>x^{c}−1} \frac{1}{p^{2}} )) .

Now Km_{0} has O(1) divisors. Furthermore, since p(A_{0} + B_{0}ℓ) > x^{c}, the number A_{0} + B_{0}ℓ also has O(1) divisors > 1, the smallest one being ≥ x^{c}. Putting all this together, we get that

∑_{\begin{matrix}d|A_{0}+B_{0}ℓ \\ d>1 \end{matrix}} ∑_{d_{1}|Km_{0}} \frac{log(dd_{1})}{dd_{1}} ≪ \frac{log x}{x^{c}} = o(1),

while also

∑_{p>x^{c}−1} \frac{1}{p^{2}} ≪ \frac{1}{x^{c}} = o(1),

both when x → ∞. Thus, we have just showed that

f(F_{n_{0}}^{(K)}) = f(F_{m_{0}}^{(K)})(1 + o(1)) = δ_{0} + ε + o(1)

as x → ∞. In the same way, one proves that

f(F_{n_{i}}^{(i)}) = f(F_{m_{i}}^{(i)})(1 + o(1)) = δ_{i} + ε + o(1) for all i = 1, …, k,

as x → ∞. Thus, choosing a large x, we get an n such that

f(F_{n_{0}}^{(K)}) ∈ (δ_{0} − 2ε, δ_{0} + 2ε) and f(F_{n_{i}}^{(i)}) ∈ (δ_{i} − 2ε, δ_{i} + 2ε) for all i = 1, …, k.

Since ε > 0 was arbitrary, the result follows.

6 Comments and Remarks

As we have already pointed out in the Introduction, typographical changes, such as working with primes p ≡ 7 (mod 8) and with (p − 1)/2 instead of (p + 1)/2 show that the conclusion of Theorem 1 remains valid when the Fibonacci numbers F_{n} are replaced by the Mersenne numbers M_{n} (see Luca [7]). Quite likely, it also applies to other Lucas sequences of the first kind not only to the Fibonacci and Mersenne numbers. Furthermore, the conclusion of the theorem remains also valid when the Euler function ϕ(n) is replaced by the sum of divisors function σ(n), or, more generally, by any multiplicative function g(n) such that there exist two constants c ≠ 0 and λ > 1 with the property that on prime powers p^{a} we have g(p^{a}) = 1 + c/p + O(1/p^{λ}). An example of such a function is the function α(n) which associates to every positive integer n the average order of the elements in the cyclic group of order n. Such function was studied in Luca [8]. On the other hand, it seems very difficult to prove the analogous Theorem 1 when the function ϕ(n) is replaced by one of the functions ω(n), or Ω(n), which count the number of prime power divisors of n, or τ(n), which counts the number of divisors of n. We leave such problems as possible research projects for the interested reader.

7 Acknowledgments

We thank the anonymous referee for pointing out various inaccuracies in a previous version of this manuscript. This work was done during a visit of V. J. M. H. and F. N. at the Mathematical Institute of the UNAM in Morelia, Mexico. During the preparation of this paper, F. L. was supported in part by Grants SEP-CONACyT 79685 and PAPIIT 100508 and V. J. M. H. was supported by Grant UAM-A 2232508 and a Postdoctoral Position at the IFM of UMSNH. He thanks the people of these institutions for their hospitality.

References

[1] N. Doyon and F. Luca, On the local behavior of the Carmichael λ-function, Michigan Math. J. 54 (2006), 283–300.

[2] P. Erdős, K. Győry and Z. Papp, On some new properties of functions σ(n), φ(n), d(n) and ν(n)”, Mat. Lapok 28 (1980), 125–131.

[3] P. Erdős and A. Schinzel Distributions of the values of some arithmetical functions, Acta Arith. 6 1960/1961 473–485.

[4] H. Halberstam and H. E. Richert, Sieve Methods, Academic Press, 1974.

[5] M. O. Hernane and F. Luca, On the independence of ϕ and σ, Acta Arith. 138 (2009), 337–346.

[6] F. Luca, Perfect Fibonacci and Lucas numbers, Rend. Circ. Mat. Palermo, Ser. II 49 (2000), 313–318.

[7] F. Luca, On the sum of divisors of the Mersenne numbers, Math. Slovaca 53 (2003), 457–466.

[8] F. Luca: On some mean values connected with the average order of elements in finite fields, The Ramanujan J. 9 (2005), 33–44.

[9] F. Luca, Fibonacci numbers with the Lehmer property, Bull. Polish Acad. Sci. Math. 55 (2007), 7–15.

[10] F. Luca and F. Nicolae, ϕ(F_{n}) = F_{m}, INTEGERS, to appear.

[11] F. Luca and I. E. Shparlinski, Approximating positive reals by ratios of radicals of consecutive integers, Sem. Math. Sci., Keio Univ. 35 (2006), 141–149.

[12] F. Luca and I. E. Shparlinski, Arithmetic functions with linear recurrences, J. Number Theory 125 (2007), 459–472.

[13] A. Schinzel, On functions φ(n) and σ(n), Bull. Acad. Polon. Sci. Cl. III. 3 (1955), 415–419.

[14] E. B. Wong, Simultaneous approximation of reals by values of arithmetic functions, in Anatomy of Integers, CRM Proc. Lecture Notes 46, Amer. Math. Soc., Providence, RI, 2008, pp. 289–297.

2010 Mathematics Subject Classification: Primary 11A25; Secondary 11B39. Keywords: Fibonacci numbers, Euler function, sieve methods.

(Concerned with sequence \underline{A000045}.)

Received May 20 2009; revised version received September 22 2009; Published in Journal of Integer Sequences, September 22 2009.

Return to Journal of Integer Sequences home page.