On the Minimal Number of Solutions of the Equation ϕ(n + k) = Mϕ(n), M = 1, 2

Matteo Ferrari Dipartimento di Scienze Matematiche “G.L. Lagrange” Politecnico di Torino Corso Duca degli Abruzzi 24 10138 Torino Italy

               matteo.ferrari@polito.it

Lorenzo Sillari Scuola Internazionale Superiore di Studi Avanzati (SISSA) Via Bonomea 265 34136 Trieste Italy

                   lsillari@sissa.it

Abstract

We fix a positive integer k and look for solutions n ∈ ℕ of the equations ϕ(n + k) = ϕ(n) and ϕ(n + k) = 2ϕ(n). For k ≤ 12 · 10^{100}, we prove that Fermat primes can be used to build five solutions for the first equation when k is even, and five for the second one when k is odd. Furthermore, for k ≤ 4 · 10^{58}, we show that for the second equation there are at least three solutions when k is even. Our work increases the previously known minimal number of solutions for both equations.

1 Introduction

Euler’s phi function ϕ(n) counts the number of positive integers less than or equal to n that are coprime with n. In 1956, Sierpiński [7] considered the equation

ϕ(n + k) = ϕ(n),  (1)

and proved that, for every positive integer k, there exists at least one solution. This result was improved by Schinzel [5], who showed that (1) has at least two solutions for every positive integer k ≤ 8 · 10^{47}. The upper bound on k was extended to 2 · 10^{58} by Schinzel and Wakulicz [6] for all k, and to 1.38 · 10^{26595411} by Holt [3] for even k. All these results were obtained exhibiting explicit solutions, built proving (or assuming) the existence of prime numbers satisfying certain conditions. Graham, Holt and Pomerance [1] showed that, for even k, if we take j and r such that j and j +k have the same prime factors, and the numbers jr/g + 1, (j + k)r/g + 1, with g = gcd(j, j + k), are both primes not dividing j, then

n = j(\frac{j + k}{g} r + 1)

is a solution of (1) [1, Theorem 1]. Despite the lack of general results, numerical evidence suggests that (1) has infinitely many solutions for every fixed k. This can be proven for some special values of k (cf. [9]).

In the same spirit of Sierpiński, Makowski [4] considered the equation

ϕ(n + k) = 2ϕ(n),  (2)

finding one solution for all fixed k. More recently, the same equation was studied by Hasanalizade [2], who proved that (2) has at least two solutions for all k ≤ 4 · 10^{58} and at least three solutions for some odd k ≤ 4 · 10^{58} [2, Theorem 1]. Hasanalizade also gave [2, Lemma 1] a modified version of [1, Theorem 1], valid for odd k multiple of 3 and for equation (2).

In this paper we find new solutions for (1) and (2). These solutions are obtained in two ways. First, we consider Fermat prime numbers and show that for each Fermat prime it is possible to build a solution for (1), when k is even, and for (2), when k is odd. Numerically, we show that these solutions can be actually built for k ≤ 2 · 10^{100}. Since only five Fermat primes are known, this method provides five different solutions. Second, we exhibit a new solution for equation (2) for even k. Together with the results of Hasanalizade, this gives our main theorem.

Theorem 1. Equation (2) has at least three solutions for all k ≤ 4 · 10^{58}.

We conclude the paper by providing several ways of building particular solutions when certain conditions are met.

2 The equation ϕ(n) = ϕ(n + k)

Let F_{m} denote the m-th Fermat number

F_{m} = 2^{2^{m}} + 1.

It is known that F_{m} is prime for m = 0, …, 4, while it is composite for all 5 ≤ m ≤ 32. It is not known whether or not there exist other values of m such that F_{m} is prime.

Let a and b be positive integers. If the prime factors of a are contained in the prime factors of b we write a |^{∗} b. If a |^{∗} b, then it is easy to see that

ϕ(ab) = aϕ(b).

Moreover, a has the same prime factors as b if and only if a |^{∗} b and b |^{∗} a. In this case, we have that

aϕ(b) = bϕ(a).

We prove the following result:

Theorem 2. Equation (1) has at least six solutions for all even k ≤ 12 · 10^{100}.

