Elementary number theory - prove the following statements

1. May 25, 2014

Amcote

This is my first time posting anything on the forum so I apologize if I do anything wrong. I have enrolled myself into elementary number theory thinking we would be taught how to do proofs however it is apparently expected that we already know how to do this. And so since I am a beginner at this, it would be very nice for someone to point out whether I'm doing/presenting the problems incorrectly or inefficiently.

Prove the following statements:

1) If p≥5 is a prime number, then p$^{2}$+2 is a composite number.

Attempt:

I know that any prime number p>3 will have the form of either 6k+1 or 6k-1, and so I am able to put 6k-1 into the equation

(6k-1)$^{2}$+2

36k$^{2}$-12k+1+2

3(12k$^{2}$-4k+1).

Similarly I substitute 6k+1 into the same equation with the result

3(12k$^{2}$+4n+1)

thus showing that p$^{2}$+2 is indeed a composite number.

2)
If a and 8a-1 are prime, then 8a+1 is composite.

Attempt:

I have been stuck on this one as I'm not really sure where to begin. The one thing I can think of doing is starting with a counter example.

Suppose a and 8a-1 are composite, this tells me (I think) that there is d|a such that 1<d<a and also c|8a-1 such that 1<c<8a-1, this is about as far as I have come and I'm not really sure how to proceed.

Any sort of help or hints would be great.

Thanks!

2. May 25, 2014

AlephZero

Your logic in part 1 is fine. The presentation could be a bit shorter, for example

Any prime number p>3 will have the form of either 6k+1 or 6k-1.

If p = 6k-1, then
p2+2 = (6k-1)2+2
...
= 3(12k2-4k+1)
so p+2 is conposite.

Similarly if p = 6k+1 ,
p2+2 = 3(12k2+4n+1)
which is composite.

For part 2, try the same idea again. Let a = 6k+1 or 6k-1, and see what you get for 8a+1 and 8a-1

3. May 25, 2014

Amcote

Thank you for your quick response,

If a is prime, it will have the form either 6k+1 or 6k-1 so,

8(6k-1)-1 should be prime as well but,
48k-8-1=48k-9=3(16k-3) this is composite so the form 6k-1 does not work.

but

8(6k+1)-1=48k+8-1=48k+7 is it sufficient to say that 48k+7 is not composite?

If it is, then 6k+1 is an acceptable form so,

8(6k+1)+1=48k+9=3(6k+3) which is composite and is what we were trying to prove.

I feel like I've over assumed something during this proof.

4. May 25, 2014

AlephZero

That proof is OK.

You know a = 6k-1 or 6k+1.
You showed a can't= 6k-1 because 8a-1 is composite.
So a = 6k+1.
You then showed if a = 6k+1, 8a+1 is always composite.
So if a = 6k+1 and also 8a-1 is prime, 8a+1 is always composite.
Of course for some primes of the form a = 6k+1, both 8a-1 and 8a+1 are composite, but that doesn't make your proof wrong. The theorem doesn't say anything about primes when 8a-1 is composite.

You forgot one small thing. In part one you said (correctly) that any prime > 3 is of the form 6k-1 or 6k+1. So you also have to show the theorem is true if a = 2 or a = 3, by just doing the arithmetic.

5. May 25, 2014

Amcote

Thank you very much for your help, it's much appreciated. (: