# Prime Question

1. Mar 15, 2004

### JonF

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. Mar 15, 2004

### matt grime

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'

3. Mar 15, 2004

### JonF

6(0)+1=1
2 and 3 don't count for some reason.
6(1)-1=5
6(1)+1=7
6(2)-1=11
6(2)+1=13
6(3)-1=17
6(3)+1=19
6(4)-1=23
6(4)+1=25 but 25/5=5 (the result divided by 5 equals an integer)
6(5)-1=29
6(5)+1=31
6(6)-1=35 but 35/5=7 (the result divided by 5 equals an integer)
6(6)+1=37

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
4. Mar 15, 2004

### matt grime

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
5. Mar 15, 2004

### JonF

6. Mar 15, 2004

### matt grime

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
7. Mar 15, 2004

### JonF

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?

8. Mar 15, 2004

How about a statement along the lines "every prime except 2 and 3 is congruent to 1 or 5 mod 6?"

Edit: notation.

9. Mar 15, 2004

### JonF

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?

10. Mar 15, 2004

### matt grime

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.

11. Mar 15, 2004

### JonF

Thank you, and I appreciated your bearing with my confusing way of saying things.

12. Mar 15, 2004

### JonF

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?

13. Mar 15, 2004

### matt grime

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.

14. Mar 15, 2004

### JonF

thanks, got it now.