Primes congruent to a mod n.

Question

Is there at least one prime p that is congruent to a mod n, where n can be any positive integer and a can be any non-negative integer less than n?

Answer 1

The complete answer is given by the different comments:

If $(a,n)=1$ then there are infinite primes that satisfy the equation $p=a$ mod $n$. This is the content of the Dirichlet's theorem on arithmetic progressions. Moreover, the primes are evenly distributed (asymptotically) among the congruence classes modulo $n$ containing the $a$'s coprime to $n$.

If $(a,n)>1$, we can have to cases:

1) If $a$ is prime, then we only have the trivial solution $p=a$.

Proof: If $a$ is prime and $(a,n)>1$ then $a$ is a factor of $n$, so $n=ab$ for some positive integer $b$, so the equation can be written $p = a$ mod $ab$, meaning $p$ = $a + (ab)c$ for some integer $c$. Then $p = a(1+bc)$, but $a$ is prime, so there is only one solution, namely when $c=0$.

2) If $a$ is composite, then there are no solutions.

Proof: $p = a$ mod $n$, means $p$ = $a + nI$ for some integer $I$, let's define $J=nI$ so now $p$ = $a + J$. Now, since $a$ and $n$ are not coprime, the same applies for $a$ and $J$, so by Bézout's identity: $aA+JB=C$ where $C > 1$ is the gcd of $a$ and $J$, and $A$ and $B$ are non-zero integers. Then $p$ = $a + ((C-aA)/B)$. And since $C$ is a factor of $a$ we have $p=CD + ((C-CDA)/B)$ for some positive integer $D$. Then $p=C(1+((1-DA)/B)$. Now, because $C>1$, for $p$ to be prime we need $(1+((1-DA)/B)$ to be equal to $1$, so $(1-DA)$ needs to be zero. But we said that $D$ is a positive integer, so $A$ has to be zero. But we said that $A$ is non-zero integer, we can conclude then that $p$ cannot be prime.