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