Fermat 6


I dedicate this page to my friend Wilfrid Keller

" Dr. John Cosgrave's talk on number theory was for many people the best thing they've been to all year. He gave a wonderfully lucid account of his recent discoveries and ideas about Fermat numbers - accessable to all & extremely interesting for those of us (i.e. everyone) who hasn't actually seen a number theorist at work. The talk [which was about the Fermat 6 work on this page] actually managed to stretch on for more than two (very short & extremely enjoyable) hours, and it was well after twelve [midnight] before we let him leave the maths department. "

(Quoted from the Trinity College Dublin (Student) Mathematical Society web site.
Thank you to whoever wrote the above; no bribes were offered!)


This page contains material relating to an e-mail which I sent to the Number Theory mailing list on 5th October 1999, following a question posted by Mingzhi Zhang on 4th October 1999 re primes of the form (2 k + 2 i + 1).

Following this I submitted a paper (now, in Sept 2006, available in pdf format: Fermat_6), 'Could there exist a sixth Fermat prime? I believe it is not impossible', to the American Mathematical Monthly on 19th March 1999, and it was rejected. I have been asked why did I not submit it elsewhere, and the simple answer is that I lacked the emotional energy to do so; my paper made a certain obvious and elementary point, which some open minded people listened to, while others didn't.

The e-mail of 20th March 1999 in which I made an announcement to a few friends and colleagues about my (new, I then thought; see later) unification of Fermat and Mersenne numbers :

From: John B. Cosgrave
To:          ...
Subject: a unification of Mersenne and Fermat numbers
Date: 20 March 1999 22:36

Dear Colleagues (and, in some cases, friends),

I am writing to tell you of some work I have done in recent weeks, which, in a way, unifies into a whole the Fermat and Mersenne numbers. This work may (actually, should) throw doubt on the frequent assertion that the only Fermat primes are the first five (3, 5, 17, 257 and 65537). That was  not, of course, what I set out to do; rather I was just making some routine preparations for my third year Number Theory and Cryptography course (in connection with improving the statement of Proth’s theorem, and its proof, so as to make it more accessible to my students), when a number of things took a turn ... (the actual details are in a paper that I have just completed, and submitted).

Here, then, is my discovered linking of the Mersenne and Fermat numbers (if it is already buried out there in the literature, then obviously I apologise for wasting your time in reading this, and I end up with egg on face. Anyway, at the age of 53 I am not worried anymore about making a fool of myself):

