Prime numbers and primality testing Yahoo Group Eisenstein Mersenne and Fermat primes =============================================== mikeoakes2@aol.com Message 1 of 1 Dec 24, 2001 ----------------------------------------------- In a posting of 2 Sep 2000 to the Mersenne list (see http://www.mail-archive.com/mersenne@.../msg05162.html) I introduced the "Gaussian Mersennes":- s[n] = (1+i)^n - 1. These now figure as Sequence A057429 in the Sloane On-line Encyclopedia of Integer Sequences (see http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum =057429) And in Chris Caldwell's database (see http://www.utm.edu/research/primes/ftp/all.txt) is to be found the latest prime of this form, which was discovered by Nick Glover in June 2001 and is currently the 45th largest known prime:- 2^364289-2^182145+1 Gaussian Mersenne norm 35 Since Sep 2000, I have been investigating how these ideas carry over into the only other complex quadratic field with more than 2 units, namely k(sqrt(-3)), the field of so-called Eisenstein (or Eisenstein-Jacobi) integers. Note that here there are 6 units, compared with the Gaussian field's 4; and that it is only in fields with more than the standard 2 units (-1 and +1) that this form of generalisation will work.. Write w = -1/2 + sqrt(-3)/2, a primitive cube root of unity: w^3 = +1. (I want to use the normal Greek omega notation, but don't have HTML available.) We are interested in series of the form T[n] = (1-w)^n + u, where n >= 0, and u = -1 or +1. I call these the Eisenstein Mersenne and Fermat numbers. Write n = 12*s + t, where 0 <= t <= 11. **** The "Eisenstein Mersenne" series is: T[n] = (1-w)^n - 1 t T = (1-w)^n - 1 N = norm(T) 0 (3^6s-1) - 1 (3^6s-1) - (3^6s)*w 3^(12s+1) - 3^(6s+1) + 1 2 -1 - (3^(6s+1))*w 3^(12s+2) - 3^(6s+1) + 1 3 -(3^(6s+1)+1) - (2*3^(6s+1))*w 3^(12s+3) + 1 4 -(3^(6s+2)+1) - (3^(6s+2))*w 3^(12s+4) + 3^(6s+2) + 1 5 -(2*3^(6s+2)+1) - (3^(6s+2))*w 3^(12s+5) + 3^(6s+3) + 1 6 -(3^(6s+3)+1) - 7 -(3^(6s+3)+1) + (3^(6s+3))*w 3^(12s+7) + 3^(6s+4) + 1 8 -1 + (3^(6s+4))*w 3^(12s+8) + 3^(6s+4) + 1 9 (3^(6s+4)-1) + (2*3^(6s+4))*w 3^(12s+9) + 1 10 (3^(6s+5)-1) + (3^(6s+5))*w 3^(12s+10) - 3^(6s+5) + 1 11 (2*3^(6s+5)-1) + (3^(6s+5))*w 3^(12s+11) - 3^(6s+6) + 1 We are looking for possible rational integer primes. If n = 0 or 6 mod 12, T is a rational integer, and is divisible by 2. In the other cases, T is not an integer, so we work with N = Norm(T). If n = 3 or 9 mod 12, N is divisible by 2; if n = 2 or 4 or 8 or 10 mod 12, N is divisible by 7; if n = 4 or 8 mod 12, N is also divisible by 13; which leaves as the general case n = 1 or 5 or 7 or 9 mod 12. Note: if n = 1 or 11 mod 12, the middle term in the expression for N occurs with a "-" sign, else with a "+" sign. If n has any proper factor, p say, so that n = p*q, then T = [(1-w)^q)]^p - 1, which is divisible by [(1-w)^q] - 1, and so T, and therefore N, cannot be prime; so n must be prime. The first 23 prime Norms are:- n Formula Description 2 3^2-3^1+1 Eisenstein Mersenne 1 5 3^5+3^3+1 Eisenstein Mersenne 2 7 3^7+3^4+1 Eisenstein Mersenne 3 11 3^11-3^6+1 Eisenstein Mersenne 4 17 3^17+3^9+1 Eisenstein Mersenne 5 19 3^19+3^10+1 Eisenstein Mersenne 6 79 3^79+3^40+1 Eisenstein Mersenne 7 163 3^163+3^82+1 Eisenstein Mersenne 8 193 3^193-3^97+1 Eisenstein Mersenne 9 239 3^239-3^120+1 Eisenstein Mersenne 10 317 3^317+3^159+1 Eisenstein Mersenne 11 353 3^353+3^177+1 Eisenstein Mersenne 12 659 3^659-3^330+1 Eisenstein Mersenne 13 709 3^709-3^355+1 Eisenstein Mersenne 14 1049 3^1049+3^525+1 Eisenstein Mersenne 15 1103 3^1103-3^552+1 Eisenstein Mersenne 16 1759 3^1759+3^880+1 Eisenstein Mersenne 17 2029 3^2029-3^1015+1 Eisenstein Mersenne 18 5153 3^5153+3^2577+1 Eisenstein Mersenne 19 7541 3^7541+3^3771+1 Eisenstein Mersenne 20 9049 3^9049-3^4525+1 Eisenstein Mersenne 21 10453 3^10453-3^5227+1 Eisenstein Mersenne 22 23743 3^23743+3^11872+1 Eisenstein Mersenne 23 Note: the primes up to n=353 are known already to the Cunningham project, on account of the following "Aurifeuillian" factorisation:- 3^(6k-3)+1 = [3^(2k-1)+1]*[3^(2k-1)-3^k+1]*[3^(2k-1)+3^k+1] (see Table 3+ at http://www.cerias.purdue.edu/homes/ssw/cun/pmain501). Apart from this, there seems to be no reference at all in the published literature (or on the Web) to this series of primes. Unfortunately, none of these primes is big enough to make Chris Caldwell's top-5000 database. I found n=23743 in Oct 2000, and since then, nothing, up to (as of now) n=165829. The existence of this _huge_ prime-free stretch (a geometric ratio of nearly 7:1) is surprising, as the Mersennes, and the Gaussian Mersennes also, are better-behaved in this respect, witness the latest Mersenne turning up on cue, almost where expected. **** The "Eisenstein Fermat" series is: T[n] = (1-w)^n + 1 t T = (1-w)^n + 1 N = norm(T) 0 (3^6s+1) - 1 (3^6s+1) - (3^6s)*w 3^(12s+1) + 3^(6s+1) + 1 2 +1 - (3^(6s+1))*w 3^(12s+2) + 3^(6s+1) + 1 3 -(3^(6s+1)-1) - (2*3^(6s+1))*w 3^(12s+3) + 1 4 -(3^(6s+2)-1) - (3^(6s+2))*w 3^(12s+4) - 3^(6s+2) + 1 5 -(2*3^(6s+2)-1) - (3^(6s+2))*w 3^(12s+5) - 3^(6s+3) + 1 6 -(3^(6s+3)-1) - 7 -(3^(6s+3)-1) + (3^(6s+3))*w 3^(12s+7) - 3^(6s+4) + 1 8 +1 + (3^(6s+4))*w 3^(12s+8) - 3^(6s+4) + 1 9 (3^(6s+4)+1) + (2*3^(6s+4))*w 3^(12s+9) + 1 10 (3^(6s+5)+1) + (3^(6s+5))*w 3^(12s+10) + 3^(6s+5) + 1 11 (2*3^(6s+5)+1) + (3^(6s+5))*w 3^(12s+11) + 3^(6s+6) + 1 We are looking for possible rational integer primes. If n = 0 or 6 mod 12, T is a rational integer, and is divisible by 2. In the other cases, T is not an integer, so we work with N = Norm(T). If n = 3 or 9 mod 12, N is divisible by 2; if n = 1 or 5 or 7 or 11 mod 12, N is divisible by 7; if n = 2 or 10 mod 12, N is divisible by 13; which leaves as the general case n = 4 or 8 mod 12. If n has any odd factor, p say, so that n = p*q, then T = [(1-w)^q)]^p + 1, which is divisible by [(1-w)^q] + 1, and so T, and therefore N, cannot be prime; so n must be a power of 2. The first 4 primes are:- n Formula Description 1 3^1+3^1+1 Eisenstein Fermat 0 2 3^2+3^1+1 Eisenstein Fermat 1 4 3^4-3^2+1 Eisenstein Fermat 2 8 3^8-3^4+1 Eisenstein Fermat 3 and for n <= 2^19 there are no others. **** The search for bigger Gaussian and Eisenstein Mersennes is bringing my 2 machines to their knees (Nick Glover is kindly helping with the GM's). So help, anyone, please! I have specially written programs which can pre-seive exponents to a depth of 2^44 (Gaussian) resp. 2^40 (Eisenstein), using the fact that (as for the usual Mersennes and Fermats) prime factors must be of the form 2*k*n+1; and I can supply a range of 5000 (say) in n for testing (with PFGW) if you are interested. Just email me off-list. Each Eisenstein test takes about 50 mins on a 1200 MHz Athlon. Happy Xmas! Mike Oakes =============================================== Cached by Georg Fischer at Nov 14 2019 12:47 with clean_yahoo.pl V1.4