Mathematics">
Tema 3.2 Congruencias
Tema 3.2 Congruencias
Tema 3.2 Congruencias
ARITMÉTICA MODULAR
Tema 3.2. Congruencias
Tema 3.2
Congruencias
Índice de contenidos
1. Aritmética modular ........................................................................................................... 3
2. Elementos inversibles ....................................................................................................... 5
3. La función de Euler. Teoremas de Euler y Fermat ............................................................ 7
4. Resolución de congruencias ............................................................................................. 8
4.1. Congruencias de primer grado .................................................................................... 8
4.2. Sistemas de congruencias lineales............................................................................ 10
Bibliografía ............................................................................................................................. 11
1. Aritmética modular
Definiciones:
Sean a, b y m .
a m b | a b mod m
Ejercicio:
Fijado m , la relación ‘ser congruente módulo m ’ es una relación de equivalencia en .
Compruébalo, basta demostrar que la relación definida por esa propiedad es reflexiva, simétrica y
transitiva.
Observaciones:
Observa que si a b mod m , por definición m | b a .
q b a q·m q b q·m a ,
Entonces, a es el resto que obtenemos de dividir b entre m .
a m r m
Por tanto dado m , para todo a existe un único r tal que r a m r m y además
0 r m.
A éste elemento se le denomina representante distinguido de la clase de equivalencia a m
Observa que dado m , queda dividido en m conjuntos disjuntos que son las clases de
equivalencia módulo m :
Definiciones:
Sea m .
El conjunto
m m 0m , 1m , 2m ,..., m 1m es el conjunto de enteros módulo m .
: m m m |
a , b a b : a b
m m m m m
: m m m |
a , b a · b : a·b
m m m m m
Proposición:
2. Elementos inversibles
Definiciones:
r ·x 1mod m
En tal caso diremos que x es inverso de r y lo denotaremos por r 1
Teorema:
Demostración (Ejercicio)
Para demostrar el teorema hay que demostrar dos implicaciones. Por una parte que si r m es
inversible entonces r y m son coprimos. Para ello basta utilizar la definición y la caracterización de
números coprimos.
Por otra parte, hay que demostrar que si r y m son coprimos entonces r m es inversible. Para
llegar a esta conclusión hay que utilizar el teorema de Bezout.
Corolario:
Ejemplo:
Queremos saber si 31 tendrá inverso módulo 97 y en caso afirmativo calcularlo.
Por tanto mcd 31,97 1 y podemos afirmar que si existe inverso de 31 módulo 97.
1 4 3·1 4 31 4·7
8·4 31 8· 97 31·3 31
97·8 31· 25
Profesora África Domingo 5
Matemática Discreta
Bloque III
ARITMÉTICA MODULAR
Tema 3.2. Congruencias
Observa que hemos tomado como inverso el representante distinguido de la clase de equivalencia
del 4 módulo 97. De esa forma podemos considerar el inverso único por cada elemento inversible.
Por el teorema anterior, el valor de la función de Euler, m coincide con el número de enteros
inversibles en m .
Teorema: Teorema de Euler
Si mcd m, r 1 entonces r
m
1mod m
Demostración: (Ejercicio)
Para demostrar este teorema se toma el conjunto de los elementos inversibles módulo m :
I m x m | x es inversible
Podemos expresar I m de la forma: I m x1 , x2 ,..., x m
Se define el conjunto r ·I m z m | x I m z r ·x mod m y se demuestra que r·I m Im .
Para ello basta demostrar los contenidos en ambas direcciones (Ejercio).
Sea x x1 ·x2 ·...·x m mod m un elemento de m inversible y su inverso mod m :
Como I m r ·I m , el conjunto r ·I m r ·x1 , r ·x2 ,..., r ·x m no es más que una reordenación de
I m x1 , x2 ,..., x m , por lo que:
x x1 ·x2 ·...·x m r ·x1 · r ·x2 ·...· r ·x m r m ·x1 ·x2 ·...·x m r m ·x mod m
4. Resolución de congruencias
4.1. Congruencias de primer grado
Una congruencia de primer grado es una ecuación de la forma:
a·x b mod m
Donde a, b m y x es la incógnita.
Teorema:
Demostración: (Ejercicio)
La demostración es clara a partir de la identidad de Bezout y la definición de congruencias.
Recuerda que se han de demostrar dos implicaciones.
Corolario:
m m m
distintas de forma que si x0 es solución entonces x0 , x0 , x0 2 ,...., x0 d 1 es el
d d d
conjunto de todas las soluciones módulo m .
Demostración: (Ejercicio)
1. Es fácil ver que si mcd a, m 1 , entonces existe a 1 mod m y por tanto
x0 a01 ·b0 m0 ·q
·d
x0 a01 ·b ·d d ·m0 ·q
m mo ·d
m
1
x0 ·d a ·b 0 mod m
0 definición de congruencia
a0 x0 ·d a0 ·a01 ·b 0 mod m
·a0
x0 ·a b mod m
1
De esta forma tenemos que x0 a0 ·b0 mod m0 es una solución de la congruencia ax b mod m
Ejemplo:
Resolver 12·x 6 mod15 .
Como mcd 12,15 3 3 | 6 aplicando el teorema anterior podemos afirmar que la congruencia
tiene solución.
15 12 3 mcd 15,12 3
15 15
13,13 ,13 2· 13,18, 23 13,3,8
3 3
Observa que efectivamente:
Ejercicio:
Resuelve la congruencia 111·x 75 mod 321
x a1 mod m1
x a mod m
2 2
x ak mod mk
Dónde mcd mi , m j 1, si i j .
x a1 mod m1
x a mod m
con mcd mi , m j 1, si i j , tiene solución.
2 2
El sistema de congruencias
x ak mod mk
Además si x y x ' son soluciones del sistema de congruencias entonces x x ' mod M con
M m1 ·m2 ·...·mk .
Demostración:
La demostración de este teorema es constructiva. A partir de ella se pueden definir los pasos a
seguir para resolver un sistema de congruencias.
M
Sea M m1 ·m2 ·...·mk y M i i 1, 2,..., k .
mi
A partir de la identidad de Bezout podemos asegurar que i 1, 2,..., k existen N i , Pi tales
que M i ·N i mi ·Pi 1 .
k
Se tiene que x a ·M ·N
i 1
i i i a1 ·M 1 ·N1 a2 ·M 2 ·N 2 ... ak ·M k ·N k es solución del sistema de
ecuaciones.
Basta observar que M i 0 mod m j si i j y por tanto:
Por otra parte si x y x' son soluciones del sistema de congruencias entonces
Esto significa que mi | x x ' i 1, 2,..., k además como mcd mi , m j 1 si i j , podemos
Ejemplo: (Ejercicio)
Resolver el siguiente sistema de congruencias:
x 3mod11
x 6 mod 8
x 1mod15
Bibliografía
Escario Gil, M. Apuntes Matemática discreta 2005/2006, Universidad San Jorge.
Enderton, H. B. Una introducción matemática a la lógica, ISBM 968-36-0084-0
Grassmann, W.K. y Tremblay J.P. Matemática discreta y lógica, Prentice Hall.