Proof. We build a solution for each F_{m} prime, exploiting the elementary fact that (F_{m}−1) |^{∗} k for even k.

Case 1: gcd(F_{m}, k) = 1. We have that

n = (F_{m} − 1)k = 2^{2^{m}}k

is a solution of (1). In fact

ϕ(n + k) = ϕ(F_{m}k) = ϕ(F_{m})ϕ(k) = (F_{m} − 1)ϕ(k),

and

ϕ(n) = ϕ((F_{m} − 1)k) = (F_{m} − 1)ϕ(k).

Note that in this case we have no upper bound on the values of k.

Case 2: F_{m} | k. Assume that there exists a positive integer r such that (F_{m} − 1)r + 1 and F_{m}r + 1 are both primes and do not divide k. Then

n = (F_{m} − 1)(F_{m}r + 1)k

is a solution of (1). In fact

ϕ(n + k) = ϕ(((F_{m} − 1)F_{m}r + F_{m})k) = ϕ(F_{m}((F_{m} − 1)r + 1)k) = F_{m}(F_{m} − 1)rϕ(k),

while

ϕ(n) = ϕ((F_{m} − 1)(F_{m}r + 1)k) = F_{m}(F_{m} − 1)rϕ(k).

\begin{matrix}m & r \\ 0 & 10^{100} + 9760 \\ 1 & 10^{100} + 60128 \\ 2 & 10^{100} + 150326 \\ 3 & 10^{100} + 51326 \\ 4 & 10^{100} + 14786 \end{matrix}

Table 1: Values of m and r.

We have that (F_{m} − 1)r + 1 and F_{m}r + 1 are both prime, for the values of m and r given in table 1.

The numbers (F_{m} − 1)r + 1 and F_{m}r + 1 are certainly prime with k, taking k ≤ 12 · 10^{100}. Indeed, since 2F_{m} | k, taking k < F_{m}((F_{m} −1)r +1), neither (F_{m} −1)r +1 nor F_{m}r +1 divide k. We point out that different choices of m and r provide different solutions. To these we must add the previously known solutions. In particular, Sierpiński’s solution might coincide with one of our solutions for some k, while Schinzel’s solution differs from the ones we provided. Indeed, Schinzel found a solution building a sequence of odd primes q_{1}, q_{2}, …, q_{ℓ}, such that 2q_{i} − 1 is prime for i = 1, …, ℓ, and 2q_{i} − 1 ≠ q_{j} for i, j = 1 … ℓ. Then, for even k < q_{1}q_{2} ⋯ q_{ℓ}, there exists a prime q_{j} in the sequence such that both q_{j} and 2q_{j} − 1 do not divide k. Schinzel’s solution n = (2q_{j} − 1)k differs from our solutions, since the former is an odd multiple of k, while the latter is an even multiple of k. This brings the minimal number of known solutions to six for all even k ≤ 2 · 10^{100}.

Remark 3. It is a well-known conjecture by Dickson that for any fixed a, b there exist infinitely many positive integers r such that both ar + 1 and br + 1 are prime. Following Graham, Holt and Pomerance [1], we write P(a, b) if such a property holds. Assuming P(F_{m}, F_{m} − 1) for m = 0, …, 4, we can remove the upper bound on k, obtaining that (1) has at least six solutions for all even k. Remark 4. Assume that F_{m} divides k, for some fixed m. Then, for any r such that (F_{m} − 1)r + 1 and F_{m}r + 1 are both prime and do not divide k, we find a solution n depending on r. Different values of r yield different solutions. As a consequence, if P(F_{m}, F_{m} − 1) is true, then equation (1) has an infinite number of solutions for all even k such that F_{m} | k.

3 The equation ϕ(n + k) = 2ϕ(n)

Our main results concern the number of solutions of (2). As for equation (1), there is substantial difference in the solutions that can be found for even k and odd k. For equation (1), it has already been observed [1, Table 1] that solutions abound for even k, while they are scarce for odd k. After an extensive numerical investigation, we find that the same phenomenon holds for equation (2), with the parity of k inverted. Indeed, we have an analogous version of Theorem 2 (with a similar proof), that holds for odd k instead of even k.

Theorem 5. Equation (2) has at least five solutions for all odd k ≤ 6 · 10^{100}.

