mersenneforum.org Prime next to multiple of 6
 Register FAQ Search Today's Posts Mark Forums Read

 2022-03-05, 18:49 #1 jovada   Aug 2016 2×3 Posts Prime next to multiple of 6 I'm not a mathematician, but I just saw a Tweet by fermatslibrary stating that every prime is next to a multiple of 6. Isn't this a way faster way of figuring out whether a number is prime or not, instead of attacking it with lengthy tests? https://primes.utm.edu/notes/faq/six.html
2022-03-05, 19:05   #2
EdH

"Ed Hall"
Dec 2009

22·1,151 Posts

Quote:
 Originally Posted by jovada I'm not a mathematician, but I just saw a Tweet by fermatslibrary stating that every prime is next to a multiple of 6. Isn't this a way faster way of figuring out whether a number is prime or not, instead of attacking it with lengthy tests? https://primes.utm.edu/notes/faq/six.html
I'm not a mathematician, either, but whether this is true or not, it wouldn't mean that every number next to a multiple of 6 is prime. In fact, this is not the case. e.g. 25 is next to 24, but is clearly not prime.

2022-03-05, 19:12   #3
slandrum

Jan 2021
California

7·61 Posts

Quote:
 Originally Posted by jovada I'm not a mathematician
Clearly

Quote:
 I just saw a Tweet by fermatslibrary stating that every prime is next to a multiple of 6. Isn't this a way faster way of figuring out whether a number is prime or not, instead of attacking it with lengthy tests? https://primes.utm.edu/notes/faq/six.html
No, all primes above 2 are odd. Therefore every prime (above 2) has to be 6n+1, 6n+3 or 6n+5. 3 is the only prime that's 6n+3 because all numbers of the form 6n+3 are divisible by 3. Therefore all primes above 3 are 6n+1 or 6n+5 (6n+5 is equivalent to 6n-1) so all prime numbers above 3 must be adjacent to a multiple of 6. There's nothing earth shattering about this.

 2022-03-06, 15:41 #4 sweety439     "99(4^34019)99 palind" Nov 2016 (P^81993)SZ base 36 D8416 Posts For any positive integer n, all primes not dividing n are coprime to n, and the remainder of them to n must be in the reduced residue system mod n, e.g. for n=15, the reduced residue system is {1, 2, 4, 7, 8, 11, 13, 14}, and for your case of n=6, the reduced residue system is {1, 5}, thus all primes p not dividing 6 must == 1 or 5 mod 6, and if p == 1 mod 6, then p-1 is multiple of 6, if p == 5 mod 6, then p+1 is multiple of 6, thus all primes p not dividing 6 (i.e. other than 2 and 3) are next to multiple of 6
2022-03-11, 11:21   #5

Aug 2016

610 Posts

Quote:
 Originally Posted by slandrum Clearly
Thanks for being so polite.

And you just re-iterated my statement, however I was looking for an answer to the question whether it would be easier to test first if a given assignment is indeed of the form 6n+1 or 6n-1, instead of brutally attacking it with a lengthy test.
Assuming that checking the 6n+1 or 6n-1 is less brutal off course.

2022-03-11, 13:37   #6
Dobri

"Καλός"
May 2018

17×19 Posts

Quote:
 Originally Posted by jovada ..., however I was looking for an answer to the question whether it would be easier to test first if a given assignment is indeed of the form 6n+1 or 6n-1, instead of brutally attacking it with a lengthy test. Assuming that checking the 6n+1 or 6n-1 is less brutal off course.
Concerning the exponents of known Mersenne primes, except for the exponents 2 and 3, 24 exponents are of the type 6k+1 and 25 exponents are of the type 6k-1, see https://mersenneforum.org/showpost.p...1&postcount=37.

However, as stated by drkirkby in another thread, within the known sample size there are "more twin primes below Mersenne exponents than above Mersenne exponents", see https://mersenneforum.org/showthread.php?t=26812 and OEIS346645.

2022-03-11, 16:04   #7
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

