The least prime in certain arithmetic progressions

Abstract

Dirichlet’s theorem states that, if a and n are relatively prime integers, there are infinitely many primes in the arithmetic progression n + a, 2n + a, 3n + a,.... However, the known proofs of this general result are not elementary (see [1, 10, 12], for example). Linnik [4, 5] proved that, if 1 ≤ a < n, there are absolute constants c1 and c2 so that the least prime p in such a progression satisfies p ≤ c1nc2 , but his proof is not elementary either. There are several different proofs of Dirichlet’s theorem for the particular case a = 1 (see for example [2, 6, 9, 11]). In [7], moreover, the bound p < n3n for the least prime satisfying p ≡ 1 (mod n) is given. Our aim is to use an elementary argument, which also shows that there are infinitely many primes ≡ 1 (mod n), to prove that the least such prime lies below (3n − 1)/2.