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 D5716 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 23010 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 341510 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 100000111000102 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

2×3×23×61 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

203428 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) 7×859 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

45478 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

34×67 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

 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 19:27.

Fri Dec 2 19:27:12 UTC 2022 up 106 days, 16:55, 0 users, load averages: 1.18, 1.05, 1.01

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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