1. May 23, 2015

geoffrey159

1. The problem statement, all variables and given/known data
Prove that there are infinitely many prime numbers written $ak+b$, with $a,b,k$ integers greater than 1

2. Relevant equations

3. The attempt at a solution

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

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.

2. May 23, 2015

micromass

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

3. May 23, 2015

geoffrey159

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

4. May 23, 2015

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.

5. May 23, 2015

micromass

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

6. May 23, 2015

geoffrey159

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

7. May 23, 2015

geoffrey159

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

8. May 23, 2015

micromass

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

9. May 23, 2015

geoffrey159

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

10. May 24, 2015

geoffrey159

@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 ?

11. May 24, 2015

micromass

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

12. May 24, 2015

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$

13. May 24, 2015

micromass

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

14. May 24, 2015

geoffrey159

Because it is smaller than it

15. May 24, 2015

micromass

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

16. May 24, 2015

geoffrey159

OOOOOOOOOK, I get it :-)

17. May 24, 2015

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)!$