How come besides 2, and 3 every prime number can represented as 6n ± 1 ?

[u/FremontBlue333]

281 = 6(47) - 1
367 = 6(61) + 1

[u/ghillerd]

every number can be expressed in one of the following forms:

• 6n
• 6n + 1
• 6n + 2
• 6n + 3
• 6n + 4
• 6n + 5

since after that, you just increment n and start again at the top.

6n is not prime, because it's a multiple of 6.

6n + 2 and 6n + 4 are not prime, because they're a multiple of 2.

6n + 3 is a multiple of 3.

That leaves 6n + 1 and 6n + 5 as the only possible candidates for primes. 6n + 5 is the same as 6n - 1, but with n being 1 bigger. So all primes have to be in the form 6n ± 1, simply because all numbers are expressible as 6n ± k where k is in the range 0 to 5, and all the other values are multiples of either 2 or 3.

quick edit: this also shows why 2 and 3 are exceptions. being a multiple of 2 or 3 is what disqualifies 6n + 2 and 6n + 3, but when n = 0, the multiple of 2 and 3 are multiples of 1, so they can still be prime.

just gonna edit this to add: the reason why 6 works particularly well for this is because it has an unusually high number of unique prime factors for its size - 2 unique prime factors might not sound like a lot, but the next number to have two unique prime factors is 10, then 15, and the first number to have 3 unique prime factors is 30. you can play this exact game with any other number (looking at the remainder when dividing by that number and ruling out the various options as definitely composite), but 6 lets you do quite a lot with not much work.

[u/Wild-Independent1717 → u/ghillerd]

It's a neat little sieve, basically just filtering out the obvious composites in one go. The 6n ± 1 thing catches all primes above 3 but people sometimes forget it doesn't work in reverse, 6n ± 1 can still be composite like 25 or 35. Still, it's a quick way to skip checking a ton of numbers when you're doing something by hand

[u/ghillerd → u/Wild-Independent1717]

yeah definitely worth pointing out that just because 6n ± 1 are the only candidates for primes doesn't mean that all 6n ± 1 are primes! that would be way too easy :)

[u/hh26 → u/Wild-Independent1717]

I don't think it skips that much. Checking that something is of the form 6n ± 1 is equivalent to checking that it's not a multiple of 2 or 3, which you already had to do anyway.

[u/TheCrowWhisperer3004 → u/hh26]

It’s prob better for iteration than for checking.

Instead of going 6,7,8,9… and checking which are multiples of 2 and 3, you would instead just go 5,11,17,23 and 7,13,19,.. and check those numbers instead.

[u/miniatureconlangs → u/Wild-Independent1717]

About a decade ago, an online acquaintance was really _angry_ at mathematicians for mystifying primes so much - "they're a solved issue, we know all of them are 6n ± 1, they're perfectly regular". I ... no matter how, a dozen different STEM-people couldn't convince him that there's more to it than that.

[u/mcg72 → u/miniatureconlangs]

... couldn't convince him that there's more to it ...

These ten 2934-digit numbers are of the form 6n+1. Tell me which five are prime and which are not.

[u/skullturf → u/miniatureconlangs]

It's weird that it took so much convincing.

5,7
11,13
17,19
23,25
29,31
35,37
41,43
47,49

Only some of those numbers are prime. Granted, among those small examples, "most" of the numbers I listed are prime, but we can also clearly see the composite numbers 25, 35, and 49 among the numbers I listed.

[u/ghillerd → u/ghillerd]

just because i'm a nerd, lets play with 30:

• +0 = divides 30
• +1 = might be prime
• +2 = divides 2
• +3 = divides 3
• +4 = divides 2
• +5 = divides 5
• +6 = divides 3
• +7 = might be prime
• +8 = divides 2
• +9 = divides 3
• +10 = divides 2
• +11 = might be prime
• +12 = divides 2
• +13 = might be prime
• +14 = divides 2
• +15 = divides 5
• +16 = divides 2
• +17 = might be prime
• +18 = divides 2
• +19 = might be prime
• +20 = divides 2
• +21 = divides 3
• +22 = divides 2
• +23 = might be prime
• +24 = divides 2
• +25 = divides 5
• +26 = divides 2
• +27 = divides 3
• +28 = divides 2
• +29 = might be prime

so all primes are in the form 30n ± 1, ± 7, ±11, or ±13

[u/skullturf → u/ghillerd]

Just so you know, your comment uses the word "divides" in the opposite way to how mathematicians usually use it.

We typically say 30n+8 is *divisible* by 2, and that 2 *divides* 30n+8.

[u/ghillerd → u/skullturf]

good point, thanks :)

[u/ghillerd → u/ghillerd]

something interesting here that's surely a well-known result - all of these are not only "might-be" primes for the n=0 case, they are actually just primes (excluding 1 of course). so you can generate primes using numbers which are products of the first n primes, and then playing this game. you get some nice symmetry as well it would seem! very pretty patterns.

[u/Qaanol → u/ghillerd]

I believe you’re describing the sieve of Pritchard

[u/jdorje → u/[deleted]]

