A note on primes in certain residue classes

21 July 2021

Original Citation:

A note on primes in certain residue classes

Published version:

DOI:10.1142/S1793042118501336

Terms of use:

Open Access

(Article begins on next page)

Anyone can freely access the full text of works made available as "Open Access". Works made available under a

Creative Commons license can be used according to the terms and conditions of said license. Use of all other works

requires consent of the right holder (author or publisher) if not exempted from copyright protection by the applicable law.

Availability:

This is the author's manuscript

A note on primes in certain residue classes

Paolo Leonetti

Department of Statistics, Universit`a “Luigi Bocconi” Via Roberto Sarfatti 25, 20100 Milano, Italy

leonetti.paolo@gmail.com Carlo Sanna

Department of Mathematics, Universit`a degli Studi di Torino Via Carlo Alberto 10, 10123 Torino, Italy

carlo.sanna.dev@gmail.com

Received (Day Month Year) Accepted (Day Month Year)

Given positive integers a1, . . . , ak, we prove that the set of primes p such that

p 6≡ 1 mod aifor i = 1, . . . , k admits asymptotic density relative to the set of all primes

which is at leastQk i=1  1 − 1 ϕ(ai) 

, where ϕ is the Euler totient function. This result is similar to the one of Heilbronn and Rohrbach, which says that the set of positive integer n such that n 6≡ 0 mod ai for i = 1, . . . , k admits asymptotic density which is at least

Qk i=1  1 −_a1 i  .

Keywords: congruences; densities; primes in residue classes; set of multiples. Mathematics Subject Classification 2010: 11N13, 11N05, 11N69.

1. Introduction

The natural density of a set of positive integers A is defined as

d(A) :=

lim

x→+∞

#(A ∩ [1, x])

x

,

whenever this limit exists. The study of natural densities of sets of positive integers

satisfying some arithmetic constraints is a classical research topic. In particular,

Heilbronn [10] and Rohrbach [11] proved, independently, the following result:

Theorem 1.1. Let a

1

, . . . , a

k

be some positive integers. Then, the set A of positive

integers n such that n 6≡ 0 mod a

i

for i = 1, . . . , k has natural density satisfying

d(A) ≥

k

Y

i=1



1 −

1

a

i



.

1

2 P. Leonetti and C. Sanna

Generalizations of Theorem 1.1 were given, for instance, by Behrend [3] and

Chung [5]. We refer to [9] for a textbook exposition and to [1,2,8,12] for related

results. It is worth noting that Besicovitch [4] proved that, given a sequence of

positive integers (a

i

)

i≥1

, the set A of positive integers n not divisible by any a

i

does

not necessarily admit natural density. However, Davenport and Erd˝

os [6] proved

that A always admits logarithmic density, i.e., the following limit exists:

lim

x→+∞

1

log x

X

n ∈ A ∩ [1,x]

1

n

.

The purpose of this note is to prove a result for the set of primes analogous to

Theorem 1.1. Of course, to this aim, the natural density is not the right quantity

to consider, since it is well known that the set of primes has natural density equal

to zero.

Define the relative density of a set of primes P to be

r(P) :=

lim

x→+∞

#(P ∩ [1, x])

x/ log x

,

whenever this limit exists. Furthermore, let ϕ denote the Euler totient function.

Our result is the following:

Theorem 1.2. Let a

1

, . . . , a

k

be positive integers. Then the set P of primes p such

that p 6≡ 1 mod a

i

for i = 1, . . . , k has relative density satisfying

r(P) ≥

k

Y

i=1



1 −

1

ϕ(a

i

)



.

2. Preliminaries

We begin by fixing some notations with the aim of simplifying the exposition.

Let N be the set of positive integers. Put

_{Jx, yK := [x, y] ∩ N for all x ≤ y, and}

let the other “integral interval” notations, like

_{Kx, yK, be defined in the obvious}

