 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 1011101001102 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 1011101001102 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 Dumbassville 203008 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,939 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
Dumbassville

26·131 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
Dumbassville

26×131 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 Cambridge (GMT/BST) 23·719 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

2×7×139 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

2×5×479 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 9 2020-10-02 07:11 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 10:41.

Wed Dec 2 10:41:17 UTC 2020 up 83 days, 7:52, 1 user, load averages: 2.54, 2.15, 2.11