Loading ...
Sorry, an error occurred while loading the content.

Eisenstein Mersenne and Fermat primes

Expand Messages
  • mikeoakes2@aol.com
    In a posting of 2 Sep 2000 to the Mersenne list (see http://www.mail-archive.com/mersenne@base.com/msg05162.html) I introduced the Gaussian Mersennes :- s[n]
    Message 1 of 1 , Dec 24, 2001
    • 0 Attachment
      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
    Your message has been successfully submitted and would be delivered to recipients shortly.