mersenneforum.org Prime numbers test primality - with proof written in invisible ink
 Register FAQ Search Today's Posts Mark Forums Read

 2018-04-03, 14:47 #1 Godzilla     May 2016 2418 Posts Prime numbers test primality - with proof written in invisible ink
 2018-04-03, 15:17 #2 CRGreathouse     Aug 2006 134648 Posts Up to 1000 this fails for 1, 6, 15, 66, 85, 91, 186, 341, 435, 451, 561, 645, 703, and 946.
2018-04-04, 13:05   #3
Dr Sardonicus

Feb 2017
Nowhere

2×1,949 Posts

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)

2018-04-04, 16:46   #4
Godzilla

May 2016

7·23 Posts

Quote:
 Originally Posted by Dr Sardonicus 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]

2018-04-05, 13:04   #5
Dr Sardonicus

Feb 2017
Nowhere

2·1,949 Posts

Quote:
 Originally Posted by Dr Sardonicus 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)

2018-04-05, 14:16   #6
Godzilla

May 2016

7·23 Posts

Quote:
 Originally Posted by Dr Sardonicus 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.

2018-04-05, 16:37   #7
CRGreathouse

Aug 2006

22·33·5·11 Posts

Quote:
 Originally Posted by Godzilla 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.

2018-04-05, 16:44   #8
Godzilla

May 2016

7·23 Posts

Quote:
 Originally Posted by CRGreathouse 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?

2018-04-05, 16:50   #9
Dr Sardonicus

Feb 2017
Nowhere

2·1,949 Posts

Quote:
 Originally Posted by Godzilla 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

2018-04-05, 17:09   #10
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

918310 Posts

Quote:
 Originally Posted by Godzilla in your opinion, is this discovery something important?
What discovery?

2018-04-05, 17:24   #11
Godzilla

May 2016

101000012 Posts

Quote:
 Originally Posted by Dr Sardonicus 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?

 Similar Threads Thread Thread Starter Forum Replies Last Post Tony Reix Wagstaff PRP Search 7 2013-10-10 01:23 princeps Math 15 2012-04-02 21:49 Arkadiusz Math 6 2011-04-05 19:39 AntonVrba Math 96 2009-02-25 10:37 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