Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

Does the statement the are an infinite number of primes p, such that for any j, $1<j<a$,

$pj\equiv b$ mod a

imply dirichlets theorem? that there are an infinite number of primes p such that $p\equiv b$ mod a,

for constants b and a

share|cite|improve this question
If $a>4$, and, say, $b=a-1$, then this would mean that (for $j=2$): $2p\equiv -1\pmod a$ and (for $j=4$) $4p\equiv -1\pmod a$. Subtracting, that would mean $2p\equiv 0\pmod a$, which seems like a contradiction, so there can not be any such $p$. – Thomas Andrews Dec 18 '12 at 0:08
Can you make your statement clearer? At the moment I am not entirely sure what you are asking. – Eric Naslund Dec 18 '12 at 0:38
@ThomasAndrews, it's not a simultaneous equation, so subtracting doesn't make sense. – user27126 Dec 18 '12 at 0:38
@Ethan, you definitely need some restrictions on $j$ you consider, like $(j,a) = 1$. Second, infinitude of primes for one such $j$ is enough, since you can divide $j$ to the other side, as in the other thread you posted. – user27126 Dec 18 '12 at 0:39
Now im confused – Ethan Dec 18 '12 at 0:44
up vote 1 down vote accepted

Dirichlet's theorem: For positive integers $a,b$ with $(a,b)=1$ there exist infinitely many primes $p$ with $p\equiv b\mod a$. Your statement (or what your statement should be): For positive integers $a,b$ with $(a,b)=1$ and $1<j<a$ with $(a,j)=1$ there exist infinitely many primes $p$ such that $pj\equiv b\mod a$.

Your statement implies Dirichlet's theorem: Let $a,b$ be positive integers with $(a,b)=1$ and $a>2$. Let $1<j<a$ with $(a,j)=1$. It is clear that $(jb,a)=1$. Then apply your statement with the pair $(jb,a)$ and conclude that there exist infinitely many primes such that $pj\equiv jb\mod a$. Now $pj\equiv jb\mod a$ implies $p\equiv b\mod a$.

The case $a=2$ only says that there are infinitely many odd primes. :)

share|cite|improve this answer
Is it common to use plain parens to represent gcd? I'm so used to reading those as tuples. – Joseph Garvin Dec 18 '12 at 3:04

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.