Is there a Lucas-Lehmer equivalent test for primes of the form ${3^p-1 \over 2}$?

Question

I'm reviewing the cyclotomic form $f_b(n)= {b^n-1 \over b-1}$ for various properties to extend an older treatize of mine on that form.

With respect to primality there is the Lucas-Lehmer-test for primeness of $f_2(p)$ where of course $p$ itself must be a prime.

I was now looking, whether I can say some things for primes of the form $f_3(p) = {3^p-1 \over 2}$ ,for instance $f_3(3)=13, f_3(7)=1093, f_3(13)=797161, ...$ (more terms see bottom). For this I was looking for a comparable test, similar to the scheme in the Lucas-Lehmer test.

There is a short remark at Weisstein's mathworld involving the concept of Lucas-sequences for a generalized primality test (eq (2) to (4)), of which then the Lucas-Lehmer-test is only a special case, but I could not decode the formulae & recipes into some algorithm.

So Q: Is there a primality test for numbers of the form $f_3(p) = {3^p-1 \over 2}$ similar to the scheme in the Lucas-Lehmer test?

---

More terms for $(3^{a(n)}-1)/2 \in \Bbb P$

 a(n)=[3, 7, 13, 71, 103, 541, 1091, 1367, 1627, 4177,
 9011, 9551, 36913, 43063, 49681, 57917, 483611, 877843 ]

source: OEIS:A028491

Answer 1

There is the basic idea behind the Lucas-Lehmer primality test. For $n= 2^p-1$ we can choose $d= 3$ (quadratic reciprocity) and $\alpha= 2+\sqrt{3}$

If $n$ is prime and $d$ is not a square $\bmod n$ then $$\mathbb{Z}/n\mathbb{Z}[\sqrt{d}] = \{ a+b \sqrt{d}, (a,b) \in \mathbb{Z}/n\mathbb{Z}\}$$ is a field with $n^2$ elements, and its multiplicative group is cyclic with $n^2-1$ elements. If we find an element $\alpha$ of multiplicative order $n+1$ (ie. $\alpha^{n+1} \equiv 1 \bmod n, \alpha^{(n+1)/p} \not\equiv 1 \bmod n $ for every prime divisors $p | n+1$) then $n$ is prime.

