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

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.