8
$\begingroup$

Problem: Consider the numbers $P_n =(3^n-1)/2$. Find $n$'s for which $P_n$ is prime. Prove that neither $P_{2n}$ nor $P_{5n}$ is prime.

Bonus task: Find more primes $q$ for which $P_{q\cdot n}$ is not prime.

What I have done so far: I have tried $ q=2,3,5,7,11,13,17,19$. So far, when $q=2,5,11,17,19$ and $n=1$ the value isn't a prime. I don't want to calculate any more. So if anyone can help me find the $n$'s for which $P_n$ isn't prime and $q$'s for which $P_{q \cdot n}$.

If you could provide a proof that will help too.

$\endgroup$
4
  • 3
    $\begingroup$ $P_{2n}$ is easy $3^{2n} -1 = (3^{n}-1).(3^{n} +1)$, in $P_{5n}$ case $3^{5n} -1= (3^{n}-1)(3^{4n}+ 3^{3n}+ \ldots+ 1)$. any of the factors are divisible by $2$ and if $n > 2$ they are not trivial. $\endgroup$
    – DBS
    Jul 28 '13 at 23:01
  • $\begingroup$ I highly doubt this is a solved problem... See: primes.utm.edu/glossary/xpage/Repunit.html. This is just the base-3 case... $\endgroup$
    – apnorton
    Jan 26 '14 at 17:23
  • 1
    $\begingroup$ Related: oeis.org/A076481 $\endgroup$
    – apnorton
    Jan 26 '14 at 17:39
  • $\begingroup$ Cf. Cunningham tables $\endgroup$ Aug 26 '19 at 8:21
9
+25
$\begingroup$

Recall the factorization $(x^n-1)=(x-1)(1+x+x^2+\cdots x^{n-1})$. Set $x=3^m$ to see that $3^{mn}-1 = (3^m-1)(1+3^m+3^{2m}+\cdots +3^{(n-1)m})$. Since $2$ divides $3^m-1$ this is a factorization of $P_n$ if $3^m-1>2$ and $1+3^m+\cdots+3^{(n-1)m}>1$, which is the case if $m>1$ and $n>1$, therefore $P_{mn}$ is composite if $m>1$ and $n>1$. We can conclude that $P_n$ can only be prime if $n$ is prime.

Given this note that $P_{2n}$ and $P_{5n}$ is composite if $2n$ and $5n$ is composite, which is the case when $n>1$. It only remains to check the case $n=1$, but $P_2=4=2*2$ is not a prime, and $P_5=121=11*11$, so $P_5$ is composite. Kind of interesting that both of $P_2$ and $P_5$ are squares.

Another interesting thing to note when checking primality of $P_q$ for $q$ a prime is that by Fermat's theorem any number dividing $P_q$ must be one more than a multiple of $q$, i.e. if $p|P_q$ then $p=kq+1$ for some integer $k$. Moreover, for odd primes $q$, $k$ would have to be even for $kq+1$ to be odd (since we are looking for an odd prime factor $p$). Therefore we only need to check $2kq+1$. For $q=5$ we have $P_5=121$ and the first primefactor we have to check is 11! $q=7$ gives $P_7=1093$. The smallest prime-factor $p$ of $P_7$ must satisfy $p<\sqrt{P_7}=33.1$, but $2*7+1=15$ is composite, so we only need to check if $4*7+1=29$ divides 1093, which it does not. For $P_{11}=88573$ we need to check divisors up to $\sqrt{P_{11}}=297$. Since we only need to check numbers of the form $22k+1$ it means that at most we will have to check 13 numbers, but in fact $88573=23*3851$, so it is composite.

I wrote a short program to look for prime $P_q$ numbers when $q$ is prime and found the following: $$ \begin{array}{rr|l} q & P_q & \text{prime or composite} \\ \hline 2 & 4 & 2|P_2\\ 3 & 13 & \text{prime}\\ 5 & 121 & 11|P_5\\ 7 & 1,093 & \text{prime}\\ 11 & 88,573 & 23|P_{11}\\ 13 & 797,161 & \text{prime}\\ 17 & 64,570,081 & 1,871 | P_{17}\\ 19 & 581,130,733 & 1,597 | P_{19} \\ 23 & 47,071,589,413 & 47 | P_{23}\\ 29 & 34,315,188,682,441 & 59 | P_{29}\\ 31 & 308,836,698,141,973 & 683 | P_{31} \\ 37 & 225,141,952,945,498,681 & 13,097,927 | P_{37}\\ 41 & 18,236,498,188,585,393,201 & 83 | P_{41}\\ 43 & 164128483697268538813 & 431 | P_{43} \\ 47 & 13294407179478751643893 & 1223 | P_{47}\\ 53 & 9691622833840009948398361 & 107 | P_{53}\\ 59 & 7065193045869367252382405533 & 14425532687 | P_{59}\\ 61 & 63586737412824305271441649801 & 603901 | P_{61}\\ 67 & 46354731573948918542880962705293 & 221101 | P_{67}\\ 71 & 3754733257489862401973357979128773 & \text{prime}\\ 73 & 33792599317408761617760221812158961 & 11243 | P_{73}\\ 79 & 24634804902390987219347201701063882933 & 432853009 | P_{79}\\ 83 & 1995419197093669964767123337786174517613 & 167 | P_{83}\\ 89 & 1454660594681285404315232913246121223340241 & 179 | P_{89}\\ 97 & 9544028161703913537712243143807801346335324481 & 76631 | P_{97}\\ 101 & 773066281098016996554691694648431909053161283001 & 33034273 | P_{101} \\ \end{array} $$ My program ran for a long time for $q=71$. It couldn't decide whether $P_{71}$ is prime.

