mathematics

# Landau’s problem

Are there infinitely many primes of the form N*N+1?

Like 2,5,17,37 …

At first, we have candidates in the form of (N,N*N+1)

(1,2) (2,5) (3,10) (4,17) (5,26) (6,37) (7,50) (8,65) (9,82) (10,101) …

We check the first candidate and it is a prime. So we can transform our candidates as:

(1,2) (2,5) (3,10) (4,17) (5,26) (6,37) (7,50) (8,65) (9,82) (10,101)

Then, we can exclude from the candidates all the pairs, where the second component is congruent by module of all divisors of 2 (greater than 1!)  – to this element’s second component.

(1,2) (2,5) (3,10) (4,17) (5,26) (6,37) (7,50) (8,65) (9,82) (10,101)

At the second step, we see that (2,5) – which is (2,2*2+1) is still a candidate and therefore an actual prime. This is the lema, you don’t need to prove! So we have:

(1,2) (2,5) (3,10) (4,17) (5,26) (6,37) (7,50) (8,65) (9,82) (10,101)

Now we must eliminate all those with the first component  congruent to 2 or 3, modulo 5. Because (5*k+2)^2+1 is divisible by 5 and (5*k+3)^2+1 is divisible by 5.

(1,2) (2,5) (3,10) (4,17) (5,26) (6,37) (7,50) (8,65) (9,82) (10,101) (11,122) (12,145) (13,170)(14,197) (15,226) (16,257) …

Now we see, that 10 is NOT a candidate for prime. We still need to find all the divisors of 10 and to eliminate the appropriate numbers from this sieve. In the case of 10 there are no new divisors, and 2 and 5 have been already used. It’s nothing to do then.

But the next one 4*4+1=17 – is a prime.

There is always infinite number of candidates in this sieve. The problem is to prove, that we never stop to encounter (non-striked) candidates, from time to time.

Prove that, and you will solve this 100 years old problem!