Proth's Theorem

ATH · 2011-02-12, 15:11

http://mathworld.wolfram.com/ProthsTheorem.html
http://primes.utm.edu/glossary/xpage/ProthPrime.html

I'm wondering about the requirement 2ⁿ>k. I know that without this requirement all odd numbers/primes would be Proth numbers/primes, but does the theorem work for k>2ⁿ ? or only sometimes?

I tested some fermat factors from: http://www.prothsearch.net/fermat.html and the theorem works on them:

N=52347*2⁷+1: a^(N-1)/2=-1 (mod N) for a=5,7,17
N=1071*2⁸+1: a^(N-1)/2=-1 (mod N) for a=5,11,13
N=262814145745*2⁸+1: a^(N-1)/2=-1 (mod N) for a=3,7,13
N=11141971095088142685*2⁹+1: a^(N-1)/2=-1 (mod N) for a=7,11
N=604944512477*2¹¹+1: a^(N-1)/2=-1 (mod N) for a=3,5,7,11
N=11131*2¹²+1: a^(N-1)/2=-1 (mod N) for a=3,5,11,17
N=395937*2¹⁴+1: a^(N-1)/2=-1 (mod N) for a=7,13,17
N=10253207784531279*2¹⁴+1: a^(N-1)/2=-1 (mod N) for a=5,7,13
N=434673084282938711*2¹³+1: a^(N-1)/2=-1 (mod N) for a=3,5,13,17

Jens K Andersen · 2011-02-14, 00:09

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.

ATH · 2011-02-14, 00:35

Thanks. I found a proof for Proth's theorem and I see how the requirement 2ⁿ>k arises.

http://www.artofproblemsolving.com/F...c.php?t=184587

science_man_88 · 2011-02-14, 01:10

Is this theorem used for Mersenne numbers? Could it be combined with LL testing to make a faster test ?

CRGreathouse · 2011-02-14, 02:58

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.

science_man_88 · 2011-02-14, 16:36

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).

science_man_88 · 2011-02-14, 17:34

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.

henryzz · 2011-02-14, 17:48

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.

chris2be8 · 2011-02-15, 18:33

Quote:

Originally Posted by ATH

Thanks. I found a proof for Proth's theorem and I see how the requirement 2ⁿ>k arises.

http://www.artofproblemsolving.com/F...c.php?t=184587

Would the proof also be valid if k=2ⁿ+1 ?

Chris K

axn · 2011-02-15, 19:09

Quote:

Originally Posted by chris2be8

Would the proof also be valid if k=2ⁿ+1 ?

Chris K

Looks like the proof structure would be valid upto k = 2^n[B]+1[/B]+1

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 2ⁿ>k. I know that without this requirement all odd numbers/primes would be Proth numbers/primes, but does the theorem work for k>2ⁿ ? or only sometimes? I tested some fermat factors from: http://www.prothsearch.net/fermat.html and the theorem works on them: N=523472⁷+1: a^(N-1)/2=-1 (mod N) for a=5,7,17 N=10712⁸+1: a^(N-1)/2=-1 (mod N) for a=5,11,13 N=2628141457452⁸+1: a^(N-1)/2=-1 (mod N) for a=3,7,13 N=111419710950881426852⁹+1: a^(N-1)/2=-1 (mod N) for a=7,11 N=6049445124772¹¹+1: a^(N-1)/2=-1 (mod N) for a=3,5,7,11 N=111312¹²+1: a^(N-1)/2=-1 (mod N) for a=3,5,11,17 N=3959372¹⁴+1: a^(N-1)/2=-1 (mod N) for a=7,13,17 N=102532077845312792¹⁴+1: a^(N-1)/2=-1 (mod N) for a=5,7,13 N=4346730842829387112¹³+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*

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Proth primes	ET_	Proth Prime Search	15	2022-06-26 03:27
Proth theorem extended	Bill Bouris	Conjectures 'R Us	4	2009-04-07 13:25
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
Last possible proth tested!	Deamiter	PSearch	3	2003-03-03 03:19

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 2ⁿ>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, 17:48	#8
henryzz Just call me Henry "David" Sep 2007 Liverpool (GMT/BST) 178F₁₆ 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.