mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2011-02-12, 15:11   #1
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

1011101001102 Posts
Default 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
ATH is online now   Reply With Quote
Old 2011-02-14, 00:09   #2
Jens K Andersen
 
Jens K Andersen's Avatar
 
Feb 2006
Denmark

2×5×23 Posts
Default

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.
Jens K Andersen is offline   Reply With Quote
Old 2011-02-14, 00:35   #3
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

1011101001102 Posts
Default

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
ATH is online now   Reply With Quote
Old 2011-02-14, 01:10   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

203008 Posts
Default

Is this theorem used for Mersenne numbers? Could it be combined with LL testing to make a faster test ?
science_man_88 is offline   Reply With Quote
Old 2011-02-14, 02:58   #5
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

5,939 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2011-02-14, 16:36   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
science_man_88 is offline   Reply With Quote
Old 2011-02-14, 17:34   #7
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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.
science_man_88 is offline   Reply With Quote
Old 2011-02-14, 17:48   #8
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

23·719 Posts
Default

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.
henryzz is offline   Reply With Quote
Old 2011-02-15, 18:33   #9
chris2be8
 
chris2be8's Avatar
 
Sep 2009

2×7×139 Posts
Default

Quote:
Originally Posted by ATH View Post
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
chris2be8 is offline   Reply With Quote
Old 2011-02-15, 19:09   #10
axn
 
axn's Avatar
 
Jun 2003

2×5×479 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
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
axn is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Proth primes ET_ Proth Prime Search 9 2020-10-02 07:11
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

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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.