PDF de programación - Teoría de la Divisibilidad

CONGRUENCIAS



BREVE ESQUEMA TEÓRICO

Versión 2016

CONTENIDO

Congruencias ................................................................................................................................................ 1

Breve esquema teórico............................................................................................................................. 1

Contenido ................................................................................................................................................. 1

Introducción ............................................................................................................................................. 2

Números congruentes .............................................................................................................................. 2

Definición.............................................................................................................................................. 2

Propiedades .......................................................................................................................................... 3

Clases de restos ........................................................................................................................................ 4

Estructura algebraica ............................................................................................................................ 4

Exponenciación modular ...................................................................................................................... 6

Sistemas de restos .................................................................................................................................... 7

Teoremas de Euler, Fermat y Wilson.................................................................................................... 7

Restos potenciales .................................................................................................................................... 8

Restos cuadráticos .................................................................................................................................... 9

Símbolo de Legendre .......................................................................................................................... 10

Ley de reciprocidad cuadrática de Gauss ........................................................................................... 10

Criterio de Euler .................................................................................................................................. 11

Ecuaciones y sistemas ............................................................................................................................ 11

El algoritmo extendido de Euclides .................................................................................................... 11

Ecuación lineal en congruencias ......................................................................................................... 12

Sistemas de ecuaciones lineales ......................................................................................................... 13

Ecuaciones polinómicas en Zm ............................................................................................................ 14

Grupos de potencias en Zn ..................................................................................................................... 15



Índice o gaussiano de un resto en Zn ................................................................................................. 15

Subgrupos cíclicos en Zm* ................................................................................................................... 18

Raíces primitivas ................................................................................................................................. 22

Índices modulares .............................................................................................................................. 24

Otros temas relacionados con las congruencias .................................................................................... 27

Números pseudoaleatorios ................................................................................................................ 27

Temas de calendarios ......................................................................................................................... 27

Criterios de divisibilidad ..................................................................................................................... 27

Cálculo con números grandes ............................................................................................................ 28

Dígitos de control ............................................................................................................................... 28

DNI ...................................................................................................................................................... 28

Funciones hash ................................................................................................................................... 29



INTRODUCCIÓN


Todo el tema de congruencias se desarrolla en el conjunto de los números enteros, pero por
simplicidad, y para facilitar el uso con alumnos, haremos mención sólo de los naturales en los
ejemplos, aunque los resultados se generalizan fácilmente.

No se demuestra ningún resultado, ya que el objetivo de estos apuntes es tan solo mostrar un
recorrido breve por los aspectos teóricos más interesantes.



NÚMEROS CONGRUENTES



DEFINICIÓN

Dos números enteros a y b se llaman congruentes respecto a un número natural m llamado
módulo, cuando a - b es divisible entre m, y se escribe a  b (mod m)

También se puede expresar esta situación como que ambos números dan el mismo resto al
dividirlos entre m.





A la relación que se establece entre ambos la llamaremos congruencia.
Por ejemplo, son válidas las congruencias 8  13 (mod 5) 129  229 (mod 100)
Este concepto fue introducido por K.F. Gauss en su obra Disquisitionae Arithmeticae


PROPIEDADES

* Para que sea a  b (mod m) es necesario y suficiente que exista un h entero tal que a = b +
hm.
* Todos los múltiplos de m son congruentes con 0.
* Si ab (mod m) y a es primo con m, también lo será b.
* Si ab (mod m), entonces anbn (mod m)

* Ley de simplificación: si acbc (mod m) y es d el MCD de c y m, se cumple que ab (mod
m/d) (un factor se puede simplificar si el módulo se divide entre su MCD con ese factor)

Esta ley tiene casos particulares interesantes:


 Si n divide a a,b y m, y ab (mod m), se tiene que a/n  b/n (mod m/n)
 Si n divide a a y b y es primo con m, y además ab (mod m), se tiene que a/n  b/n

(mod m)

 Si n divide a a y b y el MCD(n,m)=d, y además b (mod m), se tiene que a/n  b/n

(mod m/d)


* Si ab (mod m) y cd (mod m), entonces:

 a+b  c+d (mod m)
 a-b  c-d (mod m)
 a*b  c*d (mod m)
 ab  cd (mod m)



* Si dos números a y b son congruentes respecto a varios módulos, también lo serán respecto
a su mínimo común múltiplo.

* Dos números congruentes respecto a un módulo presentan el mismo MCD respecto a él.

* Si dos números a y b son congruentes respecto a un módulo m, también lo serán respecto a
todos los divisores de m.

* La congruencia es una relación de equivalencia, porque es:

 Reflexiva: a  a (mod m)
 Simétrica: Si a b (mod m) entonces b  a (mod m)
 Transitiva: Si a  b (mod m) y b  c (mod m) entonces a  c (mod m)



* Si en un polinomio con indeterminada x y coeficientes todos enteros, se sustituyen todos los
elementos dos veces mediante pares de valores congruentes respecto a un módulo, los valores
numéricos resultantes también serán congruentes respecto a ese módulo. Así: 2.22+3.2+7= 21
es congruente con 2.72+3.7+2=121 respecto al módulo 5.

Esta propiedad resume muchas anteriores y permite, por ejemplo, la prueba del 9 en las
operaciones aritméticas.





CLASES DE RESTOS


Si la congruencia es una relación de equivalencia, permitirá clasificar a los números enteros (y
por tanto a los naturales) en clases de equivalencia, conjuntos formados por cada número
entero y todos sus congruentes. En este caso se llaman clases de restos o residuales, porque
cada clase se puede representar por el resto que resulta al dividir cualquier elemento entre el
módulo m.

Las clases módulo m se representan por Z/mZ, o por Zm. Así:

Z2 = {0,1}, que son los dos restos producidos al dividir entre 2. El elemento 0 representa a los
números pares y el 1 a los impares.

Z5 = {0,1,2,3,4}, en la que, por ejemplo el elemento 3 representa a los números 3, 8, 13, 18, 23,
... que dan resto 3 al dividirlos entre 5

La clase Zm contiene exactamente m elementos: {0,1,2,3,...m-1}. A veces se usan restos
mínimos, admitiendo números positivos y negativos, mediante la elección entre a y a-m del
número con menor valor absoluto. Por ejemplo, Z5 se podría representar como {0,1,2,-2,-1}

Vimos en el apartado anterior la compatibilidad de la suma y el producto con la relación de
congruencia:

Si ab (mod m) y cd (mod m) , entonces:

a+b  c+d (mod m)
a*b  c*d (mod m)

Estas dos propiedades nos permiten definir la suma y el producto entre clases de restos:
sumar o multiplicar dos clases equivaldrá a efectuar
los restos
correspondientes a cada clase.

En Informática la función MOD convierte un número en su resto respecto a un módulo dado.
En las hojas de cálculo se usa la función RESIDUO.


la operación entre

ESTRUCTURA ALGEBRAICA

Las clases de restos tienen estructura