What are the Primality Tests ( not factoring! ) for Fermat Numbers?

[T.Rex]

Hi,
I've succeeded in proving the following:

Fn = 2^2^n +1
T[0]=40
T[i]=2*T[i-1]*(T[i-1]+1)
Fn is prime iff T[2^n-2] = 0 (mod Fn)

Example:

n=3
F[3] = 2^2^3+1 = 2^8+1 = 257

T[0] = 40
T[1] = 196
T[2] = 124
T[3] = 160
T[4] = 120
T[5] = 256
T[6] = T[2^4-2] = 0


n = 4
F[4] = 2^2^4+1 = 2^16+1 = 65537

T[ 0] = 40
T[ 1] = 3280
T[ 2] = 27224
T[ 3] = 30934
T[ 4] = 9569
T[ 5] = 40282
T[ 6] = 32909
T[ 7] = 6993
T[ 8] = 36880
T[ 9] = 32764
T[10] = 32800
T[12] = 34816
T[11] = 32640
T[13] = 65536
T[14] = T(2^4-2) = 0

But I did not succeed in proving the LLT for Fermat numbers:

Fn = 2^2^n +1
S[0]=4
S[i]=T[i-1]^2-2
Fn is prime iff S[2^n-2] = 0 (mod Fn)

though experiments have shown that it works up to F13.
Any suggestion ?

[philmoore]

Hi, Tony! I just found a reference that seems to apply to your algorithm. The article is "Biquadratic Reciprocity and a Lucasian Primality Test" by Pedro Berrizbeitia and T. G. Berry in Mathematics of Computation, latest issue, 73(2004), pages 1559-1564. You can retrieve the article at:
http://www.ams.org/journals/mcom/2004-73-247/
I haven't yet read it carefully, but it claims to prove that Lucas tests can be used to prove primality for certain numbers of the form h*2^n +/- 1. For 2^n+1 (h=1), the seed (starting point for the Lucas test) is -5/6 mod 2^n+1, which is equivalent to 3(2^(2^n)-1)/5 for the Fermat number 2^(2^n)+1. Not the same seed you used, but it does at least apparently establish that you can use a Lucas test to prove the primality of a Fermat number!

[T.Rex]