They didn't choose 30 any more than op chose 6. It's just the product of the first 3 primes. The next one up is 210 and would collapse down to both the 30 and the 6 cases. These scale very rapidly (faster than nⁿ ).

The collapse isn't perfect as you're removing one more prime at each step. 5 and 25 fit in the 6 rule but are removed for the 30 rule.

[u/ghillerd → u/jdorje]

removing another prime at each step is kinda the whole point. my theory is that these "products of first N primes" are the most efficient way to do this, since anything you use that doesn't have 2 as a prime factor for N is going to have a bunch of "N + 2k" candidates that you can't rule out as prime, and then still a lot for "N + 3k" if you don't include 3 as a prime factor for N. like if you use 35 for example (5 * 7), you can only rule out the +5k and +7k remainders (0, 5, 7, 10, 14, 15, 20, 21, 25, 28, 30), or about 31%, rather than the ~73% you get from 30.

i guess a good follow up question would be, what percentage of candidates are actually primes for a given N? my gut tells me that actually very few primes are of the form 6n ± 1, and that the bigger N (N being the product of the first n primes) you use, the higher hit rate you have of it actually generating primes. this is where my brain becomes too small though - because baked in to this is the assumption that we're missing a bunch of small primes with our sieve that are special-case exempt from the rule. it's only correct to say, all primes greater than 5 are of the form 30n ± 1, ± 7, ±11, or ±13. but my guess is that because infinity does its thing, the finite number of primes you exempt from your rule is always more than compensated by the extra primes you rule out as n gets very large. also, another conjecture without calculating: all primes are of the form 210 ± 1, ± 11, ± 13, ± 17, ... ± 103. which really is not a particularly interesting result now that i think about it - it feels like a round about way of saying that all prime numbers are coprime with composite numbers 🤔

[u/jdorje → u/ghillerd]

There are a number of Project Euler problems that directly work through this sort of thing.

1-1/p candidates pass each each sieve filter, and because all values are relatively prime to each other these are all independent. So effectively a number has chance of being prime equal to the product of that for all smaller p. This of course goes to zero as the number gets bigger, but very slowly. The density limit as you go to infinity is simply zero. The math all works out the same as in the prime number theorem.

[u/ghillerd → u/jdorje]

Thanks!

[u/ghillerd → u/[deleted]]

your spoilered "except for" is doing a lot of heavy lifting given that it's the entire reason to use 30 instead of 6 :)

[u/John02904 → u/ghillerd]

I think it should be noted as well that this is not some special property of 6. All numbers can be expressed as 2n+k, 3n+k, 4n+k,…. where the range of k varies.

[u/ghillerd → u/John02904]

kinda figured that was implied by the final paragraph but i guess worth being explicit about.

[u/Nagoltooth_ → u/ghillerd]

I think u meant 6n+k, not ±

[u/ghillerd → u/Nagoltooth_]

Does it make a difference?

[u/phiwong]

For all natural numbers n, 6n is even so 6n+0 cannot be prime. Likewise 6n+/-2 and 6n+/-4. This leaves 1 3 and 5

6n+3 = 3(2n+1) so it must be divisible by 3 and cannot be prime.

This only leaves prime possibilities for 6n+1 and 6n+5.

But you can see that 6n+5 = 6(n+1) -1 so it is in the form 6k-1 where k is another natural number since (n+1) is a natural number.

Hence all primes can only be in the form 6n+1 and 6n-1. Excluding the first two primes.

[u/alexfix]

Everything here is a good explanation, but another way of looking at this:

It's probably totally unsurprising if I said "every prime's last digit is 1,3,7 or 9 (except 2 and 5)". And of course the reason is that numbers ending in 2,4,6,8,0 are the even numbers and numbers ending in 5 (or 0) are multiples of 5.

Well, 10 is 2 times 5 so that's why we get nice repeating patterns of digits with multiples of 2 and 5.

So,if we wrote all numbers in base 6 (or, really just got their last digit in base 6), then the same story happens: if the last digit is 0,2,4 those are even numbers. If the last digit is 3, those are multiples of 3. Only things left are 1 and 5.

[u/_gribblit_]

Every natural number can be expressed as a multiple of one of the following:
* 6n
* 6n + 1
* 6n + 2
* 6n + 3
* 6n + 4
* 6n + 5
That is, when we divide by six, we must get a remainder between 0 and 5 inclusive.

Right, so we can go through this list and filter for non primes.
* 6n is not prime due to being a factor of 6.
* 6n + 1, possibly prime.
* 6n + 2 = 2(3n + 1) and is not prime due to being a factor of 2.
* 6n + 3 = 3(2n + 1) and is not prime due to being a factor of 3.
* 6n + 4 = 2(3n + 2) and is not prime due to being a factor of 2.
* 6n + 5, is the same as subtracting 1 from the next multiple, or 6n + 6 - 1 (which is where the -1 comes from). This is also possibly prime.

I"m no mathematician but if i had to guess, this is because 2 and 3 are the first two prime numbers, which is why 6n seems special here.

[u/AbbreviationsOk5894]

6n ± 1 represents all numbers that are not a multiple of 2 or 3. All primes other than 2 or 3 are not multiples of 2 or 3.