The Mersenne numbers are the M[p] with M[p] = 2^p - 1, p prime; the Fermat numbers are the F[n] = 2^(2^n) + 1, n = 0, 1, 2, 3, 4, 5, ... . Currently there are 37 Mersenne primes (the last three found by George Woltman’s wonderful GIMPS project (< http://www.mersenne.org>), and just those 5 Fermat primes.

I propose (as a pictorial image) that instead of thinking of those two sequences horizontally (as it were), one should *see* the Fermat numbers as being the vertical side, and the Mersenne numbers the horizontal side of the doubly infinite matrix of numbers:

. . . . .
(‘level’ 3)  F[3, 1],     F[3, 2],      F[3, 3],     F[3, 4], ...
(‘level’ 2)  F[2, 1],     F[2, 2],      F[2, 3],     F[2, 4], ...
(‘level’ 1)  F[1, 1],     F[1, 2],      F[1, 3],     F[1, 4], ...
(‘level’ 0)  F[0, 1],     F[0, 2],      F[0, 3],     F[0, 4], ...
              (‘rank’ 1)   (‘rank’ 2)  (‘rank’ 3)    (‘rank’ 4) ...

where the left vertical side is comprised of the Fermat numbers (F[n, 1] = F[n]), the bottom horizontal side is comprised of the Mersenne numbers (F[0, r] = M[p], p the r-th. prime), and the general entry F[n, r] is given by the value of the cyclotomic polynomial (xp-1 + xp-2 + ... + x + 1), evaluated at x = 2^(pn).

Thus the ‘ranks’ are comprised of the numbers:

rank 1: 2^(2^n) + 1 (n = 0, 1, 2, 3, 4, ... ), the Fermat numbers,
rank 2: 2^(2*3^n) + 2^(3^n) + 1 (n = 0, 1, 2, ... ),
rank 3: 2^(4*5^n) + 2^(3*5^n) + 2^(2*5^n) + 2^(5^n) + 1 (n = 0, 1, 2, ... ),

Level 0 is comprised of the numbers {F[0, r]}, and with F[0, r] = 2p - 1 + 2p - 2 + ... + 2 + 1 = 2p - 1, then those are the Mersenne numbers.

I would like to call those at level 1 the ‘first cousins’ of the Mersenne numbers; they are given by

F[1, r] = 2^((p - 1)*p) + 2^((p - 2)*p) + ... + 2^p + 1 ( = (2^(p2) - 1)/(2p - 1))

These {F[n, r]} are (proposed) ‘generalised Fermat numbers’ (though it might be better to call them the Mersenne-Fermat numbers?), and are quite different from the already named ‘generalised Fermat numbers’ (as in, e.g., Hans Riesel’s Prime Numbers and Computer Methods of Factorization), namely the F[n](a, b) = a^(2^n) + b^(2^n), with gcd(a, b) = 1, and a, b of opposite parity.

The {F[n, r]} have the following (easily proved) properties:

1. They satisfy a functional equation (similar to F[0]*F[1]*F[2]*...*F[n-1] + 2 = F[n]),

2. They are pairwise relatively prime (within and across the ranks, meaning: gcd(F[n, i], F[n, j]) = 1, for i <> j, and gcd(F[m, i], F[n, j]) = 1, for m <> n),

3. (the most interesting one, in view of the fact that the Fermat numbers - as known - all pass theLucas-Fermat test to the base 2, and indeed the same was known of the Mersenne numbers)

    Every F[n, r] passes the Lucas-Fermat test to the base 2.

And here, now, is how some doubt must be cast over the belief (?) (assertion?) that the Fermat numbers are all composite after the 5th of them. That belief may be equivalently restated as follows:

a Fermat prime may not follow a Fermat composite
(meaning: if F[n] is composite then F[n+1] is also composite?)

But the Fermat numbers are simply the left vertical side of the above square, and what about the next rank along from it?, and the one alongside it?, and ... . Those numbers (in each rank) are like the Fermat numbers (the only difference is that they grow - of course - so much more quickly in size:

F[5] = F[5, 1] = 2^(2^5) + 1 = 2^32 + 1, has 10 digits,

F[5,2] has 147 digits, F[5,3] has 3763 digits, F[5,4] has 30357 digits,

F[5,5] has 484812 digits, ... ).

Can one not also assert for each of those ranks that a prime may not follow a composite (meaning: if F[n, r] is composite, then F[n, r+1] is also composite)?

But I have found (there is a caveat, below) that at the 17th rank, where F[0, 17] is M[59] (and, as is known - M[59] = 2^59 - 1, is composite) is composite, is followed by the 1031 digit prime F[1, 17].

I have not been able to prove that F[1, 17] is prime by a classical method (say Pocklington, or Selfridge’s ‘change of base theorem’), and those of you who are familiar with such methods will immediately see why (I have explained this point in my paper). Maple (which I use) declares F[1, 17] to be prime, but as you will know that cannot be relied upon for a number of 1031 digits. F[1, 17] passes the Lucas-Fermat test to all prime bases up to 137 (I had to stop somewhere), and passes Miller’s test for the first 25 primes (again I had to stop somewhere), and so is almost certainly prime (if not it will be the first counterexample to the Maple test – but no consolation!!) I have pointed all of this out to the Editor of the journal to which I have submitted my paper, and will (if he is agreeable) submit a request about proving (or disproving) primality to the Number Theory List. In the meantime I would ask you to regard all of the above as being a private communication.

        I hope it has been of some interest to you.
        With best wishes,

4.    Part of Yves Gallot's almost immediate return e-mail to me:

From: Yves Gallot
To: John Cosgrave
Subject: Re: a unification of Mersenne and Fermat numbers
Date: 20 March 1999 23:13

... ... ...

Wilfrid Keller wrote an unpublished paper in 1991: "Factors of Generalized Fermat and Mersenne Numbers".

In 1962, D. Shanks proved a general divisibility theorem for a wide class of numbers denoted:

L_p, m(a, b) = (a^(p^(m+1))-b^(p^(m+1))) / (a^(p^m)-b^(p^m))

Wilfrid Keller studied the L_p, m = L_p, m(2, 1).  L_p, m = (2^(p^(m+1))-1) / (2^(p^m)-1) With his notation, F_m = L_2, m and M_p = L_p, 0.

All the divisors of some L_p, m are of the form 2.h.p^n+1. A lot of factors are related in the paper and today the search of them is being extented with my program.The result " The 1031-digit number L_59, 1 proved to be a probable prime " was also related in the paper. I don’t know if the primality of this number is proved today.

I am sure that Wilfrid Keller will be pleased to give to you more details.

Best Regards,


I wrote to Wilfrid Keller, and I received a very friendly reply from him, together with his fine, unpublished paper.

5.    An e-mail from Francois Morain:

From: Francois Morain
To: John Cosgrave
Subject: Re: a unification of Mersenne and Fermat numbers
Date: 25 March 1999 17:04F[1,17] is prime. It took less than two days on a DecAlpha 500 MHz (V5). The certificate is available on request.

F. Morain

6.   A later e-mail from me:

From: John B. Cosgrave
Subject: a conjectured primality test for Mersenne primes
Date: 13 April 1999 08:38

Dear Colleagues/Friends,

I am writing to all of you since each of you commented in some way on my recent circular note re ‘a unification of Mersenne and Fermat numbers’ (and it was of great value to me to hear from one of you - Yves Gallot - that my proposal was already out there in the literature. YG referred me to an unpublished paper of Wilfrid Keller’s, and in turn Wilfrid’s paper drew my attention to work of Shanks, Ligh and Jones in which my rediscovery was to be found).

I am now circulating the following, just discovered (rediscovered? - please inform me if you think so, and I will just give up), conjectured primality test for Mersenne primes: let ‘p’ be an odd prime, then M[p] ( = 2^p - 1) is prime if and only if 3^((M[p] - 1)/p) = 2^a (mod M[p]), for some non-negative integer ‘a,’ and 2^a < M[p].

I have proved the easy part of that, namely:

if M[p] is prime then 3^((M[p] - 1)/p) = 2^a (mod M[p]), 2^a < M[p].

And here is a proof: First note that the congruence x^p = 1 (mod M[p]) ... (i), has at most p mutually incongruent solutions. Then note that x = 1, 2, 22, 23, ... , 2(p - 1) (mod M[p]) are p mutually incongruent solutions of (i) (this is obvious: just note that 2 p = 1 mod (M[p]), and form all the other powers: i.e., square both sides, cube both sides, etc), and so are the p solutions of (i). (Thus the numbers 1, 2, 22, 23, ... , 2(p - 1) are the p-th roots of unity mod M[p].) Now, by Fermat's 'little' theorem we have 3^(M[p-1] - 1) = 1 (mod M[p]), and since (M[p] - 1)/p is an integer (again by Fermat's 'little' theorem) then 3^((M[p] - 1)/p) is an integer, which is a p-th root of unity mod M[p], and so we have 3^((M[p] - 1)/p) = 2^a (mod M[p]), 2^a < M[p].    

Comment. Of course this is trivial; just replace '3' by any integer 'b,' not divisible by p, and the corresponding result is true. Indeed in the case where b = 2, one has that M[p] = 2 p - 1 passes the Lucas-Fermat test to the base b = 2, even when M[p] is not prime. In short, the conjecture (question, really) is placing a lot of faith in the case where b = 3.

Incidentally, here are the values of ‘a’ for the known values of ‘p’ (up to 44497); I give them as (p, a) pairs:(3, 1), (5, 4), (7, 2), (13, 12), (17, 15), (19, 8), (31, 10), (61, 50), (89, 36), (107, 40), (127, 90), (521, 122), (607, 182), (1279, 599), (2203, 1634), (2281, 672), (3217, 1724), (4253, 813), (4423, 2385), (9689, 5644), (9941, 6272), (11213, 318), (19937, 18742), (21701, 21424), (23209, 19413) and (44497, 44095).This happened in the search for a primality test for the ‘Mersenne-Fermat’ numbers (the F[n, r] of my notation). In my Monthly note I had asked, at the end, this single question: is F[n, r] prime ([n, r] not [0, 1]) if and only if F[n, r] passes Fermat’s test to the base 3 (JB gently chided me for calling this ‘Fermat’s test,’ maintaining that it ignores Lucas’ contribution, and we have agreed to start calling it the Lucas-Fermat test)? I would dearly love to know if that is true, and you will see how the above conjectured Mersenne test is related to my Monthly question.Actually this - in general - is what I now believe to be true:

Let F[n, r] be the ‘level n’, ‘rank r’ Mersenne-Fermat number, and let‘p’ be the r-th prime; then F[n, r] is prime ([n, r] not [0, 1]) if and only if 3^((F[n, r] - 1)/p) = 2^a (mod F[n, r]), for some non-negative integer ‘a,’ and 2^a < F[n, r].(Pepin’s test for the Fermat numbers - F[n] is prime (n not 0) if and only if 3^((F[n] - 1)/2) = -1 (mod F[n])) - is clearly a special case of this; you have to see, e.g., 3^((F[4] - 1)/2) = -1 (mod F[4]) as 3^((F[4] - 1)/2) = 2^16 (mod F[4]) My request to prove the primality of the 1031-digit number F[1, 17], was answered by Francois Morain ("F[1, 17] is prime. It took less than two days on a DecAlpha 500 MHz (V5). The certificate is available on request"). If the above were true, then the primality of F[1, 17] may be established in a minute or so on an ordinary Pentium (my 166MHz), with this computation: 3^((F[1, 17]- 1)/59) = 2^1888 (mod F[1, 17]). (‘1888’ is 59 times 32.)

I hope there is something here to interest you, and I will appreciate any comments (even ones that say, e.g., John, some 12-year old published that in a school Math. mag. in 1872 ... in Kurdish (that is not a slur on Kurdish; rather I hope you know the Erdos limerick ... )). I would especially appreciate comment - about implementation time estimates – from those of you who are experts in the use of the FFT. Of course I would especially appreciate hearing of a proof of the hard part ... .

With best wishes, John

Finally, I received some friendly communications in connection with this, and eventually a rejection of my paper by the Monthly.     

Contact details. jbcosgrave at gmail.com