Encontrar todos los primos que tienen exactamente 8 raíz primitiva

Question

Encontrar todos los números primos $p$ que tiene exactamente 8% raíces primitivas $a$modulo $p$, donde $1\leq a\leq p-1$.

Esto es lo que hice hasta ahora: todos los números primos $p$ tienen una raíz primitiva $a$.

Las otras raíces primitivas son aquellos elementos de la forma $a^i$, que $\gcd(i,p-1)=1$.

Por lo tanto, queremos encontrar todas las $p$ tal que $\phi(p-1)=8$.

Y aquí estoy atrapado...

Answer 1

Vamos a encontrar todos los números naturales $n$ tal que $\phi(n)=8$, entonces vamos a verificar que tienen la propiedad de que $n+1$ es un primo.

Si la factorización prima de $n$$p_1^{a_1}\cdots p_r^{a_r}$, luego $$\phi(n)=\phi(p_1^{a_1})\cdots\phi(p_r^{a_r})=p_1^{a_1-1}(p_1-1)p_2^{a_2-1}(p_2-1)\cdots p_r^{a_r}(p_r-1).$$ La factorización en primos de $8$$2^3$. ¿Cuáles son las posibles maneras en que estos $2$'s pueden ser distribuidas entre los factores en el lado derecho de esta ecuación?

Para romper este más:

• Que el primer potencias $p_i^{a_i-1}$ no aportan nada, pero los poderes de $2$ (y en la mayoría de los que tres de ellos)? (sólo cuando se $p_i=2$ $1\leq a_i\leq 4$ o $p_i$ es algún otro el primer y el $a_i=1$)
• Que los números primos $p_i$ tienen la propiedad de que $(p_i-1)$ no aportan nada, pero los poderes de $2$?
  (sólo cuando se $p_i=3$ o $p_i=5$)

Answer 2

En orden para $\phi(n) = 2^k$ a ocurrir, tenemos $n$ a estar compuesto como $2^{k_0} \prod_i p_i$ donde cada una de las $p_i$ es de la forma $2^{k_i}+1$ (todo esto se sigue de la multiplicativity de $\phi$, véase, por ejemplo, Wikipedia). En el presente caso, $k = 3$.

En primer lugar, se observa que la mayor plenitud de la forma deseada con $k_i \le 3$$5$; y el otro es $3$. Podemos llenar el resto de las partes con algunos factores de $2$. Esto produce:

$$n = 15, 16, 20, 24, 30$$

como soluciones para $p-1$. Llegamos a la conclusión de que $p = 17, 31$ son las únicas soluciones.

Answer 3

Considere la posibilidad de la factorización de $p-1$ a de los números primos : $p-1=2^{b}p_1^{a_1}p_2^{a_2}\ldots p_r^{a_r}$.

A continuación,$\phi(p-1)=2^{b-1}\prod_{k=1}^r \phi(p_k^{a_k})$, pero $\phi(p_k^{a_k})=p_k^{a_k-1}(p_k-1)$. Usted deducir que $p_k-1$ debe dividir $\phi(p-1)=8$, lo $p_k-1$ debe ser uno de $1,2,4$ o $8$, y por lo $p_k$ sólo puede ser $3$ o $5$.

Así que podemos escribir :

$$ p-1=2^{e_2}3^{e_3}5^{e_5} $$

Desde $2$ no es una solución, $e_2>0$. Así

$$ 8=\phi(p-1)=2^{e_2-1}3^{\max(0,e_3-1)}\times 2 \times 5^{\max(0,e_5-1)} \times 4 $$

Si $e_3=0,e_5=0$,$8=2^{e_2-1}$, lo $e_2=4$ y, por tanto,$p=17$.

Si $e_3=0,e_5\gt 0$,$8=2^{e_2-1}5^{e_5-1}\times 4$, lo $p=21$ : no es un prime.

Si $e_3 \gt 0,e_5=0$,$8=2^{e_2-1}3^{e_3-2}\times 2$, lo $p=25$ : no es un prime.

Si $e_3 \gt 0,e_5 \gt 0$,$8=2^{e_2-1}3^{e_3-2}5^{e_5-2}\times 2$, lo $p=31$.

Así que hay exactamente dos soluciones : $p=17$$p=31$.