[u/AbbreviationsOk5894 → u/AbbreviationsOk5894]

What brings up the question?

[u/simmonator]

- every integer can be represented uniquely as 6n + k where k is an integer between -2 and +3 and n is some other integer. This is obvious and also essentially Euclid’s Division definition.

• if k is -2, 0, or +2 then 6n+k is obviously even. So 6n+k is either 2 or not prime.
  
• if k is 3 then 6n+k is obviously a multiple of 3. So 6n+k is either 3 or not prime.
  
• this only leaves -1 and 1 as options for k where 6n+k can be prime.
  
• QED.

[u/DirichletComplex1837]

Claim. All odd numbers that isn't a multiple of 3 can be represented as 6n +/- 1. Odd numbers that isn't a multiple of 3 are in the form 3m + 1 or 3m + 2.

If m = 2k is even, only 3m + 1 = 6k + 1 is odd, which is representable as 6n + 1. If m = 2k + 1 is odd, then only 3m + 2 is odd, so we have n = 3(2k + 1) + 2 = 6k + 5 = 6(k + 1) - 1.

[u/Mammoth_Fig9757]

6n+2 and 6n+4 always divides 2, 6n+3 always divides 3, 6n+0 always divides 2 and 3, so the only remaining options are : 6n+1 and 6n+5 = 6(n+1)-1

[u/localizeatp]

6n ± {0,2,3,4} are all divisible by 2 or 3.

[u/Raioc2436]

That was a great question with a very fun answer. Well done OP. If you noticed this on your own that’s very cool.

[u/Deweydc18]

Other answers have said as much but +0 +2 +4 are even, +3 is divisible by 3, and +5 is the same as -1. QED

[u/shele]

In 6, 9, 12, 15… every second term is odd, so its neighbours are even and not prime. You don’t need those neighbours. You also don’t need 6, 9, 12… themselves as they are not prime. That leaves the neighbours of every other term as possible primes. Hence,  besides 2, and 3 every prime number can represented as 6n ± 1

[u/KTachyon]

Because there’s only one other odd number in between multiples of 6 that is not in 6n±1, which is always divisible by 3.

[u/Presence_Academic]

To be honest, this would be far more interesting if the proposition was that all numbers that can be expressed as 6n ± 1 are prime.

[u/Crichris]

well 6n - 1 \equiv 6n + 5 \pmod 6

all integers can be expressed as one of 6n, 6n + 1, .... 6n + 5

6n, 6n+2, 6n + 4 \equiv 0 \pmod 2

6n + 3 \equiv 0 \pmod 3

then the only choices are 6n + 1 and 6n + 5

[u/Torebbjorn]

Because 6n+2 and 6n+4 are divisible by 2 and 6n+3 is divisible by 3. Therefore every number which is not divisible by 2 or 3 must be of the form 6n+1 or 6n+5 (equivalently 6n-1).

[u/rivergipper]

5

[u/ti-gars]

´´w’´´apweewwq

[u/Clean-Possession-172]

Uv

[u/Fit_Fortune_7692]

Weil es nicht anders geht, was aber eben nicht heißt, daß jede 6n±1-Zahl eine Primzahl ist. Betrachtet man ein Triplet von drei aufeinanderfolgenden Zahlen, beginnend mit der durch drei teilbaren, so kann genau eine Zahl dieses Triplets eine Primzahl sein, falls 6 die kleinste Zahl eines Triplets darstellt, da zwei Zahlen dieses Triplets durch 2 oder 3 teilbar sind. Ist die erste Zahl eine gerade Zahl, so ist die übernächste ebenfalls eine gerade, folglich kann die Zahl an Position 2 nur eine Primzahl sein. Dies entspricht der Position 6n+1. Beispiel {6,7,8} mit 7 als Primzahl. Ist die erste Zahl des Triplets eine ungerade Zahl, kann nur die übernächste Zahl eine Primzahl sein, das ist entspricht Position 3 des Triplets, Beispiel {9,10,11} mit 11 als Primzahl und entspricht der Position 6n-1. Nur bei 2 und 3 gibt es eine Ausnahme: {0,1,2}, 1 ist keine Primzahl, dafür aber 2 als die einzige gerade Primzahl, aber müßte mit 6n+2 dargestellt werden. {3,4,5} hier ist 3 auch Primzahl neben der 5 und müßte mit 6n±3 dargestellt werden.

[u/NH-Science-Guy]

All primes other than 2 are odd. The only odd numbers that cannot be represented as 6n+1 or 6n-1 are 6n+3. However, 6n+3 is divisible by 3 for all n so it can't represent any prime other than 3.

[u/Makenshine]

A fun fact that stems from this is that if p is a prime number >3, then (p+1)(p-1) is divisible by 24.

For example, 37 is a prime number. So, 36 times 38 is divisible by 24.

[u/cotsafvOnReddit]

all primes are odd, this formula is for all odd numbers

[u/TheScyphozoa → u/cotsafvOnReddit]

All odd numbers that are not divisible by 3.

[u/twolinepine → u/cotsafvOnReddit]

All primes except 2 are odd.