Una pregunta sobre grupos cíclicos.

Question

¿Cómo se puede ver que el grupo cíclico$C_n$ de orden$n$ tiene$\phi(d)$ elementos de orden$d$ para cada divisor$d$ de$n$?

(donde$\phi(d)$ es la función principal de Euler)

Answer 1

Deje $g$ ser un generador de $C_n$. ¿Cuál es el orden de $g^a$?

$(g^a)^k = g^{ak} = 1$ si y sólo si $n|ak$. Pero $$\begin{align*} n|ak &\Longleftrightarrow n|ak\text{ and }a|ak\\ &\Longleftrightarrow \mathrm{lcm}(n,a)|ak\\ &\Longleftrightarrow a\left.\left(\frac{n}{\gcd(a,n)}\right) \right| ak\\ &\Longleftrightarrow \left.\frac{n}{\gcd(a,n)} \right|k \end{align*}$$ de modo que el orden de $g^a$ es exactamente $\displaystyle \frac{n}{\gcd(a,n)}$.

Así que usted está tratando de contar el número de enteros $a$, $0\leq a \lt n$, tal que $n = d\gcd(a,n)$.

Añadido. Alternativamente, si usted puede demostrar que un grupo cíclico de orden $n$ tiene un único subgrupo de orden $d$ al $d|n$, y no hay subgrupos de orden $d$ al $d$ no divide $n$, a continuación, gire el problema en la búsqueda de cómo muchos de los generadores del grupo cíclico de orden $d$, lo que da th resultado de inmediato.

Answer 2

La recuperación $\rm\:g^i\:$ tiene un pedido$\rm\: n/(i,n)\ $ para un generador$\rm\:g\:$ de$\rm\ C_n\:.$

Por lo tanto $\rm\ \ \displaystyle\ \ d\ =\ \frac{n}{(i,n)},\quad\ \ 0 \le i \le n$

$\rm\quad\displaystyle\iff\quad\ \ \ (i\:d,\ nd)\ =\ n,\ \ \ \ 0 \le i \le n$

$\rm\quad\displaystyle\iff\quad \bigg(\frac{i\:d}{n},d\bigg)\ =\ 1,\ \ \ \ \: 0 \le i \le n,\ \ n\ |\ i\:d$

$\rm\quad\displaystyle\iff\quad\quad\ (\ j,\ d)\ \ =\ \ 1, \ \ \ \ \:0\le j \le d$