22·31·43 Posts

Quote:
 Originally Posted by jovada Thanks for being so polite. And you just re-iterated my statement, however I was looking for an answer to the question whether it would be easier to test first if a given assignment is indeed of the form 6n+1 or 6n-1, instead of brutally attacking it with a lengthy test. Assuming that checking the 6n+1 or 6n-1 is less brutal off course.
As Slandrum explained to you a couple posts ago, you are asking if candidates should be trial-divided by 2 and 3 before doing a primality test. It seems you have no idea what sieving or trial-factoring is- so, the answer to your question is "yes". Yes, we check whether a number is even before doing a primality test. We also check whether it is divisible by 3, and 5, and quite a few more primes, before brutally (?) running a lengthy algorithm.

2022-03-12, 19:56   #8
Dobri

"Καλός"
May 2018

1010000112 Posts

Quote:
 Originally Posted by jovada ..., however I was looking for an answer to the question whether it would be easier to test first if a given assignment is indeed of the form 6n+1 or 6n-1,...
Note that 2p - 1 = 6n + 1 for all odd positive integers p = 1, 3, 5, 7, 9,...
because 2p - 1 = (2 - 1)(2p-1 + 2p-2 + ... + 22 + 21 + 20) = ((3-1)p-1 + (3-1)p-2) + ... + ((3-1)2 + (3-1)1) + 1
and after applying the binomial theorem (see https://en.wikipedia.org/wiki/Binomial_theorem)
the terms (1p-1 - 1p-2) + ... + (12 - 11) within the parentheses cancel each other.

 2022-03-12, 20:50 #9 slandrum   Jan 2021 California 42710 Posts Well, if you are going to specifically talk about Mersenne primes, the candidates can't have any "small" factors (like 3) because all factors of 2^p-1 are of the form 2kp+1, so when looking at Mersenne candidates with exponents over 100 million (which is the low end of the search right now), the smallest possible factor will be over 200 million. But there are lots of other types of primes that people are looking for, that's just the main project.
2022-03-13, 02:20   #10
tuckerkao

"Tucker Kao"
Jan 2020

743 Posts

Quote:
 Originally Posted by VBCurtis As Slandrum explained to you a couple posts ago, you are asking if candidates should be trial-divided by 2 and 3 before doing a primality test. It seems you have no idea what sieving or trial-factoring is- so, the answer to your question is "yes". Yes, we check whether a number is even before doing a primality test. We also check whether it is divisible by 3, and 5, and quite a few more primes, before brutally (?) running a lengthy algorithm.
Any exponents or the numbers themselves divisible by 2 or 3 can be easily identified with the last digit. Factors of 5 or 7 can be trial divided within the matter of seconds from the trial factoring software. The GPU trial factoring usually refer to the factors of the numerical sizes of quadrillions to quintillions before the PRP tests which run the lengthy algorithm.

2022-03-13, 03:05   #11
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

533210 Posts

Quote:
 Originally Posted by tuckerkao Any exponents or the numbers themselves divisible by 2 or 3 can be easily identified with the last digit.
As usual, you reply to a post with incorrect mathematical content.

Or, please tell us how the last digit allows you to identify whether a number is divisible by 3.

Here are numbers not divisible by 3: 10, 11, 22, 23, 34, 35, 46, 47, 58, 59. There's all ten last digits. So, explain.

Last fiddled with by VBCurtis on 2022-03-13 at 03:06

 Similar Threads Thread Thread Starter Forum Replies Last Post drkirkby Math 4 2021-04-13 12:58 bgbeuning GPU Computing 52 2016-06-09 05:26 numbercruncher Information & Answers 18 2014-04-17 00:17 WraithX GPU Computing 16 2012-03-22 10:44 BillW Software 1 2003-01-21 20:11

All times are UTC. The time now is 10:56.

Sat Jul 2 10:56:24 UTC 2022 up 79 days, 8:57, 0 users, load averages: 1.44, 1.05, 1.12