1.   A greatly shortened form of my Maple worksheet (extend.mws - the 'extend' refers to extending the conditions of Proth's theorem) in which I made my original numerical observations, which led to my formulating a proposed (but rediscovered) formulation of a generalised Fermat number, and in the process a unification of Fermat and Mersenne numbers. The shortened Maple worksheet may be downloaded here: ex_short.mws (17 KB), and a html format version of it may be downloaded here: ex_short.html (20 KB). Because Maple treats outputs as gif files (and not as simple text) then the html version is slightly bigger than the active mws version.2.    I submitted my paper (now, in Sept 2006, available in pdf format: Fermat_6 (553KB)), 'Could there exist a sixth Fermat prime? I believe it is not impossible', to the American Mathematical Monthly on 19^th 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.3.   The e-mail of 20^th 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 (x^p-1 + x^p-2 + ... + x + 1), evaluated at x = 2^(pⁿ).

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] = 2^{p - 1} + 2^{p - 2} + ... + 2 + 1 = 2^p - 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^(p²) - 1)/(2^p - 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.

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

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, 2², 2³, ... , 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, 2², 2³, ... , 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