This was a question asked on a homework for my number theory class but I think I'm missing something. Here is the full question.

Let $a,b \in \mathbb{Z}$. Show that if gcd($a,b$) > 1, then there can be at most one prime of the form $p = an+b$. Under what circumstances will there be exactly one prime of this form, and when will there be none?

I apologize in advance for poor formatting. I'm new to this and trying my best. Any tips would be greatly appreciated.


Let $a, b$ be integers. Suppose gcd($a,b$)>1 and that there is a prime $p$ of the form $p=an+b$. There then exists an integer $c$ where $c = gcd(a,b)$.

By definition of division, there exists integers $d,e$ such that

$$a=ce$$ $$b=cd$$

You then have $$p=an+b=c(en+d)$$

Clearly, $p$ is divisible by $c$ which is a contradiction from our original assumption that $p$ is prime. Therefore, there can be no primes of the form $p=an+b$ if $gcd(a,b)>1$.

My questions are this. Is there anything I missed in my proof? If so, can you nudge me in the right direction to be able to answer this?

  • $\begingroup$ $p$ has two divisors, $1$ and $p$, $c|p$ is not a contradiction if $c=1$ or $c=p$. $\endgroup$ – Malcolm Mar 16 '18 at 18:53
  • $\begingroup$ If $c$ = 1, then the gcd($a,b$) = 1 which is covered in the assumption. $\endgroup$ – Mike Bagnasco Mar 16 '18 at 19:25
  • $\begingroup$ But $c$ can be $p$. $\endgroup$ – Malcolm Mar 16 '18 at 19:28

What you missed in your proof is the possibility that $a$ or $b$ can be negative.

Follow the example of $a=4, b=-6, \gcd(a,b)=2, n=2, p=2\cdot 4 + (-6) = 2$ to see what went wrong. It is not a coincidence that the prime is in fact $\gcd(a,b)$.

And in fact, even when $\gcd(a,b) =p$ is prime, you can't always find the appropriate $n$, but if there is one, you know that $$an + b = p$$ $$pdn+pe = p$$ $$dn + e = 1$$ $$n = \frac{1-e}{d}$$

So if $a = pd$ and $b=pe$ (with $p$ prime) there will be a solution, which will be $an+b=p$, if and only if $$\frac{1-e}{d} \in \Bbb{N}$$


If $g=\gcd(a,b)$ and $g>1$, then $g\mid(an+b)$. So the only way $an+b$ can be prime is if $an+b=\pm g$ and $g$ itself is prime. The only possible values of $n$ are $a^{-1}(\pm g-b)$. It is possible for this to be an integer, so one can get $g$ (or $-g$ if you allow negative numbers as prime).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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