PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 101(115) (2017), 231–245 https://doi.org/10.2298/PIM1715231F

PELL NUMBERS WHOSE EULER FUNCTION IS A PELL NUMBER

Bernadette Faye and Florian Luca

Abstract. We show that the only Pell numbers whose Euler function is also a Pell number are 1 and 2.

1. Introduction

Let ϕ(n) be the Euler function of the positive integer n. Recall that if n has the prime factorization

n = p_{1}^{a_{1}} ⋯ p_{k}^{a_{k}}

with distinct primes p_{1}, …, p_{k} and positive integers a_{1}, …, a_{k}, then

ϕ(n) = p_{1}^{a_{1} −1} (p_{1} − 1) ⋯ p_{k}^{a_{k} −1} (p_{k} − 1).

There are many papers in the literature dealing with diophantine equations involving the Euler function in members of a binary recurrent sequence. For example, in [11], it is shown that 1, 2, and 3 are the only Fibonacci numbers whose Euler function is also a Fibonacci number, while in [4] it is shown that the Diophantine equation ϕ(5^{n} − 1) = 5^{m} − 1 has no positive integer solutions (m, n). Furthermore, the divisibility relation ϕ(n) | n−1 when n is a Fibonacci number, or a Lucas number, or a Cullen number (that is, a number of the form n2^{n} + 1 for some positive integer n), or a rep-digit (g^{m} − 1)/(g − 1) in some integer base g ∈ [2, 1000] have been investigated in [10, 5, 7, 3], respectively.

Here we look for a similar equation with members of the Pell sequence. The Pell sequence (P_{n})_{n⩾0} is given by P_{0} = 0, P_{1} = 1 and P_{n+1} = 2P_{n} + P_{n−1} for all n ⩾ 0. Its first terms are

0, 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, 5741, 13860, 33461, 80782, 195025, 470832, …

We have the following result.

2010 Mathematics Subject Classification: 11B39.

Key words and phrases: Pell numbers; Euler function.

B. Faye was supported by a grant from OWSD and SIDA..

F. Luca was supported by an NRF A-rated researcher grant.

Communicated by Žarko Mijajlović.

Theorem 1.1. The only solutions in positive integers (n, m) of the equation

(1.1)  ϕ(P_{n}) = P_{m}

are (n, m) = (1, 1), (2, 1).

For the proof, we begin by following the method from [11], but we add to it some ingredients from [10].

2. Preliminary results

Let (α, β) = (1 + \sqrt{2}, 1 − \sqrt{2}) be the roots of the characteristic equation x^{2} − 2x − 1 = 0 of the Pell sequence {P_{n}}_{n⩾0} . The Binet formula for P_{n} is

P_{n} = \frac{α^{n} − β^{n}}{α − β} for all n ⩾ 0.

This implies easily that the inequalities

(2.1)  α^{n−2} ⩽ P_{n} ⩽ α^{n−1}

hold for all positive integers n.

We let {Q_{n}}_{n⩾0} be the companion Lucas sequence of the Pell sequence given by Q_{0} = 2, Q_{1} = 2 and Q_{n+2} = 2Q_{n+1} + Q_{n} for all n ⩾ 0. Its first few terms are

2, 2, 6, 14, 34, 82, 198, 478, 1154, 2786, 6726, 16238, 39202, 94642, 228486, 551614, …

The Binet formula for Q_{n} is

(2.2)  Q_{n} = α^{n} + β^{n} for all n ⩾ 0.

We use the well-known result.

Lemma 2.1. The relations (i) P_{2n} = P_{n}Q_{n} and (ii) Q_{n}^{2} − 8P_{n}^{2} = 4(−1)^{n} hold for all n ⩾ 0.

For a prime p and a nonzero integer m let ν_{p}(m) be the exponent with which p appears in the prime factorization of m. The following result is well known and easy to prove.

Lemma 2.2. The relations (i) ν_{2}(Q_{n}) = 1 and (ii) ν_{2}(P_{n}) = ν_{2}(n) hold for all positive integers n.

The following divisibility relations among the Pell numbers are well known.

Lemma 2.3. Let m and n be positive integers. We have:

(i) If m | n, then P_{m} | P_{n}, (ii) gcd(P_{m}, P_{n}) = P_{gcd (m,n)} .

For each positive integer n, let z(n) be the smallest positive integer k such that n | P_{k}. It is known that this exists and n | P_{m} if and only if z(n) | m. This number is referred to as the order of appearance of n in the Pell sequence. Clearly, z(2) = 2. Further, putting for an odd prime p, e_{p} = ( \frac{2}{p}), where the above notation stands for the Legendre symbol of 2 with respect to p, we have that z(p) | p − e_{p}. A prime factor p of P_{n} such that z(p) = n is called primitive for P_{n}. It is known that P_{n} has a primitive divisor for all n ⩾ 2 (see [2] or [1]). Write P_{z(p)} = p^{e_{p}} m_{p}, where m_{p} is coprime to p. It is known that if p^{k} | P_{n} for some k > e_{p}, then pz(p) | n. In particular,

(2.3)  ν_{p}(P_{n}) ⩽ e_{p} whenever p ∤ n.

We need a bound on e_{p}. We have the following result.

Lemma 2.4. The inequality

(2.4)  e_{p} ⩽ \frac{(p + 1) logα}{2 logp} .

holds for all primes p.

Proof. Since e_{2} = 1, the inequality holds for the prime 2. Assume that p is odd. Then z(p) | p + ε for some ε ∈ {±1}. Furthermore, by Lemmas 2.1 and 2.3, we have p^{e_{p}} | P_{z(p)} | P_{p+ε} = P_{(p+ε)/2} Q_{(p+ε)/2} . By Lemma 2.1, it follows easily that p cannot divide both P_{n} and Q_{n} for n = (p + ε)/2 since otherwise p will also divide

Q_{n}^{2} − 8P_{n}^{2} = ±4,

