Prime next to multiple of 6

[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

[EdH]

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.

[slandrum]

Originally Posted by jovada

I'm not a mathematician

Clearly

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.

[sweety439]

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

[jovada]

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.

[Dobri]

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.

[VBCurtis]

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.

[Dobri]

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 2^p - 1 = 6n + 1 for all odd positive integers p = 1, 3, 5, 7, 9,...
because 2^p - 1 = (2 - 1)(2^p-1 + 2^p-2 + ... + 2² + 2¹ + 2⁰) = ((3-1)^p-1 + (3-1)^p-2) + ... + ((3-1)² + (3-1)¹) + 1
and after applying the binomial theorem (see https://en.wikipedia.org/wiki/Binomial_theorem)
the terms (1^p-1 - 1^p-2) + ... + (1² - 1¹) within the parentheses cancel each other.

[slandrum]

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.

[tuckerkao]

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.

[VBCurtis]

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.