On Composite Odd Numbers k for Which 2^{n}k is a Noncototient for All

Positive Integers n

Marcos J. González and Alberto Mendoza Departamento de Matemáticas Puras y Aplicadas

Universidad Simón Bolívar Sartenejas, Apartado 89000

Caracas, 1080-A Venezuela

mago@usb.ve
jakob@usb.ve

Florian Luca School of Mathematics

University of the Witwatersrand 1 Jan Smuts Avenue Braamfontein 2050

Johannesburg South Africa

and

Research Group in Algebraic Structures and Applications

King Abdulaziz University

Jeddah Saudi Arabia

florian.luca@wits.ac.za

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

Abstract We provide some results relating Riesel numbers with families of cototients and

noncototients.

1 Introduction

A positive integer k is called a Riesel number whenever k is odd and k2^{n} − 1 is composite for every nonnegative integer n. These numbers are named after Hans Riesel who in 1956 discovered this property for the number k = 509203 (see [6]). This is conjectured to be the smallest Riesel number. A conjecture due to Erdős asserts that if k is a Riesel number then the smallest prime factor p_{n} of k2^{n} − 1 is bounded as n tends to infinity (see [4]). We refer to such a k as an Erdős-Riesel number. As far as we know, each known example of a Riesel number is also an Erdős-Riesel number.

A positive integer n is a noncototient if n ≠ m − φ(m), for every integer m ≥ 2, where φ(m) denotes Euler’s totient function. Notice that k is a Riesel number if and only if k2^{n} ≠ p + 1 = 2p − φ(2p), for every odd prime p. Sierpiński and Erdős asked whether or not there exist infinitely many noncototients. This question was answered affirmatively by Browkin and Schinzel [1], by showing that the number k = 509203 has the property that k2^{n} is a noncototient for every n ≥ 1. In 2005, Flammenkamp and Luca [3] found six more numbers with this property, namely:

2554843, 9203917, 9545351, 10645867, 11942443, 65484763.

The method used in [3] is based on the fact that if k is a prime Riesel number, which is not a Mersenne prime, and 2k is a noncototient, then 2^{n}k is a noncototient, for every n ≥ 1 (see [3, Proposition 1]). For prime values of k, Grytczuk and Mȩdryk [5] proved that the criterion employed in [3] are optimal; more precisely, they proved that for a prime integer k, 2^{n}k is a noncototient for every n ≥ 1, if and only if 2k is a noncototient and k is a Riesel number which is not a Mersenne prime (see [5, Theorem 1]). They also proved that if k is prime and 2k is a cototient then 2k = m − φ(m) for some even, squarefree integer m (see [5, Theorem 3]). We conclude that in this approach—adopted to find infinite families of noncototients—it is essential to work with prime numbers. The sequence of Riesel numbers is \underline{A101036} and starts as

509203, 762701, 777149, 790841, 992077, 1106681, 1247173, 1254341, …

Our first aim in this paper is to present a method also valid for composite Riesel numbers. As an application, we have obtain the following:

Theorem 1. For each k in the set

{762701, 790841, 992077, 1247173, 1730653, 1744117, 1830187, 1976473, 3419789, 3423373},

the number 2^{n}k is a noncototient, for every n ≥ 1.

It is worth adding that the 10 Riesel numbers displayed in the statement of Theorem 1 are all composite. One may ask what can one say about Riesel numbers k such that 2^{n}k is a cototient for some n ≥ 1. We next result addresses such Riesel numbers.

Theorem 2. There are infinitely many Riesel numbers k such that 2^{n}k is a cototient for some n ≥ 1.

2 The proof of Theorem 1

Given non-zero integers a, p, with p prime, we let ν_{p}(a) denote the exponent of p in the prime factorization of a. Further, we use P (n) for the largest prime factor of n. The following lemma is our workhorse when attempting to detect Riesel numbers k such that 2^{n}k is a noncototient for some positive integer n.

Lemma 3. Let k be a Riesel number. Put p := P (k) and assume

2^{ν_{2}(p+1)}k ≠ p^{ν_{p}(k)}(p + 1).  (1)

The following conditions are equivalent:

(i) for some n ≥ 1, the number 2^{n}k is a cototient;

(ii) for every n ≥ 1, the number 2^{n}k is a cototient.

Proof. It is clear that (ii) implies (i), so it is enough to show that (i) implies (ii).

Assume that (i) holds and let n_{0} ≥ 1 be minimal such that 2^{n_{0}}k = m − ϕ(m) for some positive integer m. Since 2^{2} − 1 = 3 is prime and k is a Riesel number, it follows that k ≥ 3, so m ≥ 6. In particular, ϕ(m) is even. The equation 2^{n_{0}}k = m − ϕ(m) implies that m is even.

Consider the case n_{0} > 1. If 4 | ϕ(m), then 4 | m and 2^{n_{0}−1}k = (m/2) − ϕ(m/2), contradicting the minimality of n_{0}. So, m ≥ 6 is even and 2∥ϕ(m) showing that m = 2q^{e} for some odd prime q and positive integer exponent e. But then

2^{n_{0}}k = m − ϕ(m) = 2q^{e} − q^{e−1}(q − 1) = q^{e−1}(q + 1).

If e > 1, then q = P (k) = p and e − 1 = ν_{p}(k). Since k is odd, we get ν_{2}(p + 1) = n_{0}. Thus,

2^{ν_{2}(p+1)}k = p^{ν_{p}(k)}(p + 1),

which we assumed not to hold. If e = 1, then 2^{n_{0}}k − 1 = q is prime, contradicting the fact that k is Riesel. Thus, n_{0} = 1. Since m is even, we have 2k = m − ϕ(m) and m is even. Hence, for all n ≥ 1, we have 2^{n}k = (2^{n−1}m) − ϕ(2^{n−1}m) is a cototient, which is (ii).