a contradiction since p is odd. Hence, p^{e_{p}} divides one of P_{(p+ε)/2} or Q_{(p+ε)/2} . If p^{e_{p}} divides P_{(p+ε)/2} , we have, by (2.1), that p^{e_{p}} ⩽ P_{(p+ε)/2} ⩽ P_{(p+1)/2} < α^{(p+1)/2} , which leads to the desired inequality (2.4) upon taking logarithms of both sides. In case p^{e_{p}} divides Q_{(p+ε)/2} , we use the fact that Q_{(p+ε)/2} is even by Lemma 2.2 (i). Hence, p^{e_{p}} divides Q_{(p+ε)/2} /2, therefore, by formula (2.2), we have

p^{e_{p}} ⩽ \frac{Q_{(p+ε)/2}}{2} ⩽ \frac{Q_{(p+1)/2}}{2} < \frac{α^{(p+1)/2} + 1}{2} < α^{(p+1)/2} ,

which leads again to the desired conclusion by taking logarithms of both sides. □

For a positive real number x we use logx for the natural logarithm of x. We need some inequalities from the prime number theory. For a positive integer n we write ω(n) for the number of distinct prime factors of n. The following inequalities (i), (ii) and (iii) are inequalities (3.13), (3.29) and (3.41) in [15], while (iv) is Théoréme 13 from [6].

Lemma 2.5. Let p_{1} < p_{2} < ⋯be the sequence of all prime numbers. We have:

(i) The inequality p_{n} < n(logn + loglogn) holds for all n ⩾ 6.

(ii) The inequality

∏_{p⩽x} ( 1 + \frac{1}{p − 1} ) < 1.79 logx( 1 + \frac{1}{2(logx)^{2}} )

holds for all x ⩾ 286. (iii) The inequality

ϕ(n) > \frac{n}{1.79 loglogn + 2.5/ loglogn}

holds for all n ⩾ 3.

(iv) The inequality

ω(n) < \frac{logn}{loglogn − 1.1714}

holds for all n ⩾ 26.

For a positive integer n, we put P_{n} = {p : z(p) = n}. We need the following result.

Lemma 2.6. Put S_{n} := ∑ _{p∈P_{n}} \frac{1}{p−1} . For n > 2, we have

(2.5)  S_{n} < min\{ \frac{2 logn}{n}, \frac{4 + 4 loglogn}{ϕ(n)} \}.

Proof. Since n > 2, it follows that every prime factor p ∈ P_{n} is odd and satisfies the congruence p ≡ ±1 (mod n). Further, putting ℓ_{n} := #P_{n}, we have

(n − 1)^{ℓ_{n}} ⩽ ∏_{p∈P_{n}} p ⩽ P_{n} < α^{n−1}

(by inequality (2.1)), giving

(2.6)  ℓ_{n} ⩽ \frac{(n − 1) logα}{log(n − 1)} .

Thus, the inequality

(2.7)  ℓ_{n} < \frac{n logα}{logn}

holds for all n ⩾ 3, since it follows from (2.6) for n ⩾ 4 via the fact that the function x ↦ x/ logx is increasing for x ⩾ 3, while for n = 3 it can be checked directly. To prove the first bound, we use (2.7) to deduce that

(2.8)  S_{n} ⩽ ∑_{1⩽ℓ⩽ℓ_{n}} ( \frac{1}{nℓ − 2} + \frac{1}{nℓ}) ⩽ \frac{2}{n} ∑_{1⩽ℓ⩽ℓ_{n}} \frac{1}{ℓ} + ∑_{m⩾n} ( \frac{1}{m − 2} − \frac{1}{m})

⩽ \frac{2}{n}( ∫_{1}^{ℓ_{n}} \frac{dt}{t} + 1) + \frac{1}{n − 2} + \frac{1}{n − 1} ⩽ \frac{2}{n}( logℓ_{n} + 1 + \frac{n}{n − 2} )

⩽ \frac{2}{n} log( n( \frac{(logα)e^{2+2/(n−2)}}{logn} ) ) .

Since the inequality logn > (logα)e^{2+2/(n−2)} holds for all n ⩾ 800, (2.8) implies that S_{n} < \frac{2}{n} logn for n ⩾ 800. The remaining range for n can be checked on an individual basis. For the second bound on S_{n}, we follow the argument from [10] and split the primes in P_{n} in three groups:

(i) p < 3n; (ii) p ∈ (3n, n^{2}); (iii) p > n^{2};

We have

