Permutaciones

Una introducci´ n a la teor´a de grupos o ı Noem´ Patricia Kisbye ı Fa.M.A.F Facultad de Matem´ tica, Astronom´a y F´sica a ı ı Universidad Nacional de C´ rdoba o

´ Indice general
Una introducci´ n a la teor´a de grupos o ı 1. Introducci´ n o 2. Congruencias 3. Aritm´ tica Modular e 4. Grupos 5. Grupos c´clicos ı 6. Subgrupos 7. Grupos de Permutaciones 8. Clasificaci´ n de las permutacioneso 9. Permutaciones pares e impares 10. Coclases y el Teorema de Lagrange 11. Automorfismos de un grafo 12. Gu´a de ejercicios ı Bibliograf´a ı 5 6 6 8 10 18 19 20 26 28 33 37 41 45

3

Una introducci´ n a la teor´a de grupos o ı

1. Introducci´ n o

La relaci´ n de congruencia m´ dulo un entero positivo n determina una relaci´ n de equivao o o lencia en el conjunto de los n´ merosenteros. Las operaciones de suma y multiplicaci´ n entera u o inducen operaciones similares entre las clases de equivalencia. Cada una de estas clases se identifica con un elemento del conjunto {0, 1, . . . , n − 1}, al que denotaremos Zn , y este conjunto queda entonces dotado de dos operaciones: suma y multiplicaci´ n m´ dulo n. o o Esto da lugar a la construcci´ n de una familia de estructurasalgebraicas, Zn , que reciben o el nombre de grupos de congruencia. Los grupos, en general, son conjuntos munidos de una operaci´ n que es asociativa, con elemento neutro y en la que cada elemento tiene un inverso o con respecto a dicha operaci´ n. En este texto se desarrolla fundamentalmente los grupos de o congruencias Zn y los grupos de permutaciones Sn como ejemplos de grupos conmutativos y noconmutativos, respectivamente. Se presenta adem´ s la teor´a introductoria a la estructura a ı de grupo, definiendo adem´ s grupos c´clicos, generadores, subgrupos, coclases y el cl´ sico a ı a Teorema de Lagrange. ´ Estas notas fueron escritas inicialmente como parte de los contenidos de un curso de Algebra y Matem´ tica Discreta, dictado en FAMAF en los a˜ os 2001 y 2002, para estudiantes de a n primera˜ o. Al final del texto se ha inclu´do una lista de ejercicios y referencia a bibliograf´a n ı ı complementaria para quien desee profundizar en estos temas. Es mi mayor deseo que estas notas sean utiles, tanto al estudiante como parte de su for´ maci´ n matem´ tica, como al docente en su tarea de formar. Agradezco todas las sugerencias y o a comentarios que permitan mejorar esta presente edici´n. o

2. Congruencias Denotaremos con N y Z a los n´ meros naturales y enteros, respectivamente. Si m y n son u n´ meros enteros, y n = 0 diremos que m divide a n o que n es un m´ ltiplo de m si n = q · m u u para alg´ n entero q. Equivalentemente, si el resto de la divisi´ n de n por m es 0. u o

2. CONGRUENCIAS

7

Se dice que un n´ mero entero p es primo si p es distinto de 1 y de −1 ysus unicos divisores u ´ son p, −p, 1 y −1. Por ejemplo, 2, 3, −11 y 53 son n´ meros primos. Se dice que dos n´ meros u u enteros son coprimos entre s´ si no tienen ning´ n divisor com´ n, excepto el 1 y el −1. Por ı u u ejemplo, 10 y 21 son coprimos entre s´, ya que 2, 5 y 10 no son divisores de 21. Tambi´ n ı e podemos decir que dos n´ meros enteros a y b son coprimos si los primos que aparecenen la u factorizaci´ n de a no aparecen en la factorizaci´ n de b. o o ´ D EFINICI ON 2.1. Dado un n´ mero natural n, decimos que dos n´ meros enteros a y b son u u congruentes m´ dulo n si (a − b) es divisible por n y se escribe o a ≡ b mod (n). Por ejemplo, 27 ≡ 12 mod 5 y − 2 ≡ 16 mod 3

puesto que 27 − 12 = 3 · 5, y −2 − 16 = −18 = (−6) · 3. Notemos que si r es el resto de la divisi´ n por nde un entero a, entonces a es congruente a o r m´ dulo n. Por lo tanto, podemos decir que dos enteros son congruentes m´ dulo n si tienen el o o mismo resto en la divisi´ n por n. o Por ejemplo, 27 y 12 tienen resto 2 en la divisi´ n por 5, mientras que −2 y 16 tienen resto 1 o en la divisi´ n por 3 (notar que −2 = 3 · (−1) + 1). o L EMA 2.2. Si a ≡ b mod (n) y c ≡ d mod (n), entonces a + c ≡ b...