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, 570 views)

 2008-10-05, 08:02 #2 AntonVrba     Jun 2005 9810 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 2×17×73 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

1428 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, 331 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

161110 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
TimSorbet
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

10B716 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

2·72 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 64B16 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 11:55.

Sun Jan 29 11:55:12 UTC 2023 up 164 days, 9:23, 0 users, load averages: 0.66, 1.20, 1.17