Are There Infinitely Many Prime Numbers Written as ak+b?

[geoffrey159]

Homework Statement

Prove that there are infinitely many prime numbers written $ak+b$, with $a,b,k$ integers greater than 1

Homework Equations

The Attempt at a Solution

Please could you tell me if you agree with that proof ?

By contradiction:
Assume that there is an integer $k$ such that $ak+b$ is the greatest prime number of that sort. Then for any $n > k$, there are $(u,v)\in \mathbb{N}^\star$ such that $an+b = uv$. Take $n = k + u$, therefore $ak + b = u (v-a)$, which contradicts the fact that $ak+b$ is prime.

 

[micromass]

Now you basically "proved" that any $an+b$ where $n>k$is prime.

 

[geoffrey159]

Oh ok I see my mistake, I can't chose $n$ once $u$ is set. Thank you, I'll try something else

 

[geoffrey159]

I haven't made much progress on this one...
I can show that there are infinitely many primes written $ak + 1$, $a$ even. If you assume that $ak_0 + 1$ is the greatest prime, then $N = a (ak_0+1)! + 1$ is compound and has a prime divisor $p$ that must be less than $a (ak_0 + 1)!$. In that case, $p$ divides $N$ and $a(ak_0+1)!$, so it divides 1. contradiction.

 

[micromass]

Why must $p$ divide $a(ak_0+1)$?

 

[geoffrey159]

if $p$ is less than $a(ak_0+1)!$ it divides it

 

[geoffrey159]

Oh no it doesn't work !
I don't know, this problem is too hard for me

 

[micromass]

I don't know, this problem is too hard for me

The proof usually requires some fairly difficult analytic number theory. (And the result is only true if $\text{gcd}(a,b)=1$).

 

[geoffrey159]

Thank you for the info.
The one line problem statement looked harmless at first, but I literally lost my time with this problem ;-)

 

[geoffrey159]

I haven't made much progress on this one...
I can show that there are infinitely many primes written $ak + 1$, $a$ even. If you assume that $ak_0 + 1$ is the greatest prime, then $N = a (ak_0+1)! + 1$ is compound and has a prime divisor $p$ that must be less than $a (ak_0 + 1)!$. In that case, $p$ divides $N$ and $a(ak_0+1)!$, so it divides 1. contradiction.

@micromass:
I'm sorry to bother you again, but I think the same idea would work just fine with $N = (ak_0 +1)! +1$, because one can factorize $a$ out of the factorial so that N belongs to the set $\{ ak+1 , k\ge 1 \}$. Right ?

 

[micromass]

OK, $N$ is of the form $ak+1$. So how does that prove anything?

 

[geoffrey159]

If you assume that $ak_0 +1$ is the greatest prime of the form $ak+1$, then $N$ which also has the form $ak+1$ and is greater than $ak_0 + 1$ must be compound. So there is a prime number $p$ that divides $N$ and that is not equal to $N$.
But we must have $p \le N-1 = (ak_0 +1)!$. In that case $p$ is a factor in $(ak_0 +1)!$, so that it divides it. But $p | N$ and $p| (ak_0+1)!$ implies that $p | 1$, which is impossible for a prime number. Therefore $N$ is prime and there are infinitely many primes of the form $ak+1$

 

[micromass]

Why would $p$ be a factor in $(ak_0 +1)!$

 

[geoffrey159]

Because it is smaller than it

 

[micromass]

$5$ is smaller than $3!$ and doesn't divide it.

 

[geoffrey159]

OOOOOOOOOK, I get it :-)

 

[geoffrey159]

@micromass
I was completely wrong, $N$ and $(ak_0 +1)!$ are relatively prime (Bezout), and $p | N$ so $p$ and $(ak_0+1)!$ are relatively prime. Which is the same as saying that $p$ does not divide $(ak_0+1)!$