Probar si $n$ tiene una raíz primitiva, entonces tiene exactamente $\phi(\phi(n))$

Question

Probar si $n$ tiene una raíz primitiva, entonces tiene exactamente $\phi(\phi(n))$.

Que $a$ sea la raíz primitiva entonces sé que otras raíces primitivas será entre $\{a,a^2,a^3 \cdots\cdots a^{\phi(n)} \}$ pues cualquier otro número congruente módulo $n$ a uno de estos. Entonces me di cuenta de que la respuesta es $\phi(\phi(n))$ $a^k$ raíz primitiva, $k$ debe ser coprimo con $\phi(n)$. Pero no sé la razón. ¿Me estoy perdiendo cualquier punto tonto?

Answer 1

Sugerencia: Si $G$ es un grupo cíclico de orden $n$ generado por un elemento $g$, entonces el orden del elemento $g^m$ es $n/\gcd(m,n)$ (si has visto este resultado poco después introdujeron grupos cíclicos). En particular $g^m$ es del orden de $n$, si y sólo si $\gcd(m,n)=1$.

Answer 2

Como usted ha señalado, si $g$ es una raíz primitiva de $n \ge 3$, entonces las raíces primitivas debe ser entre $g, g^2, \dots, g^{\varphi(n)-1}$.

Para contar el número exacto, como se observa, tenemos que mostrar que para $1 \le k \le\varphi(n)-1$, $g^k$ es una raíz primitiva iff $k$ es relativamente primer a $\varphi(n)$.

Supongamos que $k$ es relativamente primer a $\varphi(n)$. Entonces existen enteros $x$ $y$ tal que $xk=y\varphi(n)+1$. De ello se desprende que $(g^k)^x=(g^{\varphi(n)})^y g\equiv g\pmod{n}$. Desde $g^{kx}\equiv g\pmod{n}$, para cualquier $e$ hemos $$g^e\equiv (g^{kx})^e\equiv (g^k)^{xe}\pmod{n}.$$ De ello se sigue que cualquier potencia de $g$ es congruente con algún poder de $g^k$. Esto implica que $g^k$ es una raíz primitiva de $n$.

Por otro lado, si $k$ no es primo relativo a $\varphi(n)$, vamos a $d \gt 1$ ser un divisor común. A continuación,$(g^k)^{\varphi(n)/d}\equiv 1\pmod{n}$, ya que el $k\varphi(n)/d$ es un múltiplo de a $\varphi(n)$. De ello se desprende que $g^k$ orden $\le \varphi(n)/d$, por lo que no puede ser una raíz primitiva.

Answer 3

$a^k$ A ser una raíz primitiva, tienes que mostrar que $1,a^k,a^{2k},\dots,a^{(\phi(n)-1)k}$ son diferentes (modulo $n$). Por lo tanto, demuestran que si $\gcd(k,\phi(n))\ne1$ entonces estos números no son diferentes (forma más fácil es que muestra 1 se repite) y muestran que si el MCD es 1 entonces los números son todos distintos.

Answer 4

Si $a^k$ es primitivo, entonces para cualquier $m$ tenemos algunos $t$ tal que $a^m=(a^k)^t=a^{tk}$, lo $tk\equiv m\mod \phi(n)$. Si $k$ $\phi(n)$ había mcd $c$, $m=t(k/c)c+x(\phi(n)/c)c$ algunos $t,x$ por lo tanto es divisible por $c$. Si dejamos $m=1$ tenemos que $c=1$, lo $k$ $\phi(n)$ son coprime.

Por otro lado, si $k$ $\phi(n)$ son coprime a continuación tenemos algunos de los $t$ tal que $tk\equiv 1\mod \phi(n)$, lo que para cualquier $m$ tenemos $mtk\equiv m\mod \phi(n)$$(a^k)^{mt}=a^m$. Por lo tanto $a^k$ es una raíz primitiva.

Por lo tanto no es un bijection entre el conjunto de raíces primitivas y el conjunto de los enteros positivos a menos de $\phi(n)$ y coprime, de los cuales hay $\phi(\phi(n))$. Por lo tanto, hay $\phi(\phi(n))$ raíces primitivas.