way. For vectors x = (x

1

, . . . , x

d

) and y = (y

1

, . . . , y

d

) belonging to N

d

, define

kxk := x

1

· · · x

d

and

Jx, yK := Jx

1

, y

1

K × · · · × Jx

d

, y

d

K. Also, all the elementary

operations of addition, subtraction, multiplication, and division between vectors

are meant to be component-wise, e.g., xy := (x

1

y

1

, . . . , x

d

y

d

). Let 0, respectively

1, be the vector of N

d

_{with all components equal to 0, respectively 1, where d}

will be always clear from the context. Finally, write x ≡ y mod m if and only if

x

i

≡ y

i

mod m

i

for all i = 1, . . . , d, where m = (m

1

, . . . , m

d

) ∈ N

d

, and write

x 6≡ y mod m if and only if x

i

6≡ y

i

mod m for at least one i ∈

J1, dK.

We will need the following lemma, which might be interesting per se.

Lemma 2.1. Let d be a positive integer and let a

1

, . . . , a

k

, b ∈ N

d

be vectors such

x ∈

J1, bK such that x 6≡ 0 mod a

i

for i = 1, . . . , k satisfies

#X ≥ kbk ·

k

Y

i=1



1 −

1

ka

i

k



.

Proof. Define c := a

1

· · · a

k

and let Y be the set of y ∈

J1, cK

such that

y 6≡ 0 mod a

i

for i = 1, . . . , k. Then, a result of Chung [5] says that

#Y ≥ kck ·

k

Y

i=1



1 −

1

ka

i

k



.

(2.1)

Clearly, Y can be partitioned in kc/bk sets given by

Y

t

:=

Kb(t − 1), btK ∩ Y ,

for t ∈

_{J1, c/bK. (Note that c/b ∈ N}

d

_{since a}

1

· · · a

k

≡ 0 mod b.) Therefore, by

(2.1) there exists some t ∈

_{J1, c/bK such that}

#Y

t

≥

#Y

kc/bk

≥ kbk ·

k

Y

i=1



1 −

1

ka

i

k



.

Moreover, for each y ∈ Y

t

there exists a unique x ∈

J1, bK such that x ≡ y mod b.

Finally, since b ≡ 0 mod a

i

for i = 1, . . . , k, it follows easily that the map y 7→ x is

an injection Y

t

→ X , so that #X ≥ #Y

t

and the proof is complete.

We will also use the following version of Dirichlet’s theorem on primes in

arith-metic progressions [7, pag. 82].

Theorem 2.2. For all coprime positive integers a and b, the set of primes p such

that p ≡ a mod b has relative density equal to 1/ϕ(b).

3. Proof of Theorem 1.2

Put ` := lcm(a

1

, . . . , a

k

) and let ` = p

e11

· · · p

ed

d

be the canonical prime

factoriza-tion of `, where p

1

< · · · < p

d

are primes and e

1

, . . . , e

d

are positive integers.

Furthermore, let S be the set of all n ∈

_{J1, `K such that: n is relatively prime to `,}

and n 6≡ 1 mod a

i

for i = 1, . . . , k. Thanks to Theorem 2.2, we have

r(P) =

lim

x→+∞

#(P ∩ [1, x])

x/ log x

=

x→+∞

lim

X

n∈S

#{p ≤ x : p ≡ n mod `}

x/ log x

=

#S

