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

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

-
Maybe you are looking for Dirichlet's theorem? – Dan Brumleve Mar 18 at 2:54

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.

-
Ahh, thank you! I can't believe the answer is yes. – Vik78 Mar 18 at 2:55
Another way of phrasing the argument: Let $p_1, p_2$ be two primes satisfying the congruence. Then $\gcd(a,b)$ divides $p_1$ and it divides $p_2$; therefore it divides $\gcd(p_1, p_2)$. But this is always 1, so $\gcd(a,b)=1$ and Dirichlet's theorem applies. – Steven Stadnicki Mar 18 at 4:34
@StevenStadnicki, yes indeed, thanks! I just thought I'd consider all cases. – lhf Mar 18 at 10:35