Proof. We build a solution for each F_{m} prime, noting that gcd(F_{m} − 1, k) = 1, and that

F_{m} − 1 = 2ϕ(F_{m} − 1).

Case 1: gcd(F_{m}, k) = 1. We have that

n = (F_{m} − 1)k = 2^{2^{m}}k

is a solution of (2). Again, in this case we have no upper bound on the values of k for which we find solutions.

Case 2: F_{m} | k. Assume that there exists a positive integer r such that (F_{m} − 1)r + 1 and F_{m}r + 1 are both primes and do not divide k. Then

n = (F_{m} − 1)(F_{m}r + 1)k

is a solution of (1). Reasoning similarly to Theorem 2, we have five solutions for all odd k ≤ 6 · 10^{100}. Indeed, since F_{m} | k, taking k < F_{m}((F_{m} − 1)r + 1), neither (F_{m} − 1)r + 1 nor F_{m}r + 1 divide k.

Remark 6. Remarks 3 and 4 are also valid in this case, replacing even k with odd k. In particular for m = 0, Remark 4 applied to equation (2) has, as a consequence, the second part of [2, Lemma 1].

When k is even, equation (2) has at least two solutions. The solution n = k was noticed by Makowski [4]. Another solution was found by Hasanalizade [2], building a sequence of primes [8, \underline{A001259}]. Here we recall the construction. Take a sequence of primes 3 = p_{1} < p_{2} < ⋯ < p_{m} satisfying, for all i = 2, …, m, the following conditions:

• (p_{i} − 2) | ∏_{j≤i−1} p_{j},

• (p_{i} − 1) |^{∗} 2 ∏_{j≤i−1} p_{j},

and such that ∏_{j} p_{j} does not divide k. Let p_{ℓ} be the smallest prime of the sequence such that gcd(p_{ℓ}, k) = 1. Then n = p_{ℓ}/(p_{ℓ} −2)k is a solution of equation (2). Building the explicit sequence of primes {3, 5, 7, 17, 19, 37, 97, 113, 257, 401, 487, 631, 971, 1297, 1801, 19457, 22051, 28817, 65537, 157303, 160001}, we have one solution different from n = k for all even k ≤ 4 · 10^{58}.

Now we find a new third solution for even k.

Theorem 7. Equation (2) has at least three solutions for all even k ≤ 4 · 10^{58}.

Proof. Assume that there exists a sequence of prime numbers 2 = p_{1} < p_{2} < ⋯ < p_{m} and of positive integers a_{2} < ⋯ < a_{m} such that, for all i = 2, …, m, the following conditions hold:

• p_{i} = 2a_{i} + 1,

• a_{i} |^{∗} ∏_{j≤i−1} p_{j},

• (a_{i} + 1) | ∏_{j≤i−1} p_{j},

and such that ∏_{j} p_{j} does not divide k. Let p_{ℓ} be the smallest prime such that gcd(p_{ℓ}, k) = 1. Then n = a_{ℓ}k/(a_{ℓ} + 1) is a solution of (2). In fact

ϕ(n + k) = ϕ(\frac{2a_{ℓ} + 1}{a_{ℓ} + 1}k) = 2a_{ℓ}ϕ(\frac{k}{a_{ℓ} + 1}),

and

2ϕ(n) = 2ϕ(\frac{a_{ℓ}}{a_{ℓ} + 1}k) = 2a_{ℓ}ϕ(\frac{k}{a_{ℓ} + 1}).

A sequence of primes [8, \underline{A358717}], up to 10^{8}, satisfying the above assumptions is given by

{2, 3, 5, 11, 19, 37, 73, 109, 1459, 2179, 2917, 4357, 8713}.

The product of the prime numbers in the above sequence is of the order of 6·10^{26}, and ∏_{j} p_{j} does not divide k, for k < ∏_{j} p_{j}. To improve the upper bound on k, we slightly modify our argument. We proceed as follows:

• If k is not divisible by 2 · 3 · 5 · 11 · 19, then we simply apply our argument with no changes.

