20081005, 06:33  #1 
Jun 2005
62_{16} 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. best regards Anton Vrba 
20081005, 08:02  #2 
Jun 2005
2×7^{2} Posts 
I noticed a small typo, page 3 comment 2
(a+i)^(2k+1)=(ai) (mod 2k+1) and not (mod (a+i)) as in the paper. so please correct. 
20081005, 08:31  #3 
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 20081005 at 08:35 
20081005, 10:55  #4 
Feb 2004
France
2×461 Posts 
Waowwww !!!!
Hello Anton !
Congratulations to your work !!! I have juste read the proof and I need some time to chew it... However, I see that Phil Carmody already has a comment about a part that seems wrong to him. I hope that any unclear parts will be cleared asap, and that other people will approve your proof (Hey Bob ! Your comments ?) so that I can send my 100 Euro banknote to you ! Some preliminary comments:  In (2) and (4) and (6), it seems to me that you used q instead of p.  In many places, you use = instead of \equiv  About (9) { S(p1)=S(1) (Mod Wp) } , why ? It has been a question for the LLT when the "Penultimate LucasLehmer 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 ?  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 p2 iteration, is it impossible for a composite to reach S2 at step i<p ? Is it what your comment 2 is saying ?  I'm surprised to see that there is a (p2) cycle... but that works ! I've checked with different values. I should look again at these damned cycles for Wagstaff primes !  about your comments dealing with the cost of operations, we really don't care about one step less, same about some small numbers at beginning of iterations. That's peanuts when you have millions of iterations to do with FFT.  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^22 (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 ?  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). Once checked, the proof is yours, but I'm not sure the idea is entirely yours. Like the LLT is named LucasLehmerTest, since Lehmer provided a complete proof though Lucas did not but he had the idea, we have to clarify who had the idea to use Cycles and thus to test Sp=S0 (or Si, since you can iterate in a tail before reaching a cycle). You had the idea to use cycles for Wagstaff numbers, for sure. But, as far as I know, based on the Mersenne forum, I was the first to propose to use Cycles of a Digraph as a primality test. Did you write on a forum before me ? I need this point to be clarified because I would like that all the time I've spent on these damned tree and cycles of the Digraph under x^22 or x^2 modulo a prime before my wife died is not lost and that my children can see that all the time I didn't spend with her was useful in some way (Maths never die). Clarifying who had innovative ideas is one thing. Being able to build a proof is another thing. I'm VERY HAPPY you have made a big step !! Now, wait for other mathematicians to check and approve the proof ! What is important (once proof confirmed) is that now not only Mersenne numbers (and also the rare Fermats) can be verified proof or not in a very fast way. Other numbers are k*2^n1 numbers, with LLR, but it is a little bit smaller. Maybe George will provide such a test for Wagstaffs ? like Jean already did. Again, congratulations !! Tony 
20081005, 11:53  #5 
Jun 2005
2×7^{2} 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 Tony thanks for your comments I shall work those in and address your queries separately. 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. Last fiddled with by AntonVrba on 20081005 at 12:07 
20081005, 12:02  #6  
"Robert Gerbicz"
Oct 2005
Hungary
7^{2}×31 Posts 
Quote:
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). 

20081005, 12:07  #7 
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
10AE_{16} Posts 

20081005, 13:00  #8  
Jun 2005
2×7^{2} Posts 
Quote:
Quote:
Quote:
Quote:
Quote:
The LucasLehmer test proves that 2^p1 has no nontrivial factors smaller than 2^(p1). 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 LucasLehmer test. Thanks we now need to wait for the experts. Last fiddled with by AntonVrba on 20081005 at 13:22 Reason: in last sentance change no to now 

20081005, 13:03  #9 
Jun 2005
2·7^{2} Posts 

20081005, 13:18  #10  
Jun 2005
2×7^{2} Posts 
Quote:
(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. 

20081005, 13:23  #11 
"Robert Gerbicz"
Oct 2005
Hungary
7^{2}·31 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 20081005 at 13:23 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Prime numbers test primality  with proof written in invisible ink  Godzilla  Miscellaneous Math  40  20181017 00:11 
APRCL as primality proof  f1pokerspeed  FactorDB  14  20140109 21:06 
500€ Reward for a proof for the Wagstaff primality test conjecture  Tony Reix  Wagstaff PRP Search  7  20131010 01:23 
Proof of Primality Test for Fermat Numbers  princeps  Math  15  20120402 21:49 
Wagstaff number primality test?  ixfd64  Math  12  20100105 16:36 