If more than one prime number satisfies a given congruence, must an infinite number of primes satisfy that congruence?

Question

I understand that this is kind of a broad question, but if no affirmative proof is known, can anyone give a counterexample?

Answer 1

If you're talking about linear congruences of the form $x \equiv a \bmod b$, then the answer is yes.

The key point is that $\gcd(a,b)$ divides every solution $x$. Thus:

• If $\gcd(a,b)=1$, then there are an infinite number of prime solutions. This is the famous Dirichlet's theorem on arithmetic progressions.

• If $\gcd(a,b)$ is composite, then there are no prime solutions.

• If $\gcd(a,b)=p$, then there is at most one prime solution, $x=p$. (In fact, there is a prime solution iff $\frac ap \equiv 1 \bmod \frac bp$, but this is not relevant.)

Therefore, the only case when there is more than one prime solution is the first case, in which there are an infinite number of prime solutions.