• If 2 · 3 · 5 · 7 · 11 · 19 | k, we take the sequence starting with 2, 3, 5, 7 and then built using the rules as explained before. The solution to (2) will be again n = a_{ℓ}k/(a_{ℓ} + 1), where ℓ is the smallest index such that gcd(p_{ℓ}, k) = 1. The sequence [8, \underline{A358718}] continues as

{2, 3, 5, 7, 11, 13, 19, 29, 37, 41, 43, 59, 73, 83, 109, 113, 131, 163, 173, 181,
227, 257, 331, 347, 353, 379, 419, 491, 523, 571, 601, 653, 661, 677, …, 12011}.

In this case, since the sequence contains the number 7, it becomes dense enough in the primes to give a large upper bound. We find that such upper bound can be taken to be of the order of 2 · 10^{310}.

• If 2 · 3 · 5 · 11 · 19 | k, gcd(7, k) = 1, and gcd(13, k) = 1, then n = 36k/55 is a solution of (2).

• If 2·3·5·11·13·19 | k, gcd(7, k) = 1, and gcd(23, k) = 1, then n = 66k/95 is a solution of (2).

• If 2 · 3 · 5 · 11 · 13 · 19 · 23 | k and gcd(7, k) = 1, we find, proceeding as before, the following sequence [8, \underline{A358719}]:

{2, 3, 5, 11, 13, 23, 19, 37, 73, 109, 131, 229, 457, 571, 1459, 1481, 2179, 2621,
2917, 2963, 4357, 8713, 49921, 1318901, 3391489, 6782977, 13565953},

that gives the upper bound of 2 · 10^{83}.

We conclude the proof by observing that our solution differs from the previously known solutions, since in our case n < k. Indeed, Hasanalizade’s solutions [2] satisfy n ≥ k.

Remark 8. Our trick can be repeated as many times as desired to improve the upper bound on k, as long as we can find particular solutions.

As a consequence we obtain our main theorem.

Proof of Theorem 1. Theorem 5 proves that for all odd k ≤ 2 · 10^{100} there are at least five solutions to equation (2), while Theorem 7 proves that for all even k ≤ 4 · 10^{58} we have at least three solutions. Overall, we get three solutions for all k ≤ 4 · 10^{58}.

Remark 9. We recall that while the upper bound on k for our new solution is fairly high, increasing the upper bound of 4·10^{58} for Hasanalizade’s solution would require a lot of effort, as pointed out by Holt [3].

4 Special solutions

We open the section with a modified version of the first part of [2, Lemma 1]. Our result removes the assumption 3 | k.

Lemma 10. Let k be an odd positive integer. Suppose that j is a positive integer such that j and 2j + k have the same prime factors. Take g = gcd(j, 2j + k) and consider a positive integer r such that 2jr/g + 1 and (2j + k)r/g + 1 are both prime and coprime with k. Then

n = 2j(\frac{2j + k}{g} r + 1)

is a solution of equation (2).

Proof. We have that

ϕ(n + k) = ϕ(2j(\frac{2j + k}{g} r + 1) + k) = ϕ((2j + k)(\frac{2j}{g} r + 1)) = 2jϕ(2j + k)\frac{r}{g} ,

and

2ϕ(n) = 2ϕ(2j(\frac{2j + k}{g} r + 1)) = 2ϕ(2j)ϕ(\frac{2j + k}{g} r + 1) = 2ϕ(2j)(2j + k)\frac{r}{g} .

We conclude the result using that

2jϕ(2j + k) = 2jϕ(2(2j + k)) = ϕ(4j(2j + k)) = 2ϕ(2j)(2j + k).

Motivated by explicit computations, we would like to find more general formulas that provide new families of solutions to (2). In practice, we always find at least four solutions in the range n ≤ 10^{6}, for k ≤ 10^{4}. The only value of k for which we find exactly 4 solutions is k = 6. In that case, the solutions are

n ∈ {4, 6, 7, 10}.

A computer search yielded no other solutions n ≤ 10^{8} for k = 6. We notice that n = 6 is the solution given by Makowski and n = 10 is the solution from Hasanalizade, while n = 4 is obtained via our method with a_{ℓ} = 2. There is no known family of solutions providing n = 7. In an attempt to find such a family, we prove the following result.

