Question

Recall that the primes fall into three categories: Let Pi be the set of

primes congruent to 1 (mod 4) and P3 be the set of primes congruent to
3 (mod 4). We know that
{primes} = {2} UP, UP3.
We have previously proved that P3 is infinite. This problem completes
the story and proves that P1 is infinite. You can do this by following these
steps:
A) Fix n > 1 and define N = (n!)2 + 1. Let p be the smallest prime divisor
of N. Show p>n.
B) If p is as in part (a), show that p ⌘ 1 (mod 4). (To get started, note
that (n!)2 ⌘ 1(mod p), raise both sides to the power p1 2 and go from
there. You will need Fermat’s Theorem)
C) Produce an infinite increasing sequence of primes in P1, showing P1
is infinite.

Answer 1

Check the explanation

Explanation:

(a)Let p be the smallest prime divisor of (n!)^2+1 if p<=n then p|n! Hence p can not divide (n!)^2+1. Hence p>n

(b) (n!)^2=-1 mod p now by format theorem (n!)^(p-1)= 1 mod p ( as p doesn't divide (n!)^2)

Hence (-1)^(p-1)/2= 1 mod p hence [ as p-1/2 is an integer] and hence( p-1)/2 is even number hence p is of the form 4k+1

(C) now let p be the largest prime of the form 4k+1 consider x= (p!)^2+1 . Let q be the smallest prime dividing x . By the previous exercises q> p and q is also of the form 4k+1 hence contradiction. Hence P_1 is infinite