# 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)

**Answer**

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.