Proposition 11. Assume that there exists a prime p such that 2p − 1 is prime, gcd(p, k) = 1, gcd(2p − 1, k) = 1, and (p − 1) | k. Then

n = \frac{p}{p − 1}k

is a solution of (2).

Proof. It is immediate to check that

ϕ(n + k) = ϕ(k \frac{p}{p − 1} + k) = ϕ(k \frac{2p − 1}{p − 1}) = (2p − 2)ϕ(\frac{k}{p − 1}),

and

2ϕ(n) = 2ϕ(k \frac{p}{p − 1}) = 2(p − 1)ϕ(\frac{k}{p − 1}).

We can take p = 7 and obtain the solution n = 7, for k = 6. Unfortunately, this cannot be generalized to all even k, since the condition (p−1) | k is satisfied only for a finite number of p and it might happen that none of them satisfies the other requirements (e.g., k = 10).

We observe that for all odd k, thanks to Proposition 11, we can take p = 2 and recover the solution n = 2k given by Makowski.

Finally, we conclude the paper by giving one more way of building solutions in another special case.

Proposition 12. Let k be an even positive integer. Assume that there exists m such that m | k, gcd(m + 2, k) = 1, gcd(m + 4, k) = 1, and ϕ(m + 2) = ϕ(m + 4). Then

n = \frac{m + 4}{m}k

is a solution of (2).

Proof. Again, it is immediate to check that

ϕ(n + k) = ϕ(k \frac{m + 4}{m} + k) = 2ϕ(k \frac{m + 2}{m}) = 2ϕ(m + 2)ϕ(\frac{k}{m}),

and

2ϕ(n) = 2ϕ(k \frac{m + 4}{m}) = 2ϕ(m + 4)ϕ(\frac{k}{m}).

5 Acknowledgments

We thank the anonymous referee for suggesting an argument that improved the upper bound on k in Theorems 2 and 5. We also thank the referee for very helpful comments that improved the exposition of the paper. The first author is partially supported by MIUR grant “Dipartimenti di Eccellenza 2018-2022”, CUP E11G18000350001. The second author is partially supported by GNSAGA of INdAM. The numerical computations supporting our paper have been performed using Magma V2.27-5, and are available upon request to the first author.

References

[1] S. W. Graham and J. J. Holt and C. Pomerance, On the solutions to ϕ(n) = ϕ(n + k), in Number Theory in Progress: Proceedings of the International Conference on Number Theory organized by the Stefan Banach International Mathematical Center in Honor of the 60th Birthday of Andrzej Schinzel, Zakopane, Poland, June 30–July 9, 1997, De Gruyter, 2012, pp. 867–882.

[2] E. Hasanalizade, On the equation ϕ(n + k) = 2ϕ(n), Integers 21 (2021), Paper No. A68.

[3] J. J. Holt, The minimal number of solutions to ϕ(n) = ϕ(n+k), Math. Comp. 72 (2003), 2059–2061.

[4] A. Makowski, On the equation ϕ(n + k) = 2ϕ(n), Elem. Math. 29 (1974), 13.

[5] A. Schinzel, Sur l’équation ϕ(x + k) = ϕ(x), Acta Arith. 4 (1958), 181–184.

[6] A. Schinzel and A. Wakulicz, Sur l’équation ϕ(x + k) = ϕ(x) II, Acta Arith. 5 (1959), 425–426.

[7] W. Sierpiński, Sur une propriété de la fonction ϕ(n), Publ. Math. Debrecen 4 (1956), 184–185.

[8] N. J. A. Sloane et al., The On-line Encyclopedia of Integer Sequences, 2020. Available

   at https://oeis.org/.

[9] K. Sungjin, On the equations ϕ(n) = ϕ(n + k) and ϕ(p − 1) = ϕ(q − 1), Int. J. Number Theory 17 (2021), 1287–1305.

2020 Mathematics Subject Classification: Primary 11N25. Secondary 11Y99. Keywords: Euler’s phi function.

(Concerned with sequences \underline{A001259}, \underline{A358717}, \underline{A358718}, and \underline{A358719}.)

Received September 7 2022; revised versions received December 27 2022; January 14 2023. Published in Journal of Integer Sequences, January 15 2023.

Return to Journal of Integer Sequences home page.