20110212, 15:11  #1 
Einyen
Dec 2003
Denmark
2·17·101 Posts 
Proth's Theorem
http://mathworld.wolfram.com/ProthsTheorem.html
http://primes.utm.edu/glossary/xpage/ProthPrime.html I'm wondering about the requirement 2^{n}>k. I know that without this requirement all odd numbers/primes would be Proth numbers/primes, but does the theorem work for k>2^{n} ? or only sometimes? I tested some fermat factors from: http://www.prothsearch.net/fermat.html and the theorem works on them: N=52347*2^{7}+1: a^{(N1)/2}=1 (mod N) for a=5,7,17 N=1071*2^{8}+1: a^{(N1)/2}=1 (mod N) for a=5,11,13 N=262814145745*2^{8}+1: a^{(N1)/2}=1 (mod N) for a=3,7,13 N=11141971095088142685*2^{9}+1: a^{(N1)/2}=1 (mod N) for a=7,11 N=604944512477*2^{11}+1: a^{(N1)/2}=1 (mod N) for a=3,5,7,11 N=11131*2^{12}+1: a^{(N1)/2}=1 (mod N) for a=3,5,11,17 N=395937*2^{14}+1: a^{(N1)/2}=1 (mod N) for a=7,13,17 N=10253207784531279*2^{14}+1: a^{(N1)/2}=1 (mod N) for a=5,7,13 N=434673084282938711*2^{13}+1: a^{(N1)/2}=1 (mod N) for a=3,5,13,17 Last fiddled with by ATH on 20110212 at 15:16 
20110214, 00:09  #2 
Feb 2006
Denmark
2×5×23 Posts 
If a^(N1)/2=1 (mod N), then a^(N1)=1 (mod N), so N is a basea Fermat prp by Fermat's little theorem.
Proth's theorem gives a condition where this also proves primality. You are only testing known primes which will of course all be Fermat prp's. Proth's condition is not satisfied so you haven't shown whether they are primes or Fermat pseudoprimes. 
20110214, 00:35  #3 
Einyen
Dec 2003
Denmark
2×17×101 Posts 
Thanks. I found a proof for Proth's theorem and I see how the requirement 2^{n}>k arises.
http://www.artofproblemsolving.com/F...c.php?t=184587 
20110214, 01:10  #4 
"Forget I exist"
Jul 2009
Dartmouth NS
2·3·23·61 Posts 
Is this theorem used for Mersenne numbers? Could it be combined with LL testing to make a faster test ?

20110214, 02:58  #5 
Aug 2006
5,987 Posts 

20110214, 16:36  #6 
"Forget I exist"
Jul 2009
Dartmouth NS
10000011100010_{2} Posts 
Thanks! I actually did testing of my own the problem for me is solving for the base, the exponent is (((2^n1)1)/2) or 2^(n1)1 , So the problem becomes base^(2^(n1)1) = 1 Mod (2^n1).
Last fiddled with by science_man_88 on 20110214 at 16:36 
20110214, 17:34  #7 
"Forget I exist"
Jul 2009
Dartmouth NS
10000011100010_{2} Posts 

20110214, 17:48  #8 
Just call me Henry
"David"
Sep 2007
Liverpool (GMT/BST)
178F_{16} Posts 
The LLR test also needs 2^n>k. Is that for pretty much the same reason?
As far as I can tell some riesel primes pass the LLR test with 2^n<k but some don't. 
20110215, 18:33  #9  
Sep 2009
97A_{16} Posts 
Quote:
Chris K 

20110215, 19:09  #10 
Jun 2003
2^{2}×3^{2}×151 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Proth primes  ET_  Proth Prime Search  15  20220626 03:27 
Proth theorem extended  Bill Bouris  Conjectures 'R Us  4  20090407 13:25 
Converse of Proth's Theorem  Dougy  Math  15  20080130 21:17 
Extended Proth Theorem  Cyclamen Persicum  Math  1  20040420 04:54 
Last possible proth tested!  Deamiter  PSearch  3  20030303 03:19 