In particular, if we want k to be a Riesel number such that 2^{n}k is a noncototient for all n, it suffices to do two things:

(i) Check condition (1).

(ii) Check that 2k is a noncototient.

Given k, condition (i) is immediate to check. For (ii), we need to see whether there is a representation 2k = m − ϕ(m) for some positive integer m. As we said, if this is so then m is even, so ϕ(m) ≤ m/2; hence, 2k = m − ϕ(m) ≥ m/2, showing that m ≤ 4k. Further, m ≡ 2 (mod 4). Entry \underline{A101036} lists 28 Riesel numbers, with the largest one being 3580901 < 4 × 10^{6}. If one of them say k is such that 2k = m − ϕ(m), then m = 2(2ℓ + 1) for some ℓ < 4 × 10^{6}. We generated with Mathematica the set of numbers of the form

{m − ϕ(m) : m ≡ 2(2ℓ + 1), ℓ < 4 × 10^{6}}.

There are 2117016 such numbers. We intersected this set with the set of numbers of the form 2k, where k runs through the 28 Riesel numbers appearing in . Of these 28, only 16 numbers k survived. All of them passed condition (1) but 6 of them were primes. The remaining 10 are displayed in the statement of Theorem 1.

3 The proof of Theorem 2

Proof. Let us recall how one constructs Riesel numbers. Consider a system of triples {(a_{i}, b_{i}, p_{i})}_{i=1}^{t} of integers that satisfies the following two properties:

cov For every n ∈ ℤ, there exists i ∈ {1, 2, …, t} such that n ≡ a_{i} (mod b_{i}),

ord the numbers p_{1}, …, p_{t} are prime, pairwise distinct and p_{i} | 2^{b_{i}} − 1 for i = 1, 2, …, t.

Such covering progressions appeared in Erdős work [2] in the context of proving that there are infinitely many odd integers not of the form 2^{n} + p, where p is some prime. As for Riesel numbers, any odd positive integer k solving the system of congruences

k ≡ 2^{−a_{i}} (mod p_{i}), i = 1, 2, …, t,  (2)

fulfilling in addition the inequality k ≥ max{p_{1}, …, p_{t}}, is a Riesel number. In addition to these congruences, we also want k to satisfy (1). Assuming that ν_{p}(k) = 1, we impose the additional condition 2^{ν_{2}(p+1)}k = p(p + 1). Note that if k satisfies the above equation, then p = P (k). Consider the system of triples

{(a_{i}, b_{i}, p_{i})}_{i=1}^{7} = {(1, 2, 3), (2, 4, 5), (4, 8, 17), (8, 16, 257), (16, 32, 65537),
(32, 64, 6700417), (0, 64, 641)},

which is known to fulfill conditions cov and ord (see [4]). We note that 2^{a_{i}} ≡ ±1 ≡ 2^{−a_{i}} (mod p_{i}), for every i = 1, …, 7. Choosing ν_{2}(p + 1) = 30, the equation 2^{30}k = p(p + 1) implies

2^{30−a_{i}} ≡ p(p + 1) (mod p_{i})

for i = 1, 2, …, 7. One checks that the quadratic equations 2^{30−a_{i}} ≡ x(x + 1) (mod p_{i}) have an integer solution x for each i = 1, …, 7. The condition ν_{2}(p + 1) = 30 is equivalent to p ≡ 2^{30} − 1 (mod 2^{31}). Thus, by the Chinese Remainder Lemma there is an odd integer x coprime to p_{1}p_{2} ⋯ p_{7} such that the residue class x modulo 2^{31}p_{1} ⋯ p_{7} satisfies all the above congruences. By Dirichlet’s theorem on primes in arithmetic progressions, there are infinitely many prime numbers p in the above progression. For example,

p = 151673607358419855439422291967

satisfies all the above congruences. With each such prime p, the number k = p(p + 1)/2^{30} is a Riesel number satisfying the required property, namely that 2^{n}k is a cototient for all n ≥ 1. These numbers resemble Riesel numbers that are perfect powers, which have been studied in [4].

4 Acknowledgments

We thank the referee for a careful reading of the manuscript and suggestions that led to the current formulation of Theorem 2 and proofs of our results. During the preparation of this paper, V. J. M. H. was supported by Grant UAM-A.

References

[1] J. Browkin and A. Schinzel, On integers not of the form n − φ(n), Colloq. Math. 68 (1995), 55–58.

[2] P. Erdős, On integers of the form 2^{k} +p and some related problems, Summa Brasil. Math. 2 (1950), 113–123.

[3] A. Flammenkamp and F. Luca, Infinite families of noncototients, Colloq. Math. 86 (2000), 37–41.

[4] M. Filaseta, C. Finch, and M. Kozek, On powers associated with Sierpiński numbers, Riesel numbers and Polignac’s conjecture, J. Number Theory 128 (2008), 1916–1940.

[5] A. Grytczuk and B. Mȩdryk, On a result of Flammenkamp-Luca concerning noncototient sequence, Tsukuba J. Math. 29 (2005), 533–538.

[6] H. Riesel, Några stora primtal, Elementa 39 (1956), 258–260.

2010 Mathematics Subject Classification: Primary 11A51; Secondary 11A07, 11N25. Keywords: Riesel number, cototient.

(Concerned with sequence \underline{A101036}.) Received March 9 2021; revised version received March 10 2021; October 15 2021. Published in Journal of Integer Sequences, October 17 2021. Return to Journal of Integer Sequences home page.