Digamos que tiene de $G$ $1000$ elementos. Sin crear bucles en cada $g^m$, ¿cómo puedo mostrar que $g$ es un generador? Yo he deducido que debo demostrar que la orden de $g = N$, o en este caso $1000$, pero no estoy seguro de cómo ir sobre esto. Cualquier ayuda es apreciada. ¡Gracias!
Respuestas
¿Demasiados anuncios?
Jean-François Corbett
Puntos
16957
La teoría general que se ha dado en otra respuesta, pero en mi humilde opinión este es uno de esos resultados, donde un ejemplo concreto que hace la teoría mucho más fácil de entender.
Así, supongamos que usted tiene un elemento $g$ de un grupo de $G$ donde $|G|=1000$. Quiere saber si o no $g$ orden $1000$.
Primero de todos, usted sabe que el orden de las $g$ es un factor de $|G|$, y así los posibles valores de la orden son $$1000,\,500,\,250,\,200,\,125,\,100,\,50,\,40,\,25,\,20,\,10,\,8,\,5,\,4,\,2,\,1\,.$$ Queremos descartar las posibilidades $$500,\,250,\,200,\,125,\,100,\,50,\,40,\,25,\,20,\,10,\,8,\,5,\,4,\,2,\,1\,.$$ Así, supongamos que hemos comprobado que $500$ no funciona, es decir, hemos comprobado $g^{500}\ne e$. (Podemos pensar en más adelante acerca de cómo hacer esto de manera eficiente, por ahora vamos a decir que nos hemos hecho.) El punto es que ahora no es necesario para comprobar que el $g^{250}\ne e$; la de si $g^{250}$ fueron para la igualdad de $e$ entonces tendríamos $g^{500}=e^2=e$; y ya hemos comprobado que esto no es cierto. De la misma manera, no necesitamos de verificación $125,100,50,25,20,10,5,4,2,1$ lo que nos deja con $$200,\,40,\,8\,.$$ Así, compruebe que el $g^{200}\ne e$; después por las mismas razones antes mencionadas, no necesitamos de verificación $40$ o $8$.
Así que lo que se pretende es: $g$ es un generador de $G$ si y sólo si $$g^{500}\ne e\quad\hbox{and}\quad g^{200}\ne e\ .$$ Si usted piensa cuidadosamente debe ver cómo esto le da a la regla general, como se indica en otras respuestas: $g$ es un generador de un grupo de $n$ elementos si para cada factor primordial $p$ $n$ tenemos $g^{n/p}\ne e$.
Haciendo el problema de la "obvia", tendríamos $999$ cosas para ver: como es, sólo dos!
Usted puede hacer los cálculos necesarios por las reiteradas cuadrar y las técnicas relacionadas con: en este caso se podría calcular sucesivamente $$\eqalign{g^2&=(g)(g)\cr g^4&=(g^2)^2\cr g^5&=(g^4)g\cr g^{10}&=(g^5)^2\cr g^{20}&=(g^{10})^2\cr g^{40}&=(g^{20})^2\cr g^{50}&=(g^{40})g^{10}\cr g^{100}&=(g^{50})^2\cr g^{200}&=(g^{100})^2\cr g^{400}&=(g^{200})^2\cr g^{500}&=(g^{400})g^{100}\ ,\cr}$$ un total de $11$ cálculos para mostrar que $g$ es un generador.
jwarzech
Puntos
2769
Si los factores primos de a $|G| = N$ son conocidos, entonces uno puede probar $g^m \neq e$ (donde $e$ significa que el elemento de identidad del grupo $G$) por un relativamente pequeño subconjunto de los posibles exponentes. Es decir, uno quiere demostrar que $g^m \neq e$ por cada $m = N/p$ donde $p$ se ejecuta a través de la principal divisores de $N$.
Tenga en cuenta que sabremos automáticamente $g^N = e$. Así que el objetivo es demostrar que no hay una buena divisor $D$ $N$ también servir para lograr el $g^D = e$. Esta conclusión se deduce de lo que queremos mostrar por encima, por si $D$ fueron una adecuada divisor de $N$, a continuación, algunos divisor primo de $N$ tiene más repetidas factores en $N$$D$. Deje $p$ ser un divisor primo de $N$. De acuerdo con el criterio anterior, $D$ divide $N/p$. Pero si $g^{N/p} \neq e$, no puede ser el caso de que $g^D = e$ (debido a $D$ divide $N/p$).
