20090406, 14:45  #1 
Apr 2009
2 Posts 
Proth theorem extended
Proth theorem extended:
let Q= k*2^n +1, where n=>3 is a odd natural number & k<= 2^n +1. if for some 'a', a^((Q1)/4) == +/1(mod Q), then 'Q' is prime. 'k' doesn't need to be restricted to only 'odd' numbers, either. proof: if 'm' is from the set of natural numbers, then every odd prime divisor 'q' of a^(2^(m+1))+/1 implies that q == +/1(mod a^(m+2)) [concluded from generalized 'Fermatnumber' proofs by Proth along with my replacing 'm' with 'm+1']. now, if 'p' is any prime divisor of 'R', then a^((Q1)/4) = (a^k)^(2^(n2)) == +/1(mod p) implies that p == +/1 (mod 2^n). thus, if 'R' is composite, 'R' will be the product of at least two primes each of which has minimum value of (2^n +1), and it follows that... k*2^n +1 >= (2^n +1)*(2^n +1) = (2^n)*(2^n) + 2*(2^n) +1; but the 1's cancel, so k*(2^n) >= (2^n)*(2^n) + 2*(2^n) and upon dividing by 2^n... k>= 2^n +2. moreover, this result is incompatible with our definition, so if k<= 2^n +1 and a^((Q1)/4) == +/1(mod Q), then 'Q' is prime. finally, if either k= 2*m or k= 2*m +1, then 'Q' is still 'odd'; Q= 2*m*2^n +1= m*2^(n+1)+1, or Q= (2m+1)*2^n +1= m*2^(n+1) +2^n+1. *QED 
20090406, 16:44  #2  
"Robert Gerbicz"
Oct 2005
Hungary
1,429 Posts 
Quote:
Q=8355841, so n=15, k=255, and let a=3, the conditions are true. a^((Q1)/4)==1 mod Q, but Q is composite: Q=13*41*61*257 

20090407, 06:56  #3 
Nov 2008
2·3^{3}·43 Posts 
I vote Misc. Math.

20090407, 07:46  #4 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
1773_{16} Posts 
So where is the error in the "proof"? I think it would be quite instructive to see where it goes wrong.

20090407, 13:25  #5  
"Robert Gerbicz"
Oct 2005
Hungary
1,429 Posts 
Quote:
"now, if 'p' is any prime divisor of 'R', then a^((Q1)/4) = (a^k)^(2^(n2)) == +/1(mod p) implies that p == +/1 (mod 2^n)" This is totally false. And R=Q in the "proof", if you haven't observed it. Last fiddled with by R. Gerbicz on 20090407 at 13:29 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Extended Cunningham or so  rekcahx  Factoring  6  20110819 12:45 
Proth's Theorem  ATH  Math  9  20110215 19:09 
Extended Cunningham tables  ZetaFlux  Factoring  2  20080303 18:34 
Converse of Proth's Theorem  Dougy  Math  15  20080130 21:17 
Extended Proth Theorem  Cyclamen Persicum  Math  1  20040420 04:54 