1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Elementary number theory - prove the following statements

  1. May 25, 2014 #1
    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[itex]^{2}[/itex]+2 is a composite number.


    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




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


    thus showing that p[itex]^{2}[/itex]+2 is indeed a composite number.

    Have I gone about this the right way?

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


    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.

  2. jcsd
  3. May 25, 2014 #2


    User Avatar
    Science Advisor
    Homework Helper

    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
  4. May 25, 2014 #3
    Thank you for your quick response,

    Now using your idea:

    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.


    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.
  5. May 25, 2014 #4


    User Avatar
    Science Advisor
    Homework Helper

    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.
  6. May 25, 2014 #5
    Thank you very much for your help, it's much appreciated. (:
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted