Proth's Theorem
 

[URL="http://mathworld.wolfram.com/ProthsTheorem.html"]http://mathworld.wolfram.com/ProthsTheorem.html[/URL]
[URL="http://primes.utm.edu/glossary/xpage/ProthPrime.html"]http://primes.utm.edu/glossary/xpage/ProthPrime.html[/URL]

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

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

N=52347*2[sup]7[/sup]+1: a[sup](N-1)/2[/sup]=-1 (mod N) for a=5,7,17
N=1071*2[sup]8[/sup]+1: a[sup](N-1)/2[/sup]=-1 (mod N) for a=5,11,13
N=262814145745*2[sup]8[/sup]+1: a[sup](N-1)/2[/sup]=-1 (mod N) for a=3,7,13
N=11141971095088142685*2[sup]9[/sup]+1: a[sup](N-1)/2[/sup]=-1 (mod N) for a=7,11
N=604944512477*2[sup]11[/sup]+1: a[sup](N-1)/2[/sup]=-1 (mod N) for a=3,5,7,11
N=11131*2[sup]12[/sup]+1: a[sup](N-1)/2[/sup]=-1 (mod N) for a=3,5,11,17
N=395937*2[sup]14[/sup]+1: a[sup](N-1)/2[/sup]=-1 (mod N) for a=7,13,17
N=10253207784531279*2[sup]14[/sup]+1: a[sup](N-1)/2[/sup]=-1 (mod N) for a=5,7,13
N=434673084282938711*2[sup]13[/sup]+1: a[sup](N-1)/2[/sup]=-1 (mod N) for a=3,5,13,17

If a^(N-1)/2=-1 (mod N), then a^(N-1)=1 (mod N), so N is a base-a Fermat prp by [URL="http://primes.utm.edu/glossary/xpage/FermatsLittleTheorem.html"]Fermat's little theorem[/URL].

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.

Thanks. I found a proof for Proth's theorem and I see how the requirement 2[sup]n[/sup]>k arises.

[URL="http://www.artofproblemsolving.com/Forum/viewtopic.php?t=184587"]http://www.artofproblemsolving.com/Forum/viewtopic.php?t=184587[/URL]

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

[QUOTE=science_man_88;252415]Is this theorem used for Mersenne numbers? Could it be combined with LL testing to make a faster test ?[/QUOTE]

No and no, respectively. But it's not needed -- Lucas-Lehmer is faster anyway.

[QUOTE=CRGreathouse;252424]No and no, respectively. But it's not needed -- Lucas-Lehmer is faster anyway.[/QUOTE]

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

[QUOTE=science_man_88;252473]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).[/QUOTE]

never mind i messed up it's just p not the fancy stuff never mind.

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.

[QUOTE=ATH;252410]Thanks. I found a proof for Proth's theorem and I see how the requirement 2[sup]n[/sup]>k arises.

[URL]http://www.artofproblemsolving.com/Forum/viewtopic.php?t=184587[/URL][/QUOTE]

Would the proof also be valid if k=2[sup]n[/sup]+1 ?

Chris K

[QUOTE=chris2be8;252592]Would the proof also be valid if k=2[sup]n[/sup]+1 ?

Chris K[/QUOTE]

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