# Prime number question

Question

1) Show that if p >=5 is a prime number, then p^2 + 2 is composite (hint: p takes one of the forms 6k+1 or 6k + 5 (why?))

2) Give another proof of the infinitude of primes by assuming that there are only finitely many primes, say p_1, p_2, …, p_n, and using the following integer to arrive at a contradiction:
N = p2*p3 *..*pn + p1*p3*…*pn + … + p1*p2* …*p(n-1)

1) Firstly consider any integer divided by 6, we must get one of the residues ( remainders ), r = 0,1,2,3,4,5. If the remainder of y divided by 6 is r, thus we can write
y = 6 x “quotient” + “remainder” = 6k + r, where let k denote the value of the quotient. Since r = 0,1,2,3,4,5, we have just shown that any integer y ( we may assume positive ), can be written in one of the “forms”
y = 6k , 6k + 1, 6k + 2, 6k + 3, 6k + 4, 6k + 5.

Now among these, the ones that are composite ( NOT prime )
for any integer k, are
6k , Even
6k + 2, Even
6k + 3 = 3(2k + 1) , a multiple of 3.
6k + 4, Even

Remembering that the only even prime number is 2.
Thus, the only possibilities for forms for primes in here is either 6k+1 or 6k + 5 . All other forms denotes a composite integer. Remember that a composite integer is an integer with at least two distinct prime factors.

If p is form 6k+1, Let p = 6k+1,
Thus, p^2 + 2 = ( 6k + 1 )^2 + 2
= 36k^2 + 12k + 3
= 3 ( 12k^2 + 4k + 1 )
= A multiple of 3 > 3
= A Composite number.

If p is form 6k+5, Let p = 6k+5,
Thus, p^2 + 2 = ( 6k + 5 )^2 + 2
= 36k^2 + 60k + 27
= 3 ( 12k^2 + 20k + 9 )
= A multiple of 3 > 3
= A Composite number.

Thus, in both cases, if p is prime then p^2 + 2 is always composite.

2)
Assume that the number of primes are finite.
Now the integer N is NOT divisible by any of the primes in the list p_1, p_2, …, p_n.
Why? because say p_k divides N. Then, p_k must divide the following integer : p_1*…*p_n where it does NOT contain p_k. Which is a contradiction .
Thus, primes must be infinite for if not, they produce the contradiction shown above.