A note on primes in certain residue classes

Abstract

Given positive integers \(a_1,\ldots,a_k\), we prove that the set of primes \(p\) such that \(p \not\equiv 1 \bmod{a_i}\) for \(i=1,\ldots,k\) admits asymptotic density relative to the set of all primes which is at least \(\prod_{i=1}^k \left(1-\frac{1}{\varphi(a_i)}\right)\), where \(\varphi\) is the Euler's 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 \not\equiv 0 \bmod a_i\) for \(i=1,\ldots,k\) admits asymptotic density which is at least \(\prod_{i=1}^k \left(1-\frac{1}{a_i}\right)\).