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!

Prime Question

  1. Mar 15, 2004 #1
    I was told that all prime numbers (except 2 and 3) could be expressed as 6n +- 1 as long as the result divided by 5 is not another integer.

    Is this true? Is there a proof for this (hopefully if possible not going much beyond basic calc, I am only in calc 1).
  2. jcsd
  3. Mar 15, 2004 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Try writing down the first prime after 2,3,5,7, and the third prime after 7, and, oh, many others. Although I@m not sure what you mean when you refer to 'result'
  4. Mar 15, 2004 #3
    2 and 3 don't count for some reason.
    6(4)+1=25 but 25/5=5 (the result divided by 5 equals an integer)
    6(6)-1=35 but 35/5=7 (the result divided by 5 equals an integer)

    I couldn’t think of any primes between 1-37 not in that list, so it appeared at my first glance that:
    Where n is an integer if (6n+-1)/5=non integer, then n is prime.

    I have no idea how to look into this more than picking random primes I know of and seeing if they can be expressed that way…
    Last edited: Mar 15, 2004
  5. Mar 15, 2004 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Ah! On my fonts it looks like 6n+1, not, as I now see in your examples, 6n+/-1.

    Ok, ever number is of the form 6n, 6n+1, 6n+2, 6n+3 6n+4, or 6n+5 for some n. As long as n is bigger than 1 (or we get the degenerate cases of 2, 3 and 5) all but 6n+1 and 6n+5 (ie 6m-1) are divisible by 2 or 3 and cannot be prime.
    Last edited: Mar 15, 2004
  6. Mar 15, 2004 #5
    Um it maybe me, but I have no clue what that post means… please help?
  7. Mar 15, 2004 #6

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    The result you asked states: if p is a prime not equal to 2 or 3 (or 5), it can be written as p=6n+/-1 for some n in N.

    Firstly, this does not state anything about whether n is prime or not, nor does it state every number of the form 6n+/-1 is prime.

    Let p be any number greater than or equal to 7, then write p as 6n+r, where r is one of 0,1,2,3,4,5. n is at least 1. This can be done, and you were doing it all the time until you learned about fractions and decimals which are just evil.

    6n+2 = 2(3n+1) so nothing of this form can be prime

    6n+3 = 3(2n+1) so nothing like that can be prime

    6n+4 =2(3n+2) so that can't be prime

    obviously numbers of the form 6n aren't prime as they're divisible by 6.

    so the only chance p has of being prime is if it is 6n+1 or 6n+5. 6n+5 = 6(n+1)-1.

    Not every number of this form is prime:

    121 is divisible by 11 and is of the form 6*20+1

    I stil don't know what the 'result' and divisible by 5 means.
    Last edited: Mar 15, 2004
  8. Mar 15, 2004 #7
    The result I’m talking about is 6n+/-1

    What I do not get about what you are doing is why are you increasing the +/-1? The +/-1 is a constant. And in a pervious post you had an M variable what is that for?

    You answered half my question though, everything that satisfies if 6n+-1/5 =non integer then it isn’t necessary prime.

    But can call prime numbers be express as 6n+/-1?
  9. Mar 15, 2004 #8
    How about a statement along the lines "every prime except 2 and 3 is congruent to 1 or 5 mod 6?"

    Edit: notation.

  10. Mar 15, 2004 #9
    I think I got the mix up now, I’m not very good at all this math terminology, please forgive me.

    N isn’t the prime number. I was told that all primes can be expressed as: P=6n+/-1. Where p is the prime, and n can be any integer.

    My question is: Is this true? And if it is, is there a proof for it?
  11. Mar 15, 2004 #10

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    You wanted to know if every prime except for 2 or 3 is expressible as 6n+/-1. By considering all possible expressions of 6n+r, I showed that the only ones where the number 6n+r is prime is for r equal to 1 or 5 (with the exception of those small cases). Thus as every number is expressible as 6n+r for r equal to 0,1,2,3,4,5, then the only possibility for a prime is 1 or 5.

    The m is n+1, because then 6n+5=6m-1 and it is in the form you wanted originally.

    In short I proved exactly what the result you gave states, that every number that is prime (and not 2 or 3) is of the form 6n+/1 for some n.
  12. Mar 15, 2004 #11
    Thank you, and I appreciated your bearing with my confusing way of saying things.
  13. Mar 15, 2004 #12
    Re looking over things I see that you proved 6n+1 or 6n+5 are the only possible 6n+something combinations (except for the ones that are just adding multiples of 6) that can be prime? But is there any way to prove that 6n+-1 is a way that all primes can be expressed?
  14. Mar 15, 2004 #13

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Yes. The reason appeared earlier in the middle of a paragraph; here it is on its own.

    Let p be *any* number. Then there is a unique n with p=6n+r where r is one of 0,1,2,3,4,5 and also unique. Any number on division by 6 has a remainder one of those numbers. n is the largest number such that 6n is less than or equal to p. Now if p is also a prime number (not 2 or 3), then we showed that the remainder can't be one of 2,3,4 or 0. So it must be that for any prime there is some n with p=6n+1 or 6n+5 = 6(n+1)-1. And is of the form you wanted.
  15. Mar 15, 2004 #14
    thanks, got it now.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook