Show that if $\gcd(a,b) > 1$, then there can be at most one prime of the form $p = an+b$.

Question

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.

Proof

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?

Answer 1

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}$$

Answer 2

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).