Hi Phil,
Thanks for the reference!
Since I'm just an "amateur", I have no way to access the AMS documents and the subscription for an individual is too high for me. Nevertheless, I was able to find a preprint of the document and I will read it asap.
About Williams' book, I've bought it thru Amazon and I have started to read it. It's a marvellous book, providing many and many useful and clear information. Very valuable! Nevertheless, I think the chapter about Lehmer's work is a little short.
I was working on a proof for: S(0)=5, S(i)=S(i-1)^2-2, Fn=2^2^n+1 is prime iif Fn | S(i-2) when I received the book. I had found a way by using P=sqrt(R) and, though many details were missing, I think I was able to build a proof. Then I found in Williams' book that he did the same (use sqrt(R) instead of an integer) in his Ph D Thesis, but not exactly. So, I was both proud to be able to find it after him and also so sad not to be the first ! The theorems described in Williams' book are not exactly the same as the one I'm working on. So maybe there is some place for me. I'll let you know about my search later. (my wife is saying it's time to lunch!)
Tony

[T.Rex]

I forgot to say:
I don't understand why Mr Ribenboim says in his famous book "Little book for Bigger Primes" that Lucas Sequences are good only for N-1 numbers like Mersenne numbers. Williams' book clearly shows that Lucas Sequences can be used for both N-1 and N+1 numbers, like Fermat numbers. I think Ribenboim wanted to limit the theory to his needs: prove the LLT for Mersenne numbers; but he should clearly say that he's only showing the simpler part of Lucas Sequences theory.
Also, I'd like to say that I think Lucas Sequences and LLT and other primality proofs are only tools for showing a fundamental property of primes: symmetry.
Tony

[T.Rex]

Hi,
In post #7 of this thread: "Why not using Lucas-Lehmer test ?" I proposed to use the LLT (starting with S_0=5) for proving the primality of Fermat numbers. After some search, I was not able to build a proof.
Now, with the help of Mr Williams'book : "Edouard Lucas and primality testing", I thing I have a correct proof. I "just" need to write a LaTeX document with a mathematical proof. That should take several weeks ...

If someone knows that a proof already exists ... I'd like to be warned.

In the same thread post #14, Alex (akruppa) said it is evident that my proposal leads to a test like the Pepin's test. I'm missing the theory underneath. Which book should I read in order to understand Alex' explanations ?

Thanks,
Regards,
Tony

[T.Rex]

Hi,

The draft of the proof is available at: http://tony.reix.free.fr/Mersenne/ : "A LLT-like test for proving the primality of Fermat numbers, based on Lucas Sequences. Proof (.pdf)."

Let me know if you think the proof is correct.

Finally the proof takes only 3 pages, thanks to Lehmer's theorems.

The document is 8 pages long since I provide the Lehmer's theorems plus some proofs and some numerical data .

Tony

[T.Rex]

Hi,

I've found the following vrey interesting paper:
http://202.195.112.2/xsjl/szh/prime3F.pdf
which provides a new proof for the LLT and a new proof for my primality test for Fermat numbers (seed=5), described in the previous posts. Look at top of page 6.
The paper deals with primality test for numbers of the form k2^n+/-1 .

Mister Sun says that he gives a "new primality test for Fermat numbers". That's not true, since I provided my proof before. But maybe someone else proved it before me ! The most important is to make progress and to have more skilled people coming and studying the LLT !

Regards,

Tony

[ewmayer]

Originally Posted by T.Rex

Mister Sun says that he gives a "new primality test for Fermat numbers". That's not true, since I provided my proof before. But maybe someone else proved it before me ! The most important is to make progress and to have more skilled people coming and studying the LLT !

But all other things being equal, establishing priority is important - did you alert him to your work, Tony? Does his paper add anything significnantly new beyond what you proved?

[m_f_h]

Nice finding... (a) of the paper, (b) of the 3 year old thread...
Of course the authors of the paper did several additional things,
and some might say your paper was not really published, and there are so many documents on the web that one cannot check if their content is to be taken seriously, etc. etc... but if they or the referee were readers of this forum, they could have mentioned your results, if not as reference, at least as a comment at the end of the paper...

[T.Rex]

Originally Posted by ewmayer

But all other things being equal, establishing priority is important - did you alert him to your work, Tony?

I sent him an email but then I received an error message. I'll try again.
Since Sun added Remark 3.2 about K. Inkeri who proved the same kind of LLT for Fermats but with a seed of 8, first I think Zhi-Hong did not saw my work, and second if he had knew he would have added a remark, I think.
There are 2 guys in me: one wants the Mersenne/LLT theory to be deeper studied; so Zhi-Hong is welcome ! The other part of me would like to be famous (at least for my children and for the memory of my wife); so I would have be pleased to see a word about me in Sun's paper. But it is mainly my fault: I should have published it in http://arxiv.org/ . I'll do (when I have time ...).

Does his paper add anything significantly new beyond what you proved?

Compared to what I proved: no. The result is exactly the same. The proof is different. Main result is Theorem 3.1 page 5 and he can prove the LLT for Mersennes and the LLT for Fermats. And this is VERY IMPORTANT ! Because many Number Theory books and people divide the primality tests into two categories: the N-1 tests (including the LLT for Mersennes) and the N+1 tests (including the Pépin test for Fermats). My opinion is that LLT can be used for any kind of number and that LLT and Pépin test are equivalent (I proved this for Fermat numbers). But, up to now, I never found a proof that a N-1 number can be proved prime by Pépin's test ... (Reminder: N-1 and N+1 means that N is completely or partially factorized).

About Sun's theorem 3.1 , I cannot say how difficult is the finding of the appropriate (b,c) used by is Theorem. If someone could help ...

Now, we have 3 proofs of this theorem, mine, Gerbicz, and now Sun. Good !

Tony

[T.Rex]

Hi,

I plan to submit my paper (proof of LLT for Fermat, with seed 5) to arXiv.org .
Due to their new rules, and since I never submitted to arXiv, I need an "endorsement from another user to submit a paper to category math.NT (Number Theory)." Paper is available here: http://tony.reix.free.fr/Mersenne/PR...MBERSarXiv.pdf

I've already asked 3 people (I do not know them, but they worked around Mersenne or LLT or Primality proving) who have authority to endorse me, but no answer yet ...

So, if someone in this forum has (or knows someone who has) the authority to endorse me for publishing my paper in arXiv, that would greatly help me !

I've understood the "endorsement guy" does not have to check all the paper. He only has to check that it follows good Maths and LaTeX rules.

Information provided by arXiv.org is available below.
If you agree to endorse me, please follow their instructions:

"(Tony Reix should forward this e-mail to someone who's registered as an endorser for the math.NT (Number Theory) subject class of arXiv.)
Tony Reix requests your endorsement to submit an article to the math.NT section of arXiv. To tell us that you would (or would not) like to endorse this person, please visit the following URL: http://arxiv.org/auth/endorse.php?x=RD7EN8
If that URL does not work for you, please visit http://arxiv.org/auth/endorse.php and enter the following six-digit alphanumeric string: Endorsement Code: RD7EN8 "

Thanks,

Regards,

Tony



Endorsement needed for math.NT

You must get an endorsement from another user to submit a paper to category math.NT (Number Theory).

ArXiv is an openly accessible, moderated repository for scholarly papers in specific scientific disciplines. Material submitted to arXiv is expected to be of interest, relevance, and value to those disciplines. Endorsement is necessary but not sufficient to have a paper accepted in arXiv; arXiv reserves the right to reject or reclassify any submission.

We've sent an email message to tony.reix@XXXXXXXX with a unique endorsement code; please forward this e-mail to someone authorized to endorse you for category math.NT (Number Theory.)

Who is qualified to endorse?

To endorse another user to submit to the math.NT (Number Theory) subject class, an arXiv submitter must have submitted 4 papers to any of math.AC, math.AG, math.AP, math.AT, math.CA, math.CO, math.CT, math.CV, math.DG, math.DS, math.FA, math.GN, math.GR, math.GT, math.HO, math.KT, math.LO, math.MG, math.MP, math.NA, math.NT, math.OA, math.OC, math.PR, math.QA, math.RA, math.RT, math.SG, math.SP or math.ST earlier than three months ago and less than five years ago.

You can find out if a particular person is qualified to endorse by looking up one or more of his papers and clicking on the link "Which of the authors of this paper can endorse?" at the bottom of the abstract.

It would be good for you to find an endorser who is connected with you: for instance, if you're a graduate student, your thesis advisor or another professor in your department would be a good choice. Otherwise, you should choose an endorser whose work is related to the subject of your paper.