Números primos de la forma $(3^n-1)/2$

Question

Problema: tenga en cuenta los números de $P_n =(3^n-1)/2$. Encontrar $n$'s para que $P_n$ es primo. Demuestra que ni $P_{2n}$ ni $P_{5n}$ es primo.

Bono de tarea: Encontrar más números primos $q$ que $P_{q\cdot n}$ no es primo.

Lo que he hecho hasta ahora: he intentado $ q=2,3,5,7,11,13,17,19$. Hasta ahora, cuando $q=2,5,11,17,19$ $n=1$ el valor no es un primo. No quiero calcular más. Así que si alguien me puede ayudar a encontrar el $n$'s para que $P_n$ no es el primer y $q$'s para que $P_{q \cdot n}$.

Si usted puede proporcionar una prueba de que va a ayudar demasiado.

Answer 1

Recordar la factorización $(x^n-1)=(x-1)(1+x+x^2+\cdots x^{n-1})$. Set $x=3^m$ a ver que $3^{mn}-1 = (3^m-1)(1+3^m+3^{2m}+\cdots +3^{(n-1)m})$. Desde $2$ divide $3^m-1$ es una factorización de $P_n$ si $3^m-1>2$$1+3^m+\cdots+3^{(n-1)m}>1$, que es el caso si $m>1$$n>1$, por lo $P_{mn}$ es compuesto si $m>1$$n>1$. Podemos concluir que el $P_n$ solo puede ser la mejor si $n$ es primo.

Dada esta nota que $P_{2n}$ $P_{5n}$ es compuesto si $2n$ $5n$ es compuesto, que es el caso cuando se $n>1$. Sólo queda comprobar el caso $n=1$, pero $P_2=4=2*2$ no es un número primo, y $P_5=121=11*11$, lo $P_5$ es compuesto. Algo interesante que tanto de $P_2$ $P_5$ son cuadrados.

Otra cosa interesante de la nota cuando la comprobación de primalidad de $P_q$ $q$ un primer es que por el teorema de Fermat cualquier número dividiendo $P_q$ debe ser uno más de un múltiplo de $q$, es decir, si $p|P_q$ $p=kq+1$ para algunos entero $k$. Por otra parte, para los impares, números primos $q$, $k$ tendría que ser por $kq+1$ a ser impar (ya que estamos buscando una extraña primer factor de $p$). Por lo tanto solo necesitamos comprobar $2kq+1$. Para $q=5$ tenemos $P_5=121$ y el primer primefactor tenemos que comprobar es 11! $q=7$ da $P_7=1093$. El más pequeño primer factor de $p$ $P_7$ debe satisfacer $p<\sqrt{P_7}=33.1$, pero $2*7+1=15$ es compuesto, por lo que solo necesitamos comprobar si $4*7+1=29$ divide 1093, que no es así. Para $P_{11}=88573$ necesitamos comprobar divisores de a $\sqrt{P_{11}}=297$. Ya que solo necesitamos comprobar los números de la forma $22k+1$ esto significa que en la mayoría tenemos que comprobar 13 números, pero en realidad $88573=23*3851$, por lo que es compuesto.

Me escribió un pequeño programa para buscar el primer $P_q$ número $q$ es el primer y encontrado el siguiente: $$ \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} $$ Mi programa se ejecutó durante un largo tiempo para $q=71$. No podía decidir si $P_{71}$ es primo.

Answer 2

Sugerencia: Que $q\in\mathbb N, q\neq 1$, entonces $$ P_q \text{ is composite } \Leftrightarrow \forall n\in\mathbb N: P_{qn} \text{ is composite}$ $

En otras palabras, cada $q$ encontrará, tal que $P_q$ no es primordial (por ejemplo $q=2,5,11,17,19$) le da una clase de $P_{qn}$, que nunca es primero.

Answer 3

No hay un factor único para cada valor de $n$$b^n-1$. Estos se dividen cada instancia de $b^m-1$ donde $n \mid m$. Uno puede ver en la base 3, que $\frac 12(3^n-1)$ está escrito como una cadena de 1, por ejemplo,$11111$.

Cuando hay un número compuesto de 1 puede ser escrito con cualquier número de divisores, por ejemplo, $111111 = 11 * 10101 = 111 * 21$ El único factor que aparece con cada uno de los prime podría ser calles de una expresión algebraica del factor de $b^n-1$

Esto significa que el único representante de unidades que es de los primeros, son aquellos que tienen un primer número de dígitos. Por supuesto, $11$ $11111$ son ambos cuadrados (2, 11).

Nos encontramos, por ejemplo, 3, 7, 13, en esta lista, la medida de lo $83$. Este es el límite de UBASIC en el momento en que la mesa estaba preparada.

El programa escribí efectivamente probado la algebraica de los factores en orden de tamaño. El primer poder es $b^{t(n)}$ donde $t(n)$ es el de Euler totient de $n$. El siguiente lugar se ordenan por el número de primos divisores de $n$, y más poderes.

Hay muchos más en el primer algebraicas factores, tales como los de esta lista (aumento de tamaño de 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.

Answer 4

Para la primera parte: prueba de descomposición en factores la línea superior de $P_{2n}$ y $P_{5n}$ con diferencia de dos cuadrados y la diferencia de dos quintas partes. Echar un vistazo a más diferencias de dos potencias (tal vez 7) para la segunda parte.

Answer 5

Esto es una adición a mi comentario a la respuesta de @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{matriz} $$ podría extender la lista utilizando el siguiente pequeño Pari/GP-programa:

 {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)

La lista se completó en aproximadamente 5 segundos