20180403, 14:47  #1 
May 2016
A1_{16} Posts 
Prime numbers test primality  with proof written in invisible ink

20180403, 15:17  #2 
Aug 2006
3×1,987 Posts 
Up to 1000 this fails for 1, 6, 15, 66, 85, 91, 186, 341, 435, 451, 561, 645, 703, and 946.

20180404, 13:05  #3  
Feb 2017
Nowhere
2^{2}·7·149 Posts 
See the Wikipedia page on the Chinese hypothesis. This article says that
Quote:
2^{m} == 2 (mod m), so I guess these are also prime. Exercise: If 2^{n} == 2 (mod n), then 2^{2n1} == 2 (mod n) 

20180404, 16:46  #4  
May 2016
A1_{16} Posts 
Quote:
%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] 

20180405, 13:04  #5  
Feb 2017
Nowhere
2^{2}×7×149 Posts 
Quote:
2^{2n1} == 2 (mod n) for, e.g. n = 6, 15, 66, 85, 91, 186 whereas 2^{n} =/= 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^{n} == 2 (mod n) 

20180405, 14:16  #6  
May 2016
7·23 Posts 
Quote:


20180405, 16:37  #7 
Aug 2006
3·1,987 Posts 
It should fail only for 2pseudoprimes and certain even numbers, the primes should all be ok.

20180405, 16:44  #8 
May 2016
241_{8} Posts 

20180405, 16:50  #9  
Feb 2017
Nowhere
2^{2}×7×149 Posts 
Quote:
Quote:
Your criterion identifies more composite numbers as primes than the "Chinese hypothesis," which only errs at composite base2 pseudoprimes. The converse implication of your claim, Quote:
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." Last fiddled with by Dr Sardonicus on 20180405 at 16:56 

20180405, 17:09  #10 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3^{3}·7^{3} Posts 

20180405, 17:24  #11  
May 2016
A1_{16} Posts 
Quote:


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  20131010 01:23 
Proof of Primality Test for Fermat Numbers  princeps  Math  15  20120402 21:49 
The fastest primality test for Fermat numbers.  Arkadiusz  Math  6  20110405 19:39 
PRIMALITY PROOF for Wagstaff numbers!  AntonVrba  Math  96  20090225 10:37 
A primality test for Fermat numbers faster than Pépin's test ?  T.Rex  Math  0  20041026 21:37 