Prime numbers test primality - with proof written in invisible ink

[Godzilla]

https://zenodo.org/record/1211591#.WsORgnXOM0M

[CRGreathouse]

Up to 1000 this fails for 1, 6, 15, 66, 85, 91, 186, 341, 435, 451, 561, 645, 703, and 946.

[Dr Sardonicus]

See the Wikipedia page on the Chinese hypothesis. This article says that

Composite numbers n for which 2ⁿ−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

2^m == 2 (mod m),

so I guess these are also prime.

Exercise: If 2ⁿ == 2 (mod n), then 2^2n-1 == 2 (mod n)

[Godzilla]

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

2^m == 2 (mod m),

so I guess these are also prime.

Exercise: If 2ⁿ == 2 (mod n), then 2^2n-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]

[Dr Sardonicus]

Originally Posted by Dr Sardonicus

Exercise: If 2ⁿ == 2 (mod n), then 2^2n-1 == 2 (mod n)

I should point out that the converse is false. As CRGreathouse has pointed out already,

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

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

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

2ⁿ == 2 (mod n)

[Godzilla]

Originally Posted by Dr Sardonicus

I should point out that the converse is false. As CRGreathouse has pointed out already,

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

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

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

2ⁿ == 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.

[CRGreathouse]

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.

[Godzilla]

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?

[Dr Sardonicus]

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:

2^p−1*2^p 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,

2^p−1*2^p mod p 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 2^p−1*2^p mod p = 2.

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

[Batalov]

Originally Posted by Godzilla

in your opinion, is this discovery something important?

What discovery?

[Godzilla]

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 2^p−1*2^p 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?