$\endgroup$
5
  • 2
    $\begingroup$ Pari/GP says in a blink of a second, that the number at q=71 is prime. $\endgroup$ Jan 26 '14 at 18:51
  • $\begingroup$ OK, let me update the list then. It is definitely not a blink of a second to explicitly divide all the numbers of the form $142 k+1$ up to $\sqrt{P_{71}}$ $\endgroup$
    – Peder
    Jan 26 '14 at 18:55
  • 1
    $\begingroup$ It's a good idea to use Pari/GP, it seems. I've a list for the primes q=5 to 103 gotten in about 5 seconds. Because of the length I've made an explicite answer. $\endgroup$ Jan 26 '14 at 19:06
  • $\begingroup$ @GottfriedHelms: Thanks for the info. I also found online that $P_{103}$ is prime and the next prime is $P_{541}$. The list of smallest $P_p$ that are primes can be found at this link oeis.org/A076481/b076481.txt $\endgroup$
    – Peder
    Jan 26 '14 at 19:29
  • $\begingroup$ As seen in oeis.org/A076481 the sequence of primes $q$ for which $P_q$ is prime goes $q=3,7,13,71,103,541,1091,1367, 1627$. All other values of $q<1627$ gives composite $P_q$. $\endgroup$
    – Peder
    Jan 26 '14 at 19:42
2
$\begingroup$

Hint: Let $q\in\mathbb N, q\neq 1$, then $$ P_q \text{ is composite } \Leftrightarrow \forall n\in\mathbb N: P_{qn} \text{ is composite}$$

In other words, each $q$ you find, such that $P_q$ is not prime (e.g. $q=2,5,11,17,19$) gives you a class $P_{qn}$, which is never prime.

$\endgroup$
2
$\begingroup$

There is a unique factor for every value of $n$ in $b^n-1$. These divide every instance of $b^m-1$ where $n \mid m$. One can see in base 3, that $\frac 12(3^n-1)$ is written as a string of 1's, eg $11111$.

When there is a composite number of 1's it can be written with any of the number's divisors, eg $111111 = 11 * 10101 = 111 * 21$ The unique factor that appears with each prime might be calles an algebraic factor of $b^n-1$

This means that the only rep-units that are prime, are those that have a prime number of digits. Of course, $11$ and $11111$ are both square (2, 11).

We find, eg 3, 7, 13, in this list, as far as $83$. This is the limit of UBASIC at the time the table was prepared.

The program i wrote actually tested the algebraic factors in order of size. The first power is $b^{t(n)}$, where $t(n)$ is the Euler totient of $n$. The next place is sorted by the number of prime divisors of $n$, and any larger powers.

There are many more prime algebraic factors, such as this list (increasing size of prime) 6, 3, 10, 12, 14, 9, 7, 15, 24, 21, 26, 36, 13, 40, 60, 33, 46, 72, 70, 63, 108, 132, 86, 130, 154, 371.

$\endgroup$
1
$\begingroup$

This is an addendum to my comment at the answer of @peder.

$$\small \begin{array} {rrr} \text{prime q} & (3^q-1)/2 & \text{factorization according to Pari/GP}& \text{prime}\\ \hline 5 & 121 & 11^2 & \\ 7 & 1093 & 1093 & * \\ 11 & 88573 & 23.3851 \\ 13 & 797161 & 797161 & * \\ 17 & 64570081 & 1871.34511 \\ 19 & 581130733 & 1597.363889 \\ 23 & 47071589413 & 47.1001523179 \\ 29 & ... & 59.28537.20381027 \\ 31 & . & 683.102673.4404047 \\ 37 & . & 13097927.17189128703 \\ 41 & . & 83.2526913.86950696619 \\ 43 & . & 431.380808546861411923 \\ 47 & . & 1223.21997.5112661.96656723 \\ 53 & . & 107.24169.3747607031112307667 \\ 59 & . & 14425532687.489769993189671059 \\ 61 & . & 603901.105293313660391861035901 \\ 67 & . & 221101.441019876741.475384700124973 \\ 71 & . & 3754733257489862401973357979128773 & * \\ 73 & . & 11243.20149.15768033143.9460375336977361 \\ 79 & . & 432853009.392038110671.145171177264407947 \\ 83 & . & 167.12119.1036745531.950996059627210897943351 \\ 89 & . & 179.1611479891519807.5042939439565996049162197 \\ 97 & . & 76631.2549755542947.48845962828028421155731228333 \\ 101 & . & 33034273.465092326319.50316775668019759306202964023 \\ 103 & . & 6957596529882152968992225251835887181478451547013 & * \end{array} $$ You might extend the list using the following small Pari/GP-program:

 {myfac(n) = local(f,s,p,e,t);
   f=factor(n); 
   s="";
   for(r=1,rows(f),  
         p=f[r,1];
         e=f[r,2];
         t=if(e>1,Str("^",e),""); 
         s=Str(s,  if(r>1,".",""),p,t)
       );
    return(s); }


    list = vectorv(25) 
    for(q=3,27, p =prime(q); m=(3^p-1)/2;  list[q-2] = [p, m, myfac(m)]);   
    list=Mat(list)

The list was completed in about 5 seconds

$\endgroup$
1
  • 1
    $\begingroup$ Very cool. I found a neat list of the first few values of $P_q$ for which $P_q$ is prime here oeis.org/A076481 $\endgroup$
    – Peder
    Jan 26 '14 at 19:44
0
$\begingroup$

If you're looking for larger terms,

$(3^n-1)/2$ is prime for $n = 3, 7, 13, 71, 103, 541, 1091, 1367, 1627, 4177, 9011, 9551, 36913, 43063, 49681, 57917, 483611, 877843, 2215303$.

See https://oeis.org/A028491.

Note that some of the larger $n$'s may only correspond to probable primes (still almost certain to prime however).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.