Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
Maybe you are looking for Dirichlet's theorem? – Dan Brumleve Mar 18 at 2:54
up vote 17 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.