(since otherwise with $q$ the least prime divisor of $n$ then $\mathbb{Z}/q\mathbb{Z}[\sqrt{d}]^\times$ is a group with less than $q^2-1 \le n-1$ elements, so the order of $\alpha\bmod q$ can't be $n+1$)

Thus all we need is to know the prime divisors of $n+1$ and compute $\alpha^{(n+1)/p} \bmod n$ for many $\alpha$. The same idea works in $\mathbb{Z}/n\mathbb{Z}$ if we know the prime divisors of $n-1$, and in $\mathbb{Z}/n\mathbb{Z}[x]/(f(x))$ for some irreducible polynomial $f$ of degree $k$ if we know a large part of the factorization of $n^k-1$.

$$\boxed{\ \ \text{Thus it doesn't work for }\ \frac{3^a-1}{2} \quad(\text{but it does for }2\cdot 3^a-1)\ \ }$$

Answer 2

The Lucas-Lehmer Test works for Mersenne numbers and for Fermat numbers. There are 4 proofs, at least, including mine. About your numbers, it will be very difficult to build a proof.

Answer 3

This is not an answer but Lucas-Lehmer test for $(3^p-1)/2$ is maybe possible if you change the starting value and the sequence. I will show you the PRP test I found :

Let the sequence $S_i = 28 \cdot S_{i-1}^3 + 294 \cdot S_{i-1}^2 + 1029 \cdot S_{i-1} + 1197$ with $S_0 = 1197$

Then $(3^p-1)/2$ is prime if $S_{p-2} \equiv 0 (mod (3^p-1)/2)$

I have checked until 10000 with PARI GP and it seems it works for higher exponent

Answer 4

I refer you to Brillhart et al., Factorizations of $b^n\pm1$, published by the American Mathematical Society. The section, Introduction to the Main Tables, subsection Developments Contributing to the Present Tables, subsubsection Developments in Primality Testing, will tell you what methods there are for factoring such numbers.

Answer 5

Having offered and awarded a bounty on this question for effort more than results, after considerable analysis and effort I have come up with a solution - probably.

Given a number of this form $\sum\limits_{k=0}^{P-1}{b^k}$
Where b is an odd Prime , P is Prime

the following primality test can be used to either confirm primality or highly probable primality (I have seen plenty of evidence to suggest the high probability but none to disprove the confirmation). Assume all variables are BigInteger (or equivalent)

initialize with res = $2^b$, test = $\frac{b^P-1}{b-1}$

Repeat P-1 times
{
    res = (res ^ b) Mod(test);
}
if after repeating (res = 2^b)
then test is Prime

So for the case where b = 3, and to answer the question:

Initialize with

res = 8 and test = $\frac{3^P-1}{2}$

Repeat P-1 times
{
    res = (res ^ 3) MOD(test);
}
if after repeating (res = 8)
then test is Prime

I will explain how I came up with this and why I am not at all confident that it proves primality as the Lucas-Lehmer test has been shown to.

My initial aim was to produce an efficient Fermat Primality test for 2, as I had noticed that nearly all (if not all?) numbers of this form with b=3, that passed that test were primes.

So I set out to find an efficient way to calculate $2^N mod(N)$ where N is the sum of powers of 3. Noticing that $2^{3^{n+1}} = {({2^{3^n}}})^3$ where n>0, and being familiar with the repeated squaring method, I recognized this as a candidate for repeated cubing.

However, when I tested this out I was surprised to find that the final phase of this method (i.e. multiplying all remainders mod(N)) was not necessary as the $P^{th}$ element was always 8. The reason for this is unclear to me, but maybe someone can answer this. I was also surprised to find that I could not get the test to fail when tested with a number of different prime bases and for thousands of prime exponents with base 3.

So the questions I would have about this would be:

1. Is this just a shortcut way of doing a Fermat Primality test for witness 2?
2. If it is, is there something special about numbers of this form with odd prime bases that means they are never Fermat Liars for witness 2?
3. Is it just that there are very few such liars around and I, and probably others, have not yet exposed one?

Answer 6

This is not an answer but an extended "comment" (example) to @AlanGee's answer

---

Pari script for testing Lucas-Lehmer-analoguous tests (LLaT) on repunits/q-analogues with $q$ the odd primes up to $q=19$ and $[m]_q$ for prime $m$ up to $399$.
We find the small quirk that the LLaT's are not safe when $m<q$ .
In the script base is $q$ which defines the "generalizations" of the mersernne-numbers, p is the exponent in the generalized "mersenne-numbers" ${\text{base}^{p}-1 \over \text{base}-1}$ or in the notation of $q$-analogues $[p]_\text{base}$

{forprime(base=3,19,
     print("base ",base);print("----------------");
     forprime(p=3,399, 
       test=(base^p-1)/(base-1); \\ repunit of prime length p to be tested

          t0=isprime(test);      \\ t0 indicates primeness by standard primetest            

       cmp=res=2^base; \\ now testing with LLaT
          for(k=1,p-1,res=res^base % test); 
          t1= (res == cmp);  \\ t1 indicates primeness by LLaT

       if((t0==0) && (t1==0),next()); \\ if composite by both tests,
                                      \\ forget it and do next test

       print(dfmt(p,6,0), ": ",t0," ",t1," ",    \\ otherwise print
              if(t0,"is prime","")," :  ",
              if(test<1e16,test,1.0*test) );
      );
      print("========================");
     ); }

Document:

 base 3
     p:t0 t1          : test (or: [p]_base) 
                remark: t0==1 means exact primetest gives "prime", t1==1 LLaT gives "prime"
--------------------------------------------
      3: 1 1 is prime :  13
      7: 1 1 is prime :  1093
     13: 1 1 is prime :  797161
     71: 1 1 is prime :  3.75473325749 E33
    103: 1 1 is prime :  6.95759652988 E48
    - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
    541: 1 1 is prime :  6.63084395472 E257  \\appended on second run. 
   1091: 1 1 is prime :  1.73084789203 E520  \\exact primetest-data t0 taken
   1367: 1 1 is prime :  8.38928997716 E651  \\from [OEIS:A028491][1]
   1627: 1 1 is prime :  9.44607595177 E775   
   4177: 1 1 is prime :  4.30973898516 E1992
   9011: 1 1 is prime :  1.09293990543 E4299
   9551: 1 1 is prime :  4.83140930986 E4556
=============================================
base 5
----------------
      3: 1 0 is prime :  31
      7: 1 1 is prime :  19531
     11: 1 1 is prime :  12207031
     13: 1 1 is prime :  305175781
     47: 1 1 is prime :  1.77635683940 E32
    127: 1 1 is prime :  1.46936793853 E88
    149: 1 1 is prime :  3.50324616081 E103
    181: 1 1 is prime :  8.15663058500 E125
    - - - - - - - - - - - - - - - - - - - - - - - 
    619: 1 1 is prime :  1.14913933997 E432  \\appended on second run.
    929: 1 1 is prime :  5.50901603963 E648  \\exact primetest-data t0 taken
   3407: 1 1 is prime :  6.14815462633 E2380 \\from [OEIS:A004061][2]
  10949: 1 1 is prime :  2.63340395660 E7652
========================
base 7
----------------
      5: 1 1 is prime :  2801
     13: 1 1 is prime :  16148168401
    131: 1 1 is prime :  8.50534611648 E109
    149: 1 1 is prime :  1.38502212710 E125
    - - - - - - - - - - - - - - - - - - - - - - - 
   1699: 1 1 is prime :  1.10514365306 E1435  \\appended on second run.
  14221: 1 1 is prime :  2.29654940319 E12017 \\exact primetest-data t0 taken
                                              \\from [OEIS:A004063][3]
========================
base 11
----------------
     17: 1 1 is prime :  5.05447028499 E16
     19: 1 1 is prime :  6.11590904484 E18
     73: 1 1 is prime :  1.05115319950 E75
    139: 1 1 is prime :  5.67000232522 E143
========================
base 13
----------------
      5: 1 1 is prime :  30941
      7: 1 1 is prime :  5229043
    137: 1 1 is prime :  3.39670648186 E151
    283: 1 1 is prime :  1.46820756272 E314
========================
base 17
----------------
      3: 1 0 is prime :  307
      5: 1 0 is prime :  88741
      7: 1 1 is prime :  25646167
     11: 1 1 is prime :  2141993519227
     47: 1 1 is prime :  4.23622795799 E56
     71: 1 1 is prime :  1.43798195172 E86
========================
base 19
----------------
     19: 1 1 is prime :  1.09912203092 E23
     31: 1 1 is prime :  2.43270318891 E38
     47: 1 1 is prime :  7.01692346601 E58
     59: 1 1 is prime :  1.55306613933 E74
     61: 1 1 is prime :  5.60656876297 E76
    107: 1 1 is prime :  3.72702921316 E135
    337: 1 1 is prime :  4.83828019876 E429
=========================

for base 3 see OEIS:A028491
for base 5 see OEIS:A004061
for base 7 see OEIS:A004063
Note: for high indexes the primetest in the OEIS-lists was often only probabilistic! See details at the OEIS-pages!