Given positive integers a1,…,ak, we prove that the set of primes p such that p≢1modai for i=1,…,k admits asymptotic density relative to the set of all primes which is at least ∏ki=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≢0modai for i=1,…,k admits asymptotic density which is at least ∏ki=1(1−1ai).