Proof that for coprime $a$ and $b$, there is a prime of the form $an+b$

Suppose , $$a$$ and $$b$$ are coprime positive integers.

Is there an easy way to show that $$an+b$$ is prime for some positive integer $$n$$ ?

Dirichlet's theorem states that there are infinite many primes of this form , but the proof of this theorem is difficult.

• Dirichlet's theorem on arithmetic progressions says that there are infinitely many such $i$'s. – José Carlos Santos May 16 at 9:49
• The proof however is anything but easy ! – Peter May 16 at 9:55
• $i$ is a bad choice here: $a+ib$ looks like a complex number. – lhf May 16 at 10:16
• I wonder whether there is a simpler proof of the existence of one prime of that form that does not rely on Dirichlet's theorem on arithmetic progressions. – lhf May 16 at 10:18
• @Ihf I do not think this is the case. Dirichlet's theorem is a simple consequence of the above statement. To see that , just use the powers of $a$ , for every $n$, there is a prime of the form $a^n+b$. – Peter May 16 at 10:49

Not unless there is an easy proof of Dirichlet's theorem.

For any $$m\in \Bbb N,$$ take $$n_1\in \Bbb N$$ where $$n_1$$ is large enough that $$(n_1b+1)a+b>m.$$ Let $$a'=(n_1b+1)a.$$

Then $$gcd(a',b)=1.$$

If $$\{n'a'+b:n'\in \Bbb N\}$$ must contain a prime $$p$$ then $$p>m$$ and $$p\in \{an+b:n\in \Bbb N\}.$$

So the set of primes in $$\{na+b:n\in \Bbb N\}$$ is not empty and has no $$m$$ as an upper bound so it must be an infinite set.

• Yeah, another way is to simply choose $an + b$ as your $b'$ if there must be at least one $n$ for which it's prime and show that you can always find one more prime that way. – sanik98 May 16 at 14:29
• Dirichlet's proof is historically important because of its use of analysis ( calculus) for a number-theoretic result. – DanielWainfleet May 17 at 21:34

Sanik : For some special choices of $$a$$, there does exist simpler proof. I'll provide examples below (mostly for record purposes):

For $$a=4,b=1$$: We claim there are infinitely many primes $$p$$ of form $$4k+1$$. To see this, suppose the contrary, and that, there are finitely many of those, denoted by $$p_1,\dots,p_n$$. Let $$N=(p_1\cdots p_n)^2+1$$. If $$q\mid N$$, then it is not hard to show $$q\equiv 1\pmod{4}$$. Thus, $$q\in\{p_1,\dots,p_n\}$$, as we have by hypothesis that there are only finitely many such numbers, a contradiction.

$$a=4,b=3$$: Again, suppose there are finitely many prime numbers of from $$4k+3$$, and let $$p_1,\dots,p_n$$ be all of them. Consider $$N=4p_1\dots p_n-1$$. Clearly, $$N>1$$, and moreover, $$N\equiv 3\pmod{4}$$. Thus, $$N$$ must necessarily have a prime divisor $$q$$. of the same form, that is, $$q\in\{p_1,\dots,p_n\}$$ and $$q\mid N$$, clearly impossible.

$$a=3,b=1$$. We now show there are infinitely many primes of form $$3k+1$$. For this, we use the fact that, if $$p>3$$ is a prime, such that $$p\mid n^2+n+1$$, then $$p\equiv 1\pmod{3}$$. To see this, note that, $$n^3\equiv 1\pmod{p}$$. Furthermore, clearly, $$(n,p)=1$$. Thus by Fermat's theorem, $$n^{p-1}\equiv. 1\pmod{p}$$. Let $$k$$ be the. smallest positive integer for which $$n^k\equiv 1 \pmod{p}$$. Then it is easy to show that $$d\mid 3$$, and $$d\mid p-1$$. Now, since $$d\neq 1$$ as $$p>3$$, we have $$d=3$$, and therefore, $$3\mid p-1$$. Now, turning back to our original claim, let there be only finitely many primes $$p_1,\dots,p_n$$ of form $$3k+1$$. Consider $$N=3p_1\cdots p_n$$ and $$N'=N^2+N+1$$. Take a $$p\mid N'$$. Clearly, $$p>3$$. Hence, $$p\equiv 1\pmod{3}$$, and thus, $$p\in\{p_1,\dots,p_n\}$$. However, this implies $$p\mid N$$, which, in turn, implies together with $$p\mid N'$$ that $$p\mid 1$$, contradiction.

It is not realistic to expect such a proof in the general case since that implies the infinitude of primes in Dirichlet's theorem, as DanielWainfleet explains in another answer.

An analogue for the Bateman–Horn conjecture (existence of at least one prime value in general implies existence of infinitely many prime values) is also true. Look here.