2. Matemática discreta


ARITMÉTICA MODULAR

Trabaja con conjuntos de números restringidos a un número determinado. La aritmética modular se introduce inicialmente en el concepto de congruencia.

Sean a y b números enteros y m>0 un número natural. Diremos que a y b son congruentes módulo m si m divide a a-b y se designa como:
                                             a= b (mod m)

                                             a= b + km                   k-número natural
 

ALGORITMO EUCLIDES

Calcula el máximo común divisor de dos números d una manera muy eficiente, sin necesidad de factorizar previamente ambos números.

- Dados dos números n>m, se realiza la división de n entre m.
- Cada paso consiste en una nueva división, en la que el dividendo es el número que actuó de divisor en la división anterior y el divisor es el número que se obtuvo como resto en la división anterior.
- Cuando en una división se obtiene resto nulo, el máximo común divisor de los números de los que partimos será el número que ha actuado como divisor en esa última división efectuada y que resultó ser una división exacta.
 

Si m.c.d.(a,n)=1 entonces a tiene inversa módulo n.

CONJUNTO DE RESIDUOS DE MÓDULO N.               CR={1,......,n-1}

CONJUNTO REDUCIDO DE RESIDUOS DE MÓDULO  N.  Es un subconjunto de CR que contiene todos los elementos primos entre si con n.

FUNCIÓN DE EULER

Se denomina función de euler al cardinal de CRR, es decir el número de enteros positivos "a" tales que 0<a<n y m.c.d.(a,n)=1.
 

TEOREMA DE FERMAT

Es un caso particular del teorema de euler, cuando n es primo.

si p es primo entonces a (elevado a p-1) =1