mersenneforum.org > Math PRIMALITY PROOF for Wagstaff numbers!
 Register FAQ Search Today's Posts Mark Forums Read

2008-10-05, 06:33   #1
AntonVrba

Jun 2005

1428 Posts
PRIMALITY PROOF for Wagstaff numbers!

At last I have found the proof! Needed some lateral thinking.

This is as per my conjecture 4 in a paralel thread but now hopefully we can upgrade to theorem once checked. I am inviting comment to the attached proof.

$\blue \text{Let } q \text{ be a prime integer } > \ 3 \text{ , } W_q = \frac{1}{3}(2^q+1) \text{.}$

$\blue W_q \text{ is prime } \Longleftrightarrow \ S_{q} \equiv S_2 \ \pmod{W_q} \text{ , where: } S_0=6 \text{ , and } \ S_{i+1}=S_i^2-2 \ \pmod{W_q} \ .$

best regards
Anton Vrba
Attached Files
 Waggstaff0.0.pdf (90.3 KB, 552 views)

 2008-10-05, 08:02 #2 AntonVrba     Jun 2005 11000102 Posts I noticed a small typo, page 3 comment 2 (a+i)^(2k+1)=(a-i) (mod 2k+1) and not (mod (a+i)) as in the paper. so please correct.
 2008-10-05, 08:31 #3 Andi47     Oct 2004 Austria 46628 Posts Another typo, page 3, comment 1: "The reasoning presented may not be knew and already documented somewhere and references are kindly requested." I guess this should read: "...may not be new..." Edit: Your link to conjecture 4 does not work - there is one "http" too much. Last fiddled with by Andi47 on 2008-10-05 at 08:35
2008-10-05, 11:53   #5
AntonVrba

Jun 2005

9810 Posts

AND, after a rest, I noticed a wild and false conclusion regarding the order of the group, this has been corrected as well as the equality (19) regarding the group order.

I also added the alternate cycle S_0 = -3/2

I started of with q but then changewd to p so I must have skipped some. Editing in LaTex is not my strength and a complete new experience.
Attached Files
 Waggstaff0.2.pdf (97.3 KB, 313 views)

Last fiddled with by AntonVrba on 2008-10-05 at 12:07

2008-10-05, 12:02   #6
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

112·13 Posts

Quote:
 Originally Posted by AntonVrba At last I have found the proof! Needed some lateral thinking. This is as per my conjecture 4 in a paralel thread but now hopefully we can upgrade to theorem once checked. I am inviting comment to the attached proof.
Your proof is wrong. You can not do that step from (15) to (16), because if
a*c==b*c mod d, then you can't say that a==b mod d. You can do it only in that case, if you could prove that gcd(c,d)=1 is true in your ring (so if gcd(delta,W(p))=1 is true).

2008-10-05, 12:07   #7
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

2×3×23×31 Posts

Quote:
 Originally Posted by AntonVrba $\blue W_q \text{ is prime } \Longleftrightarrow \ S_{q} \equiv S_2 \ \pmod{W_q} \text{ , where: } S_0=6 \text{ , and } \ S_{i+1}=S_i^2-2 \ \pmod{W_q} \ .$
Is the $\pmod{W_q}$ in $\blue \ S_{q} \equiv S_2 \ \pmod{W_q}$ necessary? It seems that since both $S_{q}$ and $S_2$ are already $\pmod{W_q}$ it is completely unnecessary.

2008-10-05, 13:00   #8
AntonVrba

Jun 2005

1428 Posts