ϕ(`)

,

(3.1)

hence the relative density of P exists, and all we need is the right lower bound for

#S.

For the sake of clarity, let us first assume that 8 - `. Later, we will

ex-plain how to adapt the proof for the case 8 | `. Let g

i

be a primitive root

modulo p

ei

i

, for i = 1, . . . , d. Note that g

1

exists when p

1

= 2 since e

1

≤ 2.

Put also b := (ϕ(p

e1

1

), . . . , ϕ(p

ed

d

)). By the Chinese Remainder Theorem, each

4 P. Leonetti and C. Sanna

x(n) = (x

1

(n), . . . , x

d

(n)) ∈

J1, bK such that n ≡ g

xi(n) i

mod p

ei i

for i = 1, . . . , d.

Let a

i

= p

αi,1 1

· · · p

αi,d

d

be the prime factorization of a

i

, where α

i,1

, . . . , α

i,d

are

nonnegative integers, and define a

i

:= (ϕ(p

αi,1

1

), . . . , ϕ(p

αi,d

d

)) for i = 1, . . . , k.

At this point, it follows easily that n ∈ S if and only if x(n) ∈ X , where X is

the set in the statement of Lemma 2.1. Hence, the map n 7→ x(n) is a bijection

S → X and, as a consequence, #S = #X . Since kbk = ϕ(`), ka

i

k = ϕ(a

i

),

a

1

· · · a

k

≡ 0 mod b, and b ≡ 0 mod a

i

for i = 1, . . . , k, the desired claim follows

from Lemma 2.1 and (3.1).

The case 8 | ` is a bit more trickier since there are no primitive roots modulo

2

e

_{, for e ≥ 3 an integer. However, the previous proof still works by putting}

b := (2, 2

e1−2

_{, ϕ(p}

e2

2

), . . . , ϕ(p

ed

d

))

and

a

i

:= (2

max(0,αi,1−1)−max(0,αi,1−2)

, 2

max(0,αi,1−2)

, ϕ(p

αi,2

), . . . , ϕ(p

αi,d

))

for i = 1, . . . , k. Now each n ∈

_{J1, `K}

which is relatively prime to ` is

uniquely identified by a vector x(n) = (x

0

(n), . . . , x

d

(n)) ∈

J1, bK

such that

n ≡ (−1)

x0(n)

₅

x1(n)

_{mod 2}

e1

_{and n ≡ g}

xi(n)

i

mod p

ei

i

for i = 2, . . . , d. The rest of

the proof proceeds as before.

Acknowledgments

The authors thank the anonymous referee for carefully reading the paper.

References

[1] R. Ahlswede and L. H. Khachatrian, Density inequalities for sets of multiples, J. Number Theory 55 (1995), no. 2, 170–180.

[2] R. Ahlswede and L. H. Khachatrian, Number-theoretic correlation inequalities for Dirichlet densities, J. Number Theory 63 (1997), no. 1, 34–46.

[3] F. A. Behrend, Generalization of an inequality of Heilbronn and Rohrbach, Bull. Amer. Math. Soc. 54 (1948), 681–684.

[4] A. S. Besicovitch, On the density of certain sequences of integers, Math. Ann. 110 (1935), no. 1, 336–341.

[5] K.-L. Chung, A generalization of an inequality in the elementary theory of numbers, J. Reine Angew. Math. 183 (1941), 193–196.

[6] H. Davenport and P. Erd˝os, On sequences of positive integers, J. Indian Math. Soc. (N.S.) 15 (1951), 19–24.

[7] M. Ch.-J. de la Vall´ee Poussin, Recherches analytiques sur la th´eorie des nombres premiers, Hayez, Imprimeur de L’Acad´emie Royale de Belgique, Bruxelles, 1897. [8] P. Erd˝os, On the density of some sequences of integers, Bull. Amer. Math. Soc. 54

(1948), 685–692.

[9] R. R. Hall, Sets of multiples, Cambridge Tracts in Mathematics, vol. 118, Cambridge University Press, Cambridge, 1996.

[10] H. A. Heilbronn, On an inequality in the elementary theory of numbers, Proc. Cambridge Philos. Soc. 33 (1937), 207–209.

[11] H. Rohrbach, Beweis einer zahlentheoretischen Ungleichung, J. Reine Angew. Math. 177 (1937), 193–196.

[12] I. Z. Ruzsa, Probabilistic generalization of a number-theoretical inequality, Amer. Math. Monthly 83 (1976), no. 9, 723–725.