mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2018-04-03, 14:47   #1
Godzilla
 
Godzilla's Avatar
 
May 2016

2418 Posts
Default Prime numbers test primality - with proof written in invisible ink

https://zenodo.org/record/1211591#.WsORgnXOM0M
Godzilla is offline   Reply With Quote
Old 2018-04-03, 15:17   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

134648 Posts
Default

Up to 1000 this fails for 1, 6, 15, 66, 85, 91, 186, 341, 435, 451, 561, 645, 703, and 946.
CRGreathouse is offline   Reply With Quote
Old 2018-04-04, 13:05   #3
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2×1,949 Posts
Default

See the Wikipedia page on the Chinese hypothesis. This article says that
Quote:
Composite numbers n for which 2n−2 is divisible by n are called Poulet numbers.
Albert Beiler's Recreations in the Theory of Numbers The Queen of Mathematics Entertains mentions that the even numbers m = 215326, 2568226, and 143742226 satisfy

2m == 2 (mod m),

so I guess these are also prime.

Exercise: If 2n == 2 (mod n), then 22n-1 == 2 (mod n)
Dr Sardonicus is offline   Reply With Quote
Old 2018-04-04, 16:46   #4
Godzilla
 
Godzilla's Avatar
 
May 2016

7·23 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
See the Wikipedia page on the Chinese hypothesis. This article says that

Albert Beiler's Recreations in the Theory of Numbers The Queen of Mathematics Entertains mentions that the even numbers m = 215326, 2568226, and 143742226 satisfy

2m == 2 (mod m),

so I guess these are also prime.

Exercise: If 2n == 2 (mod n), then 22n-1 == 2 (mod n)
(19:18) gp > factor(215326)
%3 =
[ 2 1]

[ 23 1]

[ 31 1]

[151 1]

(15:54) gp > factor(2568226)
%4 =
[ 2 1]

[ 23 1]

[ 31 1]

[1801 1]

(15:54) gp > 143742226
%5 = 143742226
(15:54) gp > factor(%5)
%6 =
[ 2 1]

[ 23 1]

[ 31 1]

[100801 1]
Godzilla is offline   Reply With Quote
Old 2018-04-05, 13:04   #5
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2·1,949 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
Exercise: If 2n == 2 (mod n), then 22n-1 == 2 (mod n)
I should point out that the converse is false. As CRGreathouse has pointed out already,

22n-1 == 2 (mod n) for, e.g. n = 6, 15, 66, 85, 91, 186

whereas 2n =/= 2 (mod n) in these cases.

So it is easier for composites to satisfy the OP's "primality" criterion than it is to satisfy

2n == 2 (mod n)
Dr Sardonicus is offline   Reply With Quote
Old 2018-04-05, 14:16   #6
Godzilla
 
Godzilla's Avatar
 
May 2016

7·23 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
I should point out that the converse is false. As CRGreathouse has pointed out already,

22n-1 == 2 (mod n) for, e.g. n = 6, 15, 66, 85, 91, 186

whereas 2n =/= 2 (mod n) in these cases.

So it is easier for composites to satisfy the OP's "primality" criterion than it is to satisfy

2n == 2 (mod n)
This is right, but up to 1000 there is a relatively small error. if we then exclude the even numbers and the multiple numbers of 5, the error is even less. I think instead it is interesting until it fails with a prime number.
Godzilla is offline   Reply With Quote
Old 2018-04-05, 16:37   #7
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

22·33·5·11 Posts
Default

Quote:
Originally Posted by Godzilla View Post
This is right, but up to 1000 there is a relatively small error. if we then exclude the even numbers and the multiple numbers of 5, the error is even less. I think instead it is interesting until it fails with a prime number.
It should fail only for 2-pseudoprimes and certain even numbers, the primes should all be ok.
CRGreathouse is offline   Reply With Quote
Old 2018-04-05, 16:44   #8
Godzilla
 
Godzilla's Avatar
 
May 2016

7·23 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
It should fail only for 2-pseudoprimes and certain even numbers, the primes should all be ok.
in your opinion, is this discovery something important?
Godzilla is offline   Reply With Quote
Old 2018-04-05, 16:50   #9
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2·1,949 Posts
Default

Quote:
Originally Posted by Godzilla View Post
I think instead it is interesting until it fails with a prime number.
Sorry, but that's not what you wrote. One of your claims is the following implication:
Quote:
2p−1*2p mod p = 2 Than [sic] p Is a Prime Number
The smallest positive integer falsifying your claim is 1, which is not prime (and also not composite). The smallest composite number falsifying your claim is 6. There is no "relative" size of error when it comes to an implication. One counterexample and it's wrong.

Your criterion identifies more composite numbers as primes than the "Chinese hypothesis," which only errs at composite base-2 pseudoprimes.

The converse implication of your claim,

Quote:
2p−1*2p mod p \ne 2 Than [sic] p Is not a Prime Number
is however true. This implication is equivalent to its contrapositive,

If p is a prime number, then 2p−1*2p mod p = 2.

This may be directly verified for p = 2. For primes p > 2, it is a consequence of "Fermat's little Theorem."

Last fiddled with by Dr Sardonicus on 2018-04-05 at 16:56
Dr Sardonicus is offline   Reply With Quote
Old 2018-04-05, 17:09   #10
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

918310 Posts
Default

Quote:
Originally Posted by Godzilla View Post
in your opinion, is this discovery something important?
What discovery?
Batalov is offline   Reply With Quote
Old 2018-04-05, 17:24   #11
Godzilla
 
Godzilla's Avatar
 
May 2016

101000012 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
Sorry, but that's not what you wrote. One of your claims is the following implication:


The smallest positive integer falsifying your claim is 1, which is not prime (and also not composite). The smallest composite number falsifying your claim is 6. There is no "relative" size of error when it comes to an implication. One counterexample and it's wrong.

Your criterion identifies more composite numbers as primes than the "Chinese hypothesis," which only errs at composite base-2 pseudoprimes.

The converse implication of your claim,



is however true. This implication is equivalent to its contrapositive,

If p is a prime number, then 2p−1*2p mod p = 2.

This may be directly verified for p = 2. For primes p > 2, it is a consequence of "Fermat's little Theorem."
maybe I expressed myself badly, but even if I made wrong statements in my work, I can always say that wrong for even pseudoprime and multiples of 5 and very few odd pseudoprime numbers (five numbers excluded number 1 up to 1000), I know you mean that it is not a universal formula, but I wanted to know if it was already known as 2 ^ 2p-1 = 2 (mod p) or was it unknown as a consequence of Fermat's little Theorem?
Godzilla is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
500€ Reward for a proof for the Wagstaff primality test conjecture Tony Reix Wagstaff PRP Search 7 2013-10-10 01:23
Proof of Primality Test for Fermat Numbers princeps Math 15 2012-04-02 21:49
The fastest primality test for Fermat numbers. Arkadiusz Math 6 2011-04-05 19:39
PRIMALITY PROOF for Wagstaff numbers! AntonVrba Math 96 2009-02-25 10:37
A primality test for Fermat numbers faster than Pépin's test ? T.Rex Math 0 2004-10-26 21:37

All times are UTC. The time now is 08:47.

Sat Dec 5 08:47:42 UTC 2020 up 2 days, 4:59, 0 users, load averages: 0.95, 1.17, 1.47

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.