# Problem with prime and composite numbers

1. Sep 11, 2010

### canningdevin

If p >= 5 is prime, prove that p^2 + 2 is composite.

So i noticed if we divide any p >= 5 by 6 we only get remainders of 1 or 5.

6 | 5 , r = 5
6 | 7 , r = 1
6 | 11, r = 5
6 | 13, r = 1
6 | 17, r = 5 and so on

so for my proof i am saying for p >= 5, p = 6k + 1 or 6k = 5

so for the first , p^2 + 2 = (6k+1)^2 + 2 = 36k^2 +12k + 3 = 3(12k^2 + 4k + 1)

and similarly, p^2 + 2 = (6k+5)^2 + 2 = 36k^2 + 60k + 27 = 3(12k^2 + 20k + 3)

so both of these are composite so that is great.

But is there a way i can justify that any prime p >= 5 can be written as 6k + 1 or 6k + 5?

I mean i can go through a ton of examples and the remainders are only 1 or 5 but examples don't mean anything.

Can someone help me justify that first step.

Last edited: Sep 11, 2010
2. Sep 11, 2010

### canningdevin

I just thought of something can someone tell me if this is correct. for p primes p >=5 we can only get remainders 1 or 5 when dividing by 6 because if we get 2 3 4 we see what happens

6k + 2 = 2(3k +1)
6k + 3 = 3(2k +1)
6k + 4 = 2(2k + 2) and none of these can be prime because they have factors of either 2 or 3.
Is this correct?

3. Sep 11, 2010

### jgens

Clearly, every prime number greater than 5 can be written in the form 3k+1 or 3k+2. Then all that you need to demonstrate is that (3k+1)2+2 and (3k+2)2+2 are composite. This is similar to your line of thinking.

4. Sep 11, 2010

### canningdevin

ah ok, thank you very much