Quote:
 Originally Posted by T.Rex Some preliminary comments: - About (9) { S(p-1)=-S(1) (Mod Wp) } , why ? It has been a question for the LLT when the "Penultimate Lucas-Lehmer step" is - or +. No proof. But I remember that I read that, when using LLT in another case, it is always + (can't remember more details...). What is your proof ?
just remember s^2-2 = (-s)^2-2

Quote:
 Originally Posted by T.Rex - I do not see in the theorem the extra conditions saying that S2 must be reached at step p and never before step p. Is it no more useful ? With this p-2 iteration, is it impossible for a composite to reach S2 at step i
No, comment two says that S_0 and S_1 will never repeat in the iteration. Further, I believe that S_0=6,-6 and S_0=-3/2 are the only three numbers to guarantee cycles of p-2 and p-1 respectively and that all elemets of S_0 to S_(p-1) are unique for all prime W_p. I do not know what to call these numbers any suggestion.

Quote:
 Originally Posted by T.Rex - I'm surprised to see that there is a (p-2) cycle... but that works !
You have not studied the digraphs as you claim you have.

Quote:
 Originally Posted by T.Rex - what's inefficient in your test for Wagstaff numbers is your use of (mod Wp). There are technics for that (see LLR test) but they have a cost at each iteration, I think. Using S^2-2 (mod Np) with N=1+2^p enables to use faster FFT with modulo, I think, meaning the Prime95 code can be used with nearly no change. Hey ! you other people experts in this (Crandall, Woltman, Penné, & others), do you agree ?
I am sure that this is correct but I cannot prove it for now - somebody else can. The proof of sufficiency is not valid for 3W_p but the proof of necessity would be valid.

Quote:
 Originally Posted by T.Rex - and you say not a word about my idea to use cycles of a Digraph, nor you talk about Shallit&Vasiga work (they gave proofs about the cycles).
Please note I have not named the test but I am presenting the proof. I have not made use of any work of Shallit&Vasiga and thus no need to mention. We are not proofing the form of the diagraph, Shallit&Vasiga have done that, but the proof is making a statement regarding the possible divisors of W_p.

The Lucas-Lehmer test proves that 2^p-1 has no non-trivial factors smaller than 2^(p-1). A consequence of this is that the number is prime.

What this test does assert, is that there are no possible divisors smaller than sqrt(W_p), and as a consequence, W_p is prime - and thus it is very similar to the Lucas-Lehmer test.

Quote:
 Originally Posted by T.Rex Again, congratulations !! Tony
Thanks we now need to wait for the experts.

Last fiddled with by AntonVrba on 2008-10-05 at 13:22 Reason: in last sentance change no to now

2008-10-05, 13:03   #9
AntonVrba

Jun 2005

2·72 Posts

Quote:
 Originally Posted by Mini-Geek Is the $\pmod{W_q}$ in $\blue \ S_{q} \equiv S_2 \ \pmod{W_q}$ necessary? It seems that since both $S_{q}$ and $S_2$ are already $\pmod{W_q}$ it is completely unnecessary.
Thanks for the correction

2008-10-05, 13:18   #10
AntonVrba

Jun 2005

2·72 Posts

Quote:
 Originally Posted by R. Gerbicz Your proof is wrong. You can not do that step from (15) to (16), because if a*c==b*c mod d, then you can't say that a==b mod d. You can do it only in that case, if you could prove that gcd(c,d)=1 is true in your ring (so if gcd(delta,W(p))=1 is true).
My old number theory book from 1962 says:
(1) x = y(mod m)
and say that x is congruent to y modulo m. The quantity m is called the
modulus, and all numbers congruent (or equivalent) to x (mod m) are said
to constitute a congruence (or equivalence) class. Congruence classes are
preserved under the rational integral operations, addition, subtraction, and
multiplication.

Mathematica calculates that Mod[7,3x43]=7 and Mod[7*3,3*43]=21 so is it wrong? I think you can withdraw your statement.

 2008-10-05, 13:23 #11 R. Gerbicz     "Robert Gerbicz" Oct 2005 Hungary 112×13 Posts For example: 14==21 mod 7 is true, but after dividing 2==3 mod 7 isn't true. And you've done this. Last fiddled with by R. Gerbicz on 2008-10-05 at 13:23

 Similar Threads Thread Thread Starter Forum Replies Last Post Godzilla Miscellaneous Math 40 2018-10-17 00:11 f1pokerspeed FactorDB 14 2014-01-09 21:06 Tony Reix Wagstaff PRP Search 7 2013-10-10 01:23 princeps Math 15 2012-04-02 21:49 ixfd64 Math 12 2010-01-05 16:36

All times are UTC. The time now is 01:27.

Tue Aug 9 01:27:56 UTC 2022 up 32 days, 20:15, 1 user, load averages: 2.14, 1.43, 1.17

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.

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