Matemática Discreta 2

Semana 15

Lunes 15/6:

• Práctico 10, Ejercicio 8. Algoritmo para calcular un generador de $U(p)$ con $p$ primo.
• Logaritmo discreto. Definición.

Miércoles 17/6:

• Criptografía.

Jueves 18/6:

• Criptografía.

Semana 14

Lunes 8/6:

• Lemas 2 y 3 para la prueba de existencia de raíz primitiva módulo $p$, con $p$ primo.
• prueba de la existencia de raíz primitiva modulo $p$, para $p$ primo.

Miércoles 10/6: no hubo clase por paro.

Jueves 11/6:

• prueba de la existencia de raíz primitiva modulo $p^k$, para $p$ primo impar.

Semana 13

Lunes 1/6:

• Prueba del Teorema de Órdenes.
• Corolario del Teorema de Órdenes: si $\text{mcd}(|G|,|K|)=1$, el único homomorfismo $f:G \to K$ es el trivial.
• Definición de Isomorfismo y de grupos isomorfos.
• Práctico 9: Ejercicio 3, partes a y c, Ejercicio 4 y Ejercicio 5.

Miércoles 3/6:

• Práctico 9, ejercicios sobre el grupo de automorfismos de $\mathbb{Z}$ y $\mathbb{Z}_5$.

Jueves 4/6:

• Algoritmo de exponenciación rápida.
• Definición de raíz primitiva.
• Lema 1 para la prueba de existencia de raíz primitiva módulo $p$, con $p$ primo.

Semana 12

Lunes 25/5:

• Teorema de Lagrange.
• Corolario del Teorema de Lagrange para órdenes y grupos cíclicos.
• Teorema de Euler como corolario del Teorema de Lagrange.

Miércoles 27/5:

• Práctico 8, Ejercicios 9 y 11.
• Homomorfismo de grupos.
• Propiedades básicas de homomorfismos.

Jueves 28/5:

• Definición de Núcleo e Imagen de un homomorfismo.
• Homomorfismo inyectivo sii Núcleo trivial.
• Teorema de órdenes (enunciado).
• Caracterización de todos los posibles homomorfismos $f:G \to K$ cuando $G$ es cíclico.

Semana 11

Lunes 18/5:

• Feriado. Batalla de las Piedras.

Miércoles 20/5:

• Definición del orden de un elemento de un grupo.
• Caracterización del orden de un elemento.
• Cálculo del orden de $g^k$ conociendo el orden de $g$.
• El orden de un elemento $g$ coincide con el orden del subgrupo generado por $g$.
• Corolario: grupo es cíclico sii tiene un elemento con orden igual al orden del grupo.
• Corolario: conociendo un generador del grupo, podemos calcular todos los generadores.

Jueves 21/5:

• No hubo clase.

Semana 10

Lunes 11/5:

• Definición de grupo
• Grupo de permutaciones $S_n$.
• Propiedades básicas de los elementos de un grupo.
• Tabla de Cayley de un grupo.
• En cualquier fila o columna de una tabla de Cayley no hay elementos repetidos.

Miércoles 13/5:

• Grupo Diedral $D_n$
• Grupo de enteros módulo $n$ con la suma modular.
• Grupo de invertibles módulo $n$ con el producto modular.

Jueves 14/5:

• Definición de subgrupo.
• Ejemplos de subgrupos.
• Subgrupo generado por un elemento de un grupo.
• Definición de grupo cíclico.

Semana 7

Lunes 20/4:

• Función $\varphi$ de Euler.
• $\varphi (p^k) = p^k - p^{k-1}$, para todo $p$ primo.
• $mcd(m,n)=1$ implica $\varphi(m n) = \varphi(m) \varphi(n)$
• Función de Euler conociendo la factorización en primos.

Miércoles 22/4:

• Teorema de Euler de exponenciación módulo $n$.
• Teorema de Fermat como corolario.
• Aplicación del Teorema de Euler para calcular el resto de una potencia módulo $n$.

Jueves 23/4:

• No hubo clase.

Semana 5

Lunes 6/4

• Repaso de ecuaciones diofánticas lineales: existencia y soluciones.
• Ejercicios del Práctico 3 sobre diofánticas lineales.

Miércoles 8/4

• Definición de congruencia módulo $n$.
• Relación de equivalencia.
• Vínculo con el resto al dividir entre $n$.
• Propiedad cancelativa.
• Dígitos verificadores del ISBN.

Jueves 9/4

• Práctico 5, Ejercicio 1.
• Propiedades de aritmética modular (Proposición 2.3.1 de las notas).
• Ecuaciones con congruencias: existencia y cantidad de soluciones módulo $n$.

Semana 2

Lunes 9/3:

• Cofactores: $a = a^* mcd(a,b)$, $b = b^* mcd(a,b)$, con $mcd(a^*, b^*)=1$.
• $\sqrt{2}$ es irracional (usando corolario del Lema de Euclides).
• Mínimo común múltiplo: definición y relación con el mcd.
• Algoritmo de Euclides extendido.

Miércoles 11/3:

• Práctico 1: divisibilidad.

Jueves 12/3:

• Práctico 1: el juego del polinomio.
• Algoritmo de Euclides extendido versión matricial.
• Ecuaciones diofánticas lineales: existencia de soluciones y cálculo de soluciones (Ejemplo informal).

Semana 1

Martes 3/3:

• Teorema de división entera: $a=b q + r$, con $0 \leq r < |b|$.
• Aplicación: representación de un número en base $b \geq 2$.

Miércoles 4/3:

• Definición de divisibilidad: $m$ divide a $n$.
• Conjunto de divisores de un entero.
• Definición de máximo común divisor (mcd) y algunas propiedades.
• Cálculo del mcd de forma no eficiente: calculando el conjunto de divisores de cada entero y tomando el máximo de su intersección.
• Algoritmo de Euclides para calcular el mcd de forma eficiente. Ejemplo.

Jueves 5/3:

• Algoritmo de Euclides se detiene (gracias al Teorema de división entera). 
• ¿Para qué vamos a usar el mcd?: para buscar soluciones enteras de ecuaciones lineales.
• Igualdad de Bezout y Coeficientes de Bezout.
• Coeficientes de Bezout no son únicos.
• Lema de Euclides (como aplicación de Bezout). Ejemplo de que no siempre ocurre lo que garantiza Euclides.
• Corolario del Lema de Euclides para $p$ primo.