(2.9) T_{1} = ∑_{\begin{matrix}p∈P_{n} \\ p<3n \end{matrix}} \frac{1}{p − 1} ⩽ \{ \begin{matrix}\frac{1}{n−2} + \frac{1}{n} + \frac{1}{2n−2} + \frac{1}{2n} + \frac{1}{3n−2} & < \frac{10.1}{3n} , n even, \\ \frac{1}{2n−2} + \frac{1}{2n} & < \frac{7.1}{3n} , n odd, \end{matrix}

where the last inequalities above hold for all n ⩾ 84. For the remaining primes in P_{n}, we have

(2.10)  ∑_{\begin{matrix}p∈P_{n} \\ p>3n \end{matrix}} \frac{1}{p − 1} < ∑_{\begin{matrix}p∈P_{n} \\ p>3n \end{matrix}} \frac{1}{p} + ∑_{m⩾3n+1} ( \frac{1}{m − 1} − \frac{1}{m}) = T_{2} + T_{3} + \frac{1}{3n},

where T_{2} and T_{3} denote the sums of the reciprocals of the primes in P_{n} satisfying (ii) and (iii), respectively. The sum T_{2} was estimated in [10] using the large sieve inequality of Montgomery and Vaughan [13] (see also page 397 in [11]), and the bound on it is

(2.11)  T_{2} = ∑_{3n<p<n^{2}}  \frac{1}{p} < \frac{4}{ϕ(n) logn} + \frac{4 loglogn}{ϕ(n)} < \frac{1}{ϕ(n)} + \frac{4 loglogn}{ϕ(n)},

where the last inequality holds for n ⩾ 55. Finally, for T_{3}, we use estimate (2.7) on ℓ_{n} to deduce that

(2.12)  T_{3} < \frac{ℓ_{n}}{n^{2}} < \frac{logα}{n logn} < \frac{0.9}{3n},

where the last bound holds for all n ⩾ 19. To summarize, for n ⩾ 84, we have, by (2.9), (2.10), (2.11) and (2.12),

S_{n} < \frac{10.1}{3n} + \frac{1}{3n} + \frac{0.9}{3n} + \frac{1}{ϕ(n)} + \frac{4 loglogn}{ϕ(n)} = \frac{4}{n} + \frac{1}{ϕ(n)} + \frac{4 loglogn}{ϕ(n)} ⩽ \frac{3 + 4 loglogn}{ϕ(n)}

for n even, which is stronger that the desired inequality. Here, we used that ϕ(n) ⩽ n/2 for even n. For odd n, we use the same argument except that the first fraction 10.1/(3n) on the right-hand side above gets replaced by 7.1/(3n) (by (2.9)), and we only have ϕ(n) ⩽ n for odd n. This was for n ⩾ 84. For n ∈ [3, 83], the desired inequality can be checked on an individual basis. □

The next lemma from [9] gives an upper bound on the sum appearing in the right-hand side of (2.5).

Lemma 2.7. We have

∑_{d|n} \frac{logd}{d} < ( ∑_{p|n} \frac{logp}{p − 1}) \frac{n}{ϕ(n)} .

Throughout the rest of this paper we use p, q, r with or without subscripts to denote prime numbers.

3. Proof of the Theorem

3.1. A bird’e eye view of the proof of the Theorem. In this section, we explain the plan of attack for the proof of the Theorem. We assume n > 2. We put k for the number of distinct prime factors of P_{n} and ℓ = n − m. We first show that 2^{k} | m and that any putative solution must be large. This only uses the fact that p − 1 | ϕ(P_{n}) = P_{m} for all prime factors p of P_{n}, and all such primes with at most one exception are odd. We show that k ⩾ 416 and n > m ⩾ 2^{416}. This is Lemma 3.1. We next bound ℓ in terms of n by showing that ℓ < logloglogn/ logα + 1.1 (Lemma 3.2). Next we show that k is large, by proving that 3^{k} > n/6 (Lemma 3.3). When n is odd, then every prime factor of P_{n} is congruent to 1 modulo 4. This implies that 4^{k} | m. Thus, 3^{k} > n/6 and n > m ⩾ 4^{k}, a contradiction in our range for n. This is done in Subsection 3.5. When n is even, we write n = 2^{s}n_{1} with an odd integer n_{1} and bound s and the smallest prime factor r_{1} of n_{1}. We first show that s ⩽ 3, that if n_{1} and m have a common divisor larger than 1, then r_{1} ∈ {3, 5, 7} (Lemma 3.4). A lot of effort is spend into finding a small bound on r_{1}. As we saw, r_{1} ⩽ 7 if n_{1} and m are not coprime. When n_{1} and m are coprime, we succeed in proving that r_{1} < 10^{6}. Putting e_{r} for the exponent of r in the factorization of P_{z(r)} , it turns out that our argument works well when e_{r} = 1 and we get a contradiction, but when e_{r} = 2, then we need some additional information about the prime factors of Q_{r}. It is always the case that e_{r} = 1 for all primes r < 10^{6}, except for r ∈ {13, 31} for which e_{r} = 2, but, lucky for us, both Q_{13} and Q_{31} have two suitable prime factors each which allows us to obtain a contradiction. Our efforts in obtaining r_{1} < 10^{6} involve quite a complicated argument (roughly the entire argument after Lemma 3.4 until the end), which we believe it is justified by the existence of the mighty prime r_{1} = 1546463, for which e_{r_{1}} = 2. Should we have only obtained say r_{1} < 1.6 × 10^{6}, we would have had to say something nontrivial about the prime factors of Q_{15467463} , a nuisance which we succeeded in avoiding simply by proving that r_{1} cannot get that large!

3.2. Some lower bounds on m and ω(P_{n}) . We start with a computation showing that there are no other solutions than n = 1, 2 when n ⩽ 100. So, from now on n > 100. We write P_{n} = q_{1}^{α_{1}} …q_{k}^{α_{k}} , where q_{1} < ⋯< q_{k} are primes and α_{1}, …, α_{k} are positive integers. Clearly, m < n.

McDaniel [12], proved that P_{n} has a prime factor q ≡ 1 (mod 4) for all n > 14. Thus, McDaniel’s result applies for us showing that 4 | q − 1 | ϕ(P_{n}) | P_{m}, so 4 | m by Lemma 2.2. Further, it follows from a the result of the second author [5], that ϕ(P_{n}) ⩾ P_{ϕ(n)} . Hence, m ⩾ ϕ(n). Thus,

(3.1)  m ⩾ ϕ(n) ⩾ \frac{n}{1.79 loglogn + 2.5/ loglogn} ,

by Lemma 2.5 (iii). The function

x ↦ \frac{x}{1.79 loglogx + 2.5/ loglogx}

is increasing for x ⩾ 100. Since n ⩾ 100, inequality (3.1) together with the fact that 4 | m, show that m ⩾ 24.

Put ℓ = n − m. Since m is even, we have β^{m} > 0, therefore

(3.2)  \frac{P_{n}}{P_{m}} = \frac{α^{n} − β^{n}}{α^{m} − β^{m}} > \frac{α^{n} − β^{n}}{α^{m}} ⩾ α^{ℓ} − \frac{1}{α^{m+n}} > α^{ℓ} − 10^{−40} ,

where we used the fact that

\frac{1}{α^{m+n}} ⩽ \frac{1}{α^{124}} < 10^{−40} .

We now are ready to provide a large lower bound on n. We distinguish the following cases.

Case 1: n is odd. Here, we have ℓ ⩾ 1. So, P_{n}/P_{m} > α − 10^{−40} > 2.4142. Since n is odd, it follows that P_{n} is divisible only by primes q such that z(q) is odd. Among the first 10000 primes, there are precisely 2907 of them with this property. They are

F_{1} = {5, 13, 29, 37, 53, 61, 101, 109, …, 104597, 104677, 104693, 104701, 104717}.

Since

∏_{p∈F_{1}} ( 1 − \frac{1}{p})^{−1} < 1.963 < 2.4142 < \frac{P_{n}}{P_{m}} = ∏_{i=1}^{k} ( 1 − \frac{1}{q_{i}})^{−1} ,

we get that k > 2907. Since 2^{k} | ϕ(P_{n}) | P_{m}, we get, by Lemma 2.2, that

(3.3)  n > m > 2^{2907} .

Case 2: n ≡ 2 (mod 4). Since both m and n are even, we get ℓ ⩾ 2. Thus,

(3.4)  \frac{P_{n}}{P_{m}} > α^{2} − 10^{−40} > 5.8284.

If q is a prime factor of P_{n}, as in Case 1, we have that z(q) is not divisible by 4. Among the first 10000 primes, there are precisely 5815 of them with this property. They are

F_{2} = {2, 5, 7, 13, 23, 29, 31, 37, 41, 47, 53, 61, …, 104693, 104701, 104711, 104717}.

Writing p_{j} as the j^{th} prime number in F_{2}, we check with Mathematica that

∏_{i=1}^{415} ( 1 − \frac{1}{p_{i}} )^{−1} = 5.82753 … ∏_{i=1}^{416} ( 1 − \frac{1}{p_{i}} )^{−1} = 5.82861 …,

which via inequality (3.4) shows that k ⩾ 416. Of the k prime factors of P_{n}, we have that only k − 1 of them are odd (q_{1} = 2 because n is even), but one of those is congruent to 1 modulo 4 by McDaniel’s result. Hence, 2^{k} | ϕ(P_{n}) | P_{m}, which shows, via Lemma 2.2, that

(3.5)  n > m ⩾ 2^{416}.

Case 3: 4 | n. In this case, since both m and n are multiples of 4, we get that ℓ ⩾ 4. Therefore, P_{n}/P_{m} > α^{4} − 10^{−40} > 33.97. Letting p_{1} < p_{2} < ⋯be the sequence of all primes, we have that

∏_{i=1}^{2000} ( 1 − \frac{1}{p_{i}} )^{−1} < 17.41 … < 33.97 < \frac{P_{n}}{P_{m}} = ∏_{i=1}^{k} ( 1 − \frac{1}{q_{i}}) ,

showing that k > 2000. Since 2^{k} | ϕ(P_{n}) = P_{m}, we get

(3.6)  n > m ⩾ 2^{2000} .

To summarize, from (3.3), (3.5) and (3.6), we get the following results.

Lemma 3.1. If n > 2, then (i) 2^{k} | m; (ii) k ⩾ 416; (iii) n > m ⩾ 2^{416}.

3.3. Bounding ℓ in term of n. We saw in the preceding section that k ⩾ 416. Since n > m ⩾ 2^{k}, we have

(3.7)  k < k(n) := \frac{logn}{log2}.

Let p_{j} be the j^{th} prime number. Lemma 2.5 shows that

p_{k} ⩽ p_{⌊k(n)⌋} ⩽ k(n)(logk(n) + loglogk(n)) := q(n).

We then have, using Lemma 2.5 (ii), that

\frac{P_{m}}{P_{n}} = ∏_{i=1}^{k} ( 1 − \frac{1}{q_{i}}) ⩾ ∏_{2⩽p⩽q(n)} ( 1 − \frac{1}{p}) > \frac{1}{1.79 logq(n)(1 + 1/(2(logq(n))^{2}))} .

Inequality (ii) of Lemma 2.5 requires that x ⩾ 286, which holds for us with x = q(n) because k(n) ⩾ 416. Hence, we get

1.79 logq(n)( 1 + \frac{1}{(2(logq(n))^{2})}) > \frac{P_{n}}{P_{m}} > α^{ℓ} − 10^{−40} > α^{ℓ}( 1 − \frac{1}{10^{40}} ) .

Since k ⩾ 416, we have q(n) > 3256. Hence, we get

logq(n)( 1.79( 1 − \frac{1}{10^{40}} )^{−1} ( 1 + \frac{1}{2(log(3256))^{2}} ) ) > α^{ℓ},

which yields, after taking logarithms, to

(3.8)  ℓ ⩽ \frac{loglogq(n)}{logα} + 0.67.

The inequality

(3.9)  q(n) < (logn)^{1.45}

holds in our range for n (in fact, it holds for all n > 10^{83}, which is our case since for us n > 2^{416} > 10^{125}). Inserting inequality (3.9) into (3.8), we get

ℓ < \frac{loglog(logn)^{1.45}}{logα} + 0.67 < \frac{logloglogn}{logα} + 1.1.

Thus, we proved the following result.

Lemma 3.2. If n > 2, then

ℓ < \frac{logloglogn}{logα} + 1.1.

3.4. Bounding the primes q_{i} for i = 1, …, k . Write P_{n} = q_{1} ⋯ q_{k}B, where B = q_{1}^{α_{1} −1} ⋯ q_{k}^{α_{k} −1} . Clearly, B | ϕ(P_{n}), therefore B | P_{m}. Since also B | P_{n}, we have, by Lemma 2.3, that B | gcd(P_{n}, P_{m}) = P_{gcd (n,m)} | P_{ℓ} where the last relation follows again by Lemma 2.3 because gcd(n, m) | ℓ. Using inequality (2.1) and Lemma 3.2, we get

(3.10)  B ⩽ P_{n−m} ⩽ α^{n−m−1} ⩽ α^{0.1} loglogn.

To bound the primes q_{i} for all i = 1, …, k, we use the inductive argument from Section 3.3 in [11]. We write

∏_{i=1}^{k} ( 1 − \frac{1}{q_{i}}) = \frac{ϕ(P_{n})}{P_{n}} = \frac{P_{m}}{P_{n}} .

Therefore,

1 − ∏_{i=1}^{k} ( 1 − \frac{1}{q_{i}}) = 1 − \frac{P_{m}}{P_{n}} = \frac{P_{n} − P_{m}}{P_{n}} ⩾ \frac{P_{n} − P_{n−1}}{P_{n}} > \frac{P_{n−1}}{P_{n}} .

Using the inequality

1 − (1 − x_{1}) ⋯ (1 − x_{s}) ⩽ x_{1} + ⋯+ x_{s} valid for all x_{i} ∈ [0, 1] for i = 1, …, s,

we get,

\frac{P_{n−1}}{P_{n}} < 1 − ∏_{i=1}^{k} ( 1 − \frac{1}{q_{i}}) ⩽ ∑_{i=1}^{k} \frac{1}{q_{i}} < \frac{k}{q_{1}},

therefore, q_{1} < k(P_{n}/P_{n−1} ) < 3k. Using the method of the proof of inequality (13) in [11], one proves by induction on the index i ∈ {1, …, k} that if we put u_{i} := ∏ _{j=1}^{i} q_{j} , then u_{i} < (2α^{2.1}k loglogn)^{(3^{i} −1)/2} . In particular,

q_{1} ⋯ q_{k} = u_{k} < (2α^{2.1}k loglogn)^{(3^{k} −1)/2} ,

which together with formula (3.8) and (3.10) gives

P_{n} = q_{1} ⋯ q_{k}B < (2α^{2.1}k loglogn)^{1+(3^{k} −1)/2} = (2α^{2.1}k loglogn)^{(3^{k} +1)/2} .

Since P_{n} > α^{n−2} by inequality (2.1), we get

(n − 2) logα < \frac{(3^{k} + 1)}{2} log(2α^{2.1}k loglogn).

Since k < logn/ log2 (see (3.7)), we get

3^{k} > (n − 2)( \frac{2 logα}{log(2α^{2.1}(logn)(loglogn)(log2)^{−1} )} ) − 1 > 0.17(n − 2) − 1 > \frac{n}{6},

where the last two inequalities above hold because n > 2^{416}.

So, we proved the following result.

Lemma 3.3. If n > 2, then 3^{k} > n/6.

3.5. The case when n is odd. Assume that n > 2 is odd and let q be any prime factor of P_{n}. Reducing relation Q_{n}^{2} −8P_{n}^{2} = 4(−1)^{n} of Lemma 2.1 (ii) modulo q, we get Q_{n}^{2} ≡ −4 (mod q). Since q is odd, (because n is odd), we get that q ≡ 1 (mod 4). This is true for all prime factors q of P_{n}. Hence,

4^{k} | ∏_{i=1}^{k} (q_{i} − 1) | ϕ(P_{n}) | P_{m},

which, by Lemma 2.2 (ii), gives 4^{k} | m. Thus, n > m ⩾ 4^{k}, inequality which together with Lemma 3.3 gives n > (3^{k})^{log 4/ log 3} > ( \frac{n}{6} )^{log 4/ log 3} , so

n < 6^{log 4/ log(4/3)} < 5621,

in contradiction with Lemma 3.1.

3.6. Bounding n. From now on, n > 2 is even. We write it as

n = 2^{s}r_{1}^{λ_{1}} ⋯ r_{t}^{λ_{t}} =: 2^{s}n_{1},

where s ⩾ 1, t ⩾ 0 and 3 ⩽ r_{1} < ⋯< r_{t} are odd primes. Thus, by inequality (3.2), we have

α^{ℓ}( 1 − \frac{1}{10^{40}} ) < α^{ℓ} − \frac{1}{10^{40}} < \frac{P_{n}}{ϕ(P_{n})} = ∏_{p|P_{n}} ( 1 + \frac{1}{p − 1} ) = 2 ∏_{\begin{matrix}d⩾3 \\ d|n \end{matrix}} ∏_{p∈P_{d}} ( 1 + \frac{1}{p − 1} ) ,

and taking logarithms we get

(3.11)  ℓ logα − \frac{1}{10^{39}} < log( α^{ℓ}( 1 − \frac{1}{10^{40}} ) )

< log2 + ∑_{\begin{matrix}d⩾3 \\ d|n \end{matrix}} ∑_{p∈P_{d}} log( 1 + \frac{1}{p − 1} ) < log2 + ∑_{\begin{matrix}d⩾3 \\ d|n \end{matrix}} S_{d}.

In the above, we used the inequality log(1 − x) > −10x valid for all x ∈ (0, 1/2) with x = 1/10^{40} and the inequality log(1 + x) ⩽ x valid for all real numbers x with x = p for all p ∈ P_{d} and all divisors d | n with d ⩾ 3.

Let us deduce that the case t = 0 is impossible. Indeed, if this were so, then n is a power of 2 and so, by Lemma 3.1, both m and n are divisible by 2^{416}. Thus, ℓ ⩾ 2^{416}. Inserting this into (3.11), and using Lemma 2.6, we get

2^{416} logα − \frac{1}{10^{39}} < ∑_{a⩾1} \frac{2 log(2^{a})}{2^{a}} = 4 log2,

a contradiction.

Thus, t ⩾ 1 so n_{1} > 1. We now put I := {i : r_{i} | m} and J = {1, …, t} ∖ I. We put M = ∏ _{i∈I} r_{i}. We also let j be minimal in J. We split the sum appearing in (3.11) in two parts:

∑_{d|n} S_{d} = L_{1} + L_{2},

where

L_{1} := ∑_{\begin{matrix}d|n \\ r|d⇒r|2M \end{matrix}} S_{d} and L_{2} := ∑_{\begin{matrix}d|n \\ r_{u} |d for some u∈J \end{matrix}} S_{d}.

To bound L_{1}, we note that all divisors involved divide n′, where

n′ = 2^{s} ∏_{i∈I} r_{i}^{λ_{i}} .

Using Lemmas 2.6 and 2.7, we get

(3.12) L_{1} ⩽ 2 ∑_{d|n′} \frac{logd}{d} < 2( ∑_{r|n′} \frac{logr}{r − 1} ) ( \frac{n′}{ϕ(n′)} ) = 2( ∑_{r|2M} \frac{logr}{r − 1} ) ( \frac{2M}{ϕ(2M)} ) .

We now bound L_{2}. If J = ∅, then L_{2} = 0 and there is nothing to bound. So, assume that J ≠ ∅. We argue as follows. Note that since s ⩾ 1, by Lemma 2.1 (i), we have P_{n} = P_{n_{1}} Q_{n_{1}} Q_{2n_{1}} ⋯ Q_{2^{s−1} n_{1}} . Let q be any odd prime factor of Q_{n_{1}} . By reducing relation (ii) of Lemma 2.1 modulo q and using the fact that n_{1} and q are both odd, we get 2P_{n_{1}}^{2} ≡ 1 (mod q), therefore ( \frac{2}{q}) = 1. Hence, z(q) | q − 1 for such primes q. Now let d be any divisor of n_{1} which is a multiple of r_{j}. The number of them is τ(n_{1}/r_{j}), where τ(u) is the number of divisors of the positive integer u. For each such d, there is a primitive prime factor q_{d} of Q_{d} | Q_{n_{1}} . Thus, r_{j} | d | q_{d} − 1. This shows that

(3.13)  ν_{r_{j}} (ϕ(P_{n})) ⩾ ν_{r_{j}} (ϕ(Q_{n_{1}} )) ⩾ τ(n_{1}/r_{j}) ⩾ τ(n_{1})/2,

where the last inequality follows from the fact that

\frac{τ(n_{1}/r_{j})}{τ(n_{1})} = \frac{λ_{j}}{λ_{j} + 1} ⩾ \frac{1}{2}.

Since r_{j} does not divide m, it follows from (2.3) that

(3.14)  ν_{r_{j}} (P_{m}) ⩽ e_{r_{j}} .

Hence, (3.13), (3.14) and (1.1) imply that

τ(n_{1}) ⩽ 2e_{r_{j}} .

Invoking Lemma 2.4, we get

(3.15)  τ(n_{1}) ⩽ \frac{(r_{j} + 1) logα}{logr_{j}} .

Now every divisor d participating in L_{2} is of the form d = 2^{a}d_{1}, where 0 ⩽ a ⩽ s and d_{1} is a divisor of n_{1} divisible by r_{u} for some u ∈ J. Thus,

L_{2} ⩽ τ(n_{1}) min\{ ∑_{\begin{matrix}0⩽a⩽s, d_{1} |n_{1} \\ r_{u} |d_{1} for some u∈J \end{matrix}} S_{2^{a} d_{1}} \} := g(n_{1}, s, r_{1}).

In particular, d_{1} ⩾ 3 and since the function x ↦ logx/x is decreasing for x ⩾ 3, we have that

(3.16)  g(n_{1}, s, r_{1}) ⩽ 2τ(n_{1}) ∑_{0⩽a⩽s} \frac{log(2^{a}r_{j})}{2^{a}r_{j}}.

Putting also s_{1} := min{s, 416}, we get, by Lemma 3.1, that 2^{s_{1}} | ℓ. Thus, inserting this as well as (3.12) and (3.16) all into (3.11), we get

(3.17)  ℓ logα − \frac{1}{10^{39}} < 2( ∑_{r|2M} \frac{logr}{r − 1} ) ( \frac{2M}{ϕ(2M)} ) + g(n_{1}, s, r_{1}).

Since

(3.18)  ∑_{0⩽a⩽s} \frac{log(2^{a}r_{j})}{2^{a}r_{j}} < \frac{4 log2 + 2 logr_{j}}{r_{j}} ,

inequalities (3.18), (3.15) and (3.16) give us that

g(n_{1}, s, r_{1}) ⩽ 2( 1 + \frac{1}{r_{j}} ) ( 2 + \frac{4 log2}{logr_{j}}) logα := g(r_{j}).

The function g(x) is decreasing for x ⩾ 3. Thus, g(r_{j}) ⩽ g(3) < 10.64. For a positive integer N put

f(N) := N logα − \frac{1}{10^{39}} − 2( ∑_{r|N} \frac{logr}{r − 1} ) ( \frac{N}{ϕ(N)} ) .

Then inequality (3.17) implies that both inequalities

(3.19)  f(ℓ) < g(r_{j}), (ℓ − M) logα + f(M) < g(r_{j})

hold. Assuming that ℓ ⩾ 26, we get, by Lemma 2.5, that

ℓ logα − \frac{1}{10^{39}} − 2(log2)\frac{(1.79 loglogℓ + 2.5/ loglogℓ) logℓ}{loglogℓ − 1.1714} ⩽ 10.64.

Mathematica confirmed that the above inequality implies ℓ ⩽ 500. Another calculation with Mathematica showed that the inequality f(ℓ) < 10.64 for even values of ℓ ∈ [1, 500] ∩ ℤ implies that ℓ ∈ [2, 18]. The minimum of the function f(2N) for N ∈ [1, 250] ∩ ℤ is at N = 3 and f(6) > −2.12. For the remaining positive integers N, we have f(2N) > 0. Hence, inequality (3.19) implies

(2^{s_{1}} − 2) logα < 10.64 and (2^{s_{1}} − 2)3 logα < 10.64 + 2.12 = 12.76,

according to whether M ≠ 3 or M = 3, and either one of the above inequalities implies that s_{1} ⩽ 3. Thus, s = s_{1} ∈ {1, 2, 3}. Since 2M | ℓ, 2M is square-free and ℓ ⩽ 18, we have that M ∈ {1, 3, 5, 7}. Assume M > 1 and let i be such that M = r_{i}. Let us show that λ_{i} = 1. Indeed, if λ_{i} ⩾ 2, then

199 | Q_{9} | P_{n}, 29201 | P_{25} | P_{n}, 1471 | Q_{49} | P_{n},

according to whether r_{i} = 3, 5, 7, respectively, and 3^{2} | 199 − 1, 5^{2} | 29201 − 1, 7^{2} | 1471 − 1. Thus, we get that 3^{2}, 5^{2}, 7^{2} divide ϕ(P_{n}) = P_{m}, showing that 3^{2}, 5^{2}, 7^{2} divide ℓ. Since ℓ ⩽ 18, only the case ℓ = 18 is possible. In this case, r_{j} ⩾ 5, and inequality (3.19) gives 8.4 < f(18) ⩽ g(5) < 7.9, a contradiction. Let us record what we have deduced so far.

Lemma 3.4. If n > 2 is even, then s ∈ {1, 2, 3}. Further, if I ≠ ∅, then I = {i}, r_{i} ∈ {3, 5, 7} and λ_{i} = 1.

We now deal with J. For this, we return to (3.11) and use the better inequality namely

2^{s}M logα − \frac{1}{10^{39}} ⩽ ℓ logα − \frac{1}{10^{39}} ⩽ log( \frac{P_{n}}{ϕ(P_{n})}) ⩽ ∑_{d|2^{s} M} ∑_{p∈P_{d}} log( 1+ \frac{1}{p−1} ) + L_{2},

so

L_{2} ⩾ 2^{s}M logα − \frac{1}{10^{39}} − ∑_{d|2^{s} M} ∑_{p∈P_{d}} log( 1 + \frac{1}{p − 1} ) .

In the right-hand side above, M ∈ {1, 3, 5, 7} and s ∈ {1, 2, 3}. The values of the right-hand side above are in fact

h(u) := u logα − \frac{1}{10^{39}} − log(P_{u}/ϕ(P_{u}))

for u = 2^{s}M ∈ {2, 4, 6, 8, 10, 12, 14, 20, 24, 28, 40, 56}. Computing we get:

h(u) ⩾ H_{s,M} ( \frac{M}{ϕ(M)} ) for M ∈ \{1, 3, 5, 7\}, s ∈ \{1, 2, 3\},

where

H_{1,1} > 1.069, H_{1,M} > 2.81 for M > 1, H_{2,M} > 2.426, H_{3,M} > 5.8917.

We now exploit the relation

(3.20)  H_{s,M} ( \frac{M}{ϕ(M)} ) < L_{2}.

Our goal is to prove that r_{j} < 10^{6}. Assume this is not so. We use the bound

L_{2} < ∑_{\begin{matrix}d|n \\ r_{u} |d for sume u∈J \end{matrix}} \frac{4 + 4 loglogd}{ϕ(d)}

of Lemma 2.6. Each divisor d participating in L_{2} is of the form 2^{a}d_{1}, where a ∈ [0, s] ∩ ℤ and d_{1} is a multiple of a prime at least as large as r_{j}. Thus,

\frac{4 + 4 loglogd}{ϕ(d)} ⩽ \frac{4 + 4 loglog8d_{1}}{ϕ(2^{a})ϕ(d_{1})} for a ∈ \{0, 1, …, s\},

and

\frac{d_{1}}{ϕ(d_{1})} ⩽ \frac{n_{1}}{ϕ(n_{1})} ⩽ \frac{M}{ϕ(M)} ( 1 + \frac{1}{r_{j} − 1} )^{ω(n_{1} )} .

Using (3.15), we get

2^{ω(n_{1} )} ⩽ τ(n_{1}) ⩽ \frac{(r_{j} + 1) logα}{logr_{j}} < r_{j} ,

where the last inequality holds because r_{j} is large. Thus,

(3.21)  ω(n_{1}) < \frac{logr_{j}}{log2} < 2 logr_{j} .

Hence,

(3.22)  \frac{n_{1}}{ϕ(n_{1})} ⩽ \frac{M}{ϕ(M)} ( 1 + \frac{1}{r_{j} − 1} )^{ω(n_{1} )} < \frac{M}{ϕ(M)} ( 1 + \frac{1}{r_{j} − 1} )^{2 log r_{j}}

< \frac{M}{ϕ(M)} exp( \frac{2 logr_{j}}{r_{j} − 1} ) < \frac{M}{ϕ(M)} ( 1 + \frac{4 logr_{j}}{r_{j} − 1} ) ,

where we used the inequalities 1 + x < e^{x}, valid for all real numbers x, as well as e^{x} < 1 + 2x which is valid for x ∈ (0, 1/2) with x = 2 logr_{j} /(r_{j} − 1) which belongs to (0, 1/2) because r_{j} is large. Thus, the inequality

\frac{4 + 4 loglogd}{ϕ(d)} ⩽ ( \frac{4 + 4 loglog8d_{1}}{d_{1}} ) ( 1 + \frac{4 logr_{j}}{r_{j} − 1} ) ( \frac{1}{ϕ(2^{a})} ) \frac{M}{ϕ(M)}

holds for d = 2^{a}d_{1} participating in L_{2}. The function x ↦ (4 + 4 loglog(8x))/x is decreasing for x ⩾ 3. Hence,

(3.23) L_{2} ⩽ ( \frac{4 + 4 loglog(8r_{j})}{r_{j}} ) τ(n_{1})( 1 + \frac{4 logr_{j}}{r_{j} − 1} ) ( ∑_{0⩽a⩽s} \frac{1}{ϕ(2^{a})} ) ( \frac{M}{ϕ(M)} ) .

Inserting inequality (3.15) into (3.23) and using (3.20), we get

(3.24)  logr_{j} < 4( 1 + \frac{1}{r_{j}} ) ( 1 + \frac{4 logr_{j}}{r_{j} − 1} ) (1 + loglog(8r_{j}))(logα)( \frac{G_{s}}{H_{s,M}} ) ,

where

G_{s} = ∑_{0⩽a⩽s} \frac{1}{ϕ(2^{a})} .

For s = 2, 3, inequality (3.24) implies r_{j} < 900, 000 and r_{j} < 300, respectively. For s = 1 and M > 1, inequality (3.24) implies r_{j} < 5000. When M = 1 and s = 1, we get n = 2n_{1} and j = 1. Here, inequality (3.24) implies that r_{1} < 8 × 10^{12}. This is too big, so we use the bound

S_{d} < \frac{2 logd}{d}

of Lemma 2.6 instead for the divisors d of participating in L_{2}, which in this case are all the divisors of n larger than 2. We deduce that

1.06 < L_{2} < 2 ∑_{\begin{matrix}d|2n_{1} \\ d>2 \end{matrix}} \frac{logd}{d} < 4 ∑_{d_{1} |n_{1}} \frac{logd_{1}}{d_{1}}.

The last inequality above follows from the fact that all divisors d > 2 of n are either of the form d_{1} or 2d_{1} for some divisor d_{1} ⩾ 3 of n_{1}, and the function x ↦ logx/x is decreasing for x ⩾ 3. Using Lemma 2.7 and inequalities (3.21) and (3.22), we get

1.06 < 4( ∑_{r|n_{1}} \frac{logr}{r − 1} ) ( \frac{n_{1}}{ϕ(n_{1})} ) < ( \frac{4 logr_{1}}{r_{1} − 1} ) ω(n_{1})( 1 + \frac{4 logr_{1}}{r_{1} − 1} )

< ( \frac{4 logr_{1}}{r_{1} − 1} ) ( 2 logr_{1}) ( 1 + \frac{4 logr_{1}}{r_{1} − 1} ) ,

which gives r_{1} < 159. So, in all cases, r_{j} < 10^{6}. Here, we checked that e_{r} = 1 for all such r except r ∈ {13, 31} for which e_{r} = 2. If e_{r_{j}} = 1, we then get τ(n_{1}/r_{j}) ⩽ 1, so n_{1} = r_{j}. Thus, n ⩽ 8 · 10^{6}, in contradiction with Lemma 3.1. Assume now that r_{j} ∈ {13, 31}. Say r_{j} = 13. In this case, 79 and 599 divide Q_{13} which divides P_{n}, therefore 13^{2} | (79 − 1)(599 − 1) | ϕ(P_{n}) = P_{m}. Thus, if there is some other prime factor r′ of n_{1}/13, then 13r′ | n_{1}, and Q_{13r′} has a primitive prime factor q ≡ 1 (mod 13r′). In particular, 13 | q − 1. Thus, ν_{13}(ϕ(P_{n})) ⩾ 3, showing that 13^{3} | P_{m}. Hence, 13 | m, therefore 13 | M, a contradiction. A similar contradiction is obtained if r_{j} = 31 since Q_{31} has two primitive prime factors namely 424577 and 865087 so 31 | M.

This finishes the proof.

Acknowledgement. We thank the referee for comments which improved the quality of this paper.

References

1. Y. F. Bilu, G. Hanrot, P. M. Voutier, Existence of Primitive Divisors of Lucas and Lehmer Numbers. With an appendix by M. Mignotte, J. Reine Angew. Math. 539 (2001), 75–122.

2. R. D. Carmichael, On the numerical factors of the arithmetic forms α^{n} ± β^{n}, Ann. Math. (2) 15 (1913), 30–70.

3. J. Cilleruelo, F. Luca, Repunit Lehmer numbers, Proc. Edinb. Math. Soc., II. Ser. 54 (2011), 55-65.

4. B. Faye, F. Luca, A. Tall, On the equation ϕ(5^{m} − 1) = 5^{n} − 1, Bull. Korean Math. Soc. 52 (2015), 513–524.

5. B. Faye, F. Luca, Lucas numbers with the Lehmer property, Math. Rep., Buchar., to appear.

6. R. Guy, Estimation de la fonction de Tchebychef θ sur le k-ieme nombre premier et grandes valeurs de la fonction ω(n) nombre de diviseurs premiers de n, Acta Arith. 42 (1983), 367–389.

7. J. M. Grau Ribas, F. Luca, Cullen numbers with the Lehmer property, Proc. Am. Math. Soc. 140 (2012), 129–134: Corrigendum 141 (2013), 2941–2943.

8. F. Luca, Arithmetic functions of Fibonacci numbers, Fibonacci Q. 37 (1999), 265–268.

9. , Multiply perfect numbers in Lucas sequences with odd parameters, Publ. Math. 58 (2001), 121–155.

10. , Fibonacci numbers with the Lehmer property, Bull. Pol. Acad. Sci., Math. 55 (2007), 7–15.

11. F. Luca, F. Nicolae, ϕ(F_{m} ) = F_{n}, Integers 9 (2009), A30.

12. W. McDaniel, On Fibonacci and Pell Numbers of the Form kx^{2}, Fibonacci Q. 40, (2002), 41–42.

13. H. L. Montgomery, R. C. Vaughan, The large sieve, Mathematika 20 (1973), 119–134.

14. A. Pethő, The Pell sequence contains only trivial perfect powers, in Sets, graphs and numbers (Budapest, 1991), Colloq. Math. Soc. János Bolyai 60, North-Holland, Amsterdam, (1992), 561–568.

15. J. B. Rosser, L. Schoenfeld, Approximate formulas for some functions of prime numbers, Ill. J. Math. 6 (1962), 64–94.

School of Mathematics (Received 22 08 2015) University of the Witwatersrand (Revised 11 04 2016) Wits, South Africa

Ecole Doctorale de Mathematiques et d’Informatique Université Cheikh Anta Diop de Dakar Dakar Fann, Senegal

 bernadette@aims-senegal.org

School of Mathematics University of the Witwatersrand Wits, South Africa

 florian.luca@wits.ac.za