mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Conjectures 'R Us

Reply
 
Thread Tools
Old 2009-04-06, 14:45   #1
Bill Bouris
 
Apr 2009

2 Posts
Default 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^((Q-1)/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 'Fermat-number' proofs by Proth along with my replacing 'm' with 'm+1'].

now, if 'p' is any prime divisor of 'R', then a^((Q-1)/4) = (a^k)^(2^(n-2)) == +/-1(mod p) implies that p == +/-1 (mod 2^n). thus, if 'R' is compo-site, '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^((Q-1)/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
Bill Bouris is offline   Reply With Quote
Old 2009-04-06, 16:44   #2
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

11·127 Posts
Default

Quote:
Originally Posted by Bill Bouris View Post
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^((Q-1)/4) == +/-1(mod Q), then 'Q' is prime. 'k' doesn't need to be restricted to only 'odd' numbers, either.

proof:
When I see such a "theorem" I try to find a counter-example in Pari-Gp. Here it is one:

Q=8355841, so n=15, k=255, and let a=3, the conditions are true.
a^((Q-1)/4)==1 mod Q, but Q is composite: Q=13*41*61*257
R. Gerbicz is offline   Reply With Quote
Old 2009-04-07, 06:56   #3
10metreh
 
10metreh's Avatar
 
Nov 2008

2·33·43 Posts
Default

I vote Misc. Math.
10metreh is offline   Reply With Quote
Old 2009-04-07, 07:46   #4
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

25·179 Posts
Default

So where is the error in the "proof"? I think it would be quite instructive to see where it goes wrong.
retina is offline   Reply With Quote
Old 2009-04-07, 13:25   #5
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

57516 Posts
Default

Quote:
Originally Posted by retina View Post
So where is the error in the "proof"? I think it would be quite instructive to see where it goes wrong.
Yes, this is far from a standard proof in math. Here it is a big mistake:
"now, if 'p' is any prime divisor of 'R', then a^((Q-1)/4) = (a^k)^(2^(n-2)) == +/-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 2009-04-07 at 13:29
R. Gerbicz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Extended Cunningham or so rekcahx Factoring 6 2011-08-19 12:45
Proth's Theorem ATH Math 9 2011-02-15 19:09
Extended Cunningham tables Zeta-Flux Factoring 2 2008-03-03 18:34
Converse of Proth's Theorem Dougy Math 15 2008-01-30 21:17
Extended Proth Theorem Cyclamen Persicum Math 1 2004-04-20 04:54

All times are UTC. The time now is 00:09.

Wed Sep 23 00:09:19 UTC 2020 up 12 days, 21:20, 1 user, load averages: 1.74, 1.77, 1.71

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.