 mersenneforum.org > Math Proth's Theorem
 Register FAQ Search Today's Posts Mark Forums Read 2011-02-12, 15:11 #1 ATH 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 2n>k. I know that without this requirement all odd numbers/primes would be Proth numbers/primes, but does the theorem work for k>2n ? or only sometimes? I tested some fermat factors from: http://www.prothsearch.net/fermat.html and the theorem works on them: N=52347*27+1: a(N-1)/2=-1 (mod N) for a=5,7,17 N=1071*28+1: a(N-1)/2=-1 (mod N) for a=5,11,13 N=262814145745*28+1: a(N-1)/2=-1 (mod N) for a=3,7,13 N=11141971095088142685*29+1: a(N-1)/2=-1 (mod N) for a=7,11 N=604944512477*211+1: a(N-1)/2=-1 (mod N) for a=3,5,7,11 N=11131*212+1: a(N-1)/2=-1 (mod N) for a=3,5,11,17 N=395937*214+1: a(N-1)/2=-1 (mod N) for a=7,13,17 N=10253207784531279*214+1: a(N-1)/2=-1 (mod N) for a=5,7,13 N=434673084282938711*213+1: a(N-1)/2=-1 (mod N) for a=3,5,13,17 Last fiddled with by ATH on 2011-02-12 at 15:16   2011-02-14, 00:09 #2 Jens K Andersen   Feb 2006 Denmark 2×5×23 Posts If a^(N-1)/2=-1 (mod N), then a^(N-1)=1 (mod N), so N is a base-a 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.   2011-02-14, 00:35 #3 ATH Einyen   Dec 2003 Denmark 2×17×101 Posts Thanks. I found a proof for Proth's theorem and I see how the requirement 2n>k arises. http://www.artofproblemsolving.com/F...c.php?t=184587   2011-02-14, 01:10 #4 science_man_88   "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 ?   2011-02-14, 02:58   #5
CRGreathouse

Aug 2006

5,987 Posts Quote:
 Originally Posted by science_man_88 Is this theorem used for Mersenne numbers? Could it be combined with LL testing to make a faster test ?
No and no, respectively. But it's not needed -- Lucas-Lehmer is faster anyway.   2011-02-14, 16:36   #6
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

100000111000102 Posts Quote:
 Originally Posted by CRGreathouse No and no, respectively. But it's not needed -- Lucas-Lehmer is faster anyway.
Thanks! I actually did testing of my own the problem for me is solving for the base, the exponent is (((2^n-1)-1)/2) or 2^(n-1)-1 , So the problem becomes base^(2^(n-1)-1) = -1 Mod (2^n-1).

Last fiddled with by science_man_88 on 2011-02-14 at 16:36   2011-02-14, 17:34   #7
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

100000111000102 Posts Quote:
 Originally Posted by science_man_88 Thanks! I actually did testing of my own the problem for me is solving for the base, the exponent is (((2^n-1)-1)/2) or 2^(n-1)-1 , So the problem becomes base^(2^(n-1)-1) = -1 Mod (2^n-1).
never mind i messed up it's just p not the fancy stuff never mind.   2011-02-14, 17:48 #8 henryzz Just call me Henry   "David" Sep 2007 Liverpool (GMT/BST) 178F16 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 2011-02-15, 18:33   #9
chris2be8

Sep 2009

97A16 Posts Quote:
 Originally Posted by ATH Thanks. I found a proof for Proth's theorem and I see how the requirement 2n>k arises. http://www.artofproblemsolving.com/F...c.php?t=184587
Would the proof also be valid if k=2n+1 ?

Chris K   2011-02-15, 19:09   #10
axn

Jun 2003

22×32×151 Posts Quote:
 Originally Posted by chris2be8 Would the proof also be valid if k=2n+1 ? Chris K
Looks like the proof structure would be valid upto k = 2n[B]+1[/B]+1  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post ET_ Proth Prime Search 15 2022-06-26 03:27 Bill Bouris Conjectures 'R Us 4 2009-04-07 13:25 Dougy Math 15 2008-01-30 21:17 Cyclamen Persicum Math 1 2004-04-20 04:54 Deamiter PSearch 3 2003-03-03 03:19

All times are UTC. The time now is 21:21.

Thu Feb 2 21:21:53 UTC 2023 up 168 days, 18:50, 1 user, load averages: 0.77, 0.83, 0.84