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