P4-Aritmética Modular PDF

Preview

Summary

Teoría...

Description

Teoría de Números Aritmética Modular Mariam Cobalea Universidad de Málaga Dpto. de Matemática Aplicada

Curso 18/19

Mariam Cobalea (UMA)

Matemática Discreta, Curso 18/19

Teoría de números. Aritmética modular

1 / 72

Aritmética Modular Congruencia módulo m

Dos números enteros son congruentes módulo m si su diferencia es un múltiplo de m. El lenguaje de las congruencias fué introducido al final del siglo XV III por Gauss (1777-1855). Definición 1 (Congruencia módulo m ) Sean a, b, m 2 Z, tales que m > 1. Se dice que a es congruente con b módulo m si y sólo si (a  b) es múltiplo de m. Se denota a⌘b

(mód m)

Ejemplo 1 (i) 23 ⌘ (ii) 12 ⌘

17 14

(mód 3), ya que (mód 13), ya que

23  17 = 6 = 2 · 3  12  14 = 26 = (2)13

* a ⌘ b (mód m) si y sólo si existe k 2 Z tal que a = b + km Mariam Cobalea (UMA)

Matemática Discreta, Curso 18/19

Teoría de números. Aritmética modular

2 / 72

Aritmética Modular Congruencia módulo m

Las congruencias surgen a menudo en la vida diaria: Los relojes trabajan (mód 12) ó (mód 24) para las horas y (mód 60) para los minutos y segundos. Los calendarios trabajan (mód 7) para los días de la semana y (mód 12) para los meses. Los odómetros trabajan

(mód 1,000,000)

Ejercicio Demuestra que: 1

en años no bisiestos el mes de enero coincide con el mes de octubre;

2

en años bisiestos el mes de enero coincide con el mes de julio. Mariam Cobalea (UMA)

Matemática Discreta, Curso 18/19

Teoría de números. Aritmética modular

3 / 72

Aritmética Modular Congruencia módulo m

Teorema 1 Sean a, b, m 2 Z, tales que m > 1. Entonces a ⌘ b (mód m) si y sólo si a y b tienen el mismo resto al dividirse entre m. Ejemplo 2 58 ⌘ 23 (mód 5) ()

(

58 = 5 · 11 + 3, 23 = 5 · 4 + 3,

03 1. La congruencia módulo m verifica las propiedades: Reflexiva: a ⌘ a (mód m) Simétrica: Si a ⌘ b (mód m), entonces b ⌘ a (mód m) Transitiva: Si a ⌘ b (mód m) y b ⌘ c (mód m), entonces a ⌘ c (mód m) * Del teorema anterior se deduce que la congruencia módulo m es una relación de equivalencia definida en Z. Por tanto, establece una partición en Z.

Mariam Cobalea (UMA)

Matemática Discreta, Curso 18/19

Teoría de números. Aritmética modular

5 / 72

Aritmética Modular Propiedades de las congruencias

Cada clase de equivalencia definida por la relación de congruencia módulo m se denota [a]m y se denomina clase a módulo m [a]m = {b 2 Z | b ⌘ a

(mód m)}

Por lo tanto, como consecuencia de las propiedades anteriores: a ⌘ b (mód m)

()

[a]m = [b]m

El conjunto cociente, es decir, el conjunto formado por todas las clases de equivalencia se denota Zm . Y teniendo en cuenta los teoremas anteriores, el conjunto Zm tiene exactamente m elementos: Zm = {[0]m , [1]m , [2]m , . . . , [m  1]m } Mariam Cobalea (UMA)

Matemática Discreta, Curso 18/19

Teoría de números. Aritmética modular

6 / 72

Aritmética Modular Propiedades de las congruencias

Ejemplo 3 27 = 3 + 4 · 6 () 27 ⌘ 3 (mód 4) () [27]4 = [3]4 Ejemplo 4 Las cuatro clases de la congruencia módulo 4 son: [0]4 = {. . . , 8, 4, 0, 4, 8, . . . } [1]4 = {. . . , 7, 3, 1, 5, 9, . . . } [2]4 = {. . . , 6, 2, 2, 6, 10, . . . } [3]4 = {. . . , 5, 1, 3, 7, 11, . . . } n o Z4 = [0]4 , [1]4 , [2]4 , [3]4 Mariam Cobalea (UMA)

Matemática Discreta, Curso 18/19

Teoría de números. Aritmética modular

7 / 72

Aritmética Modular Aritmética de las congruencias

Teorema 4 (Aritmética de las congruencias Sean a, b, c, m 2 Z,

m>1

1

a + c ⌘ b + c (mód m)

2

a  c ⌘ b  c (mód m)

3

a · c ⌘ b · c (mód m)

II )

tales que a ⌘ b (mód m). Entonces:

Ejemplo 5 Para a = 20 , b = 6, c = 2 y m = 7 tenemos que: 20 ⌘ 6 Aplicando el teorema, resulta: 8 > 20 + 2 ⌘ 6 + 2 < (i) (ii) 20  2 ⌘ 6  2 20 ⌘ 6 (mód 7) =) (iii) 20 · 2 ⌘ 6 · 2 Mariam Cobalea (UMA)

> :

Matemática Discreta, Curso 18/19

(mód 7).

9 (mód 7) > = (mód 7) (mód 7)

Teoría de números. Aritmética modular

> ;

8 / 72

Aritmética Modular Aritmética de las congruencias

Hemos visto que al sumar, restar o multiplicar por un entero ambos lados de una congruencia se preserva la congruencia. ¿Qué sucederá cuando dividimos ambos lados de la congruencia por un número? ¿Se conserva la congruencia? Ejemplo 6 2 · 9 ⌘ 2 · 3 (mód 12), pero 96⌘3 (mód 12). Con este ejemplo comprobamos que no se preserva la congruencia al dividir ambos lados por un entero. Sin embargo, los siguientes teoremas nos enseñan cómo se pueden simplificar las congruencias. Mariam Cobalea (UMA)

Matemática Discreta, Curso 18/19

Teoría de números. Aritmética modular

9 / 72

Aritmética Modular Aritmética de las congruencias

Teorema 5 (Aritmética de las congruencias

III )

Sean los enteros a, b, c, m 2 Z, m > 1. Si a · c ⌘ b · c (mód m · c), entonces a ⌘ b (mód m) Demostración: Ya que a · c ⌘ b · c (mód m · c), existe k 2 Z, tal que a · c  b · c = k · m · c. Luego, a · c  b · c = k · m · c () a  b = km () a ⌘ b (mód m) Ejemplo 7 2 · 9 ⌘ 2 · 3 (mód 12) =) 9 ⌘ 3 (mód 6) 66 ⌘ 30 (mód 18) =) 11 ⌘ 5 (mód 3) 51 ⌘ 21 (mód 15) =) 17 ⌘ 7 (mód 5) Mariam Cobalea (UMA)

Matemática Discreta, Curso 18/19

Teoría de números. Aritmética modular

10 / 72

Aritmética Modular Aritmética de las congruencias

Teorema 6 (Aritmética de las congruencias m > 1, ⇣ ⌘ m entonces a ⌘ b (mód ) d Sean a, b, c, d, m 2 Z,

III I )

d = mcd(c, m). Si a · c ⌘ b · c (mód m),

a · c ⌘ b · c (mód m) d = mcd(c, m)

)

=) a ⌘ b (mód

⇣m⌘ d

)

Ejemplo 8 Simplifica la congruencia

9 · 6 ⌘ 4 · 6 (mód 15).

15 = 6 · 2 + 3 6 = 3·2 9·6⌘ 4·6 Mariam Cobalea (UMA)

)

=) mcd(6, 15) = 3

(mód 15) =) 9 ⌘ 4 Matemática Discreta, Curso 18/19

(mód

15 ) 3

Teoría de números. Aritmética modular

11 / 72

Aritmética Modular Aritmética de las congruencias

Demostración: a · c ⌘ b · c (mód m) () Existe k 2 Z, a · c  b · c = km

(1)

Dividiendo ambos lados de (1) por

d, tenemos ⇣c⌘ ⇣ m⌘ (a  b) =k d d ⇣ ⌘ ⇣ ⌘ m c y De aquí, por ser coprimos , se sigue que d d ⇣ m ⌘  (a  b) d Por tanto,

a ⌘ b (mód Mariam Cobalea (UMA)

⇣m⌘ d

Matemática Discreta, Curso 18/19

) Teoría de números. Aritmética modular

12 / 72

Aritmética Modular Aritmética de las congruencias

Corolario 7 Sean a, b, c, m 2 Z, m > 1 con mcd(c, m) = 1. Si a · c ⌘ b · c (mód m), entonces a ⌘ b (mód m). Ejemplo 9 Simplifica la congruencia

234 ⌘ 24 (mód 35).

234 = 39 · 6 35 = 6 · 5 + 5 6 = 5·1+ 1 5 = 1·5 234 ⌘ 24

24 = 4 · 6 9 > =

=) mcd(35, 6) = 1

> ;

(mód 35) =) 39 ⌘ 4

Mariam Cobalea (UMA)

Matemática Discreta, Curso 18/19

(mód 35)

Teoría de números. Aritmética modular

13 / 72

Aritmética Modular Aritmética de las congruencias

En los conjuntos Zm podemos definir la suma, la resta y el producto. Estas operaciones están justificadas por el siguiente resultado. Teorema 8 (Aritmética básica de las congruencias Sean a, b, c, d, m 2 Z, entonces:

IIV )

m > 1. Si a ⌘ b (mód m) y

1

a + c ⌘ b + d (mód m)

2

a  c ⌘ b  d (mód m)

3

a · c ⌘ b · d (mód m)

c ⌘ d (mód m),

Ejemplo 10 18 −2

≡ ≡

6 10

(mód 12) (mód 12)

Mariam Cobalea (UMA)

)

8 > < (i) =⇒ (ii) (iii) > :

18 + (−2) 18 − (−2) 18 · (−2)

Matemática Discreta, Curso 18/19

≡ ≡ ≡

6 + 10 6 − 10 6 · 10

9 (mód 12) > = (mód 12) (mód 12)

Teoría de números. Aritmética modular

> ;

14 / 72

Aritmética Modular Aritmética de las congruencias

Demostración: „ La demostración del teorema anterior es una simple comprobación: 8 ) > < a + c = b + d + m(k1 + k2 ) a = b + m · k1 a  c = b  d + m(k1  k2 ) =) > c = d + m · k2 : a · c = b · d + m(d · k1 + b · k2 ) Este teorema justifica que las siguientes operaciones en Zm están bien definidas [a]m +m [b]m = [a + b]m

[a]m ·m [b]m = [a · b]m

Estas propiedades permitirán trabajar más eficientemente con congruencias. Mariam Cobalea (UMA)

Matemática Discreta, Curso 18/19

Teoría de números. Aritmética modular

15 / 72

Aritmética Modular Aritmética de las congruencias

Corolario 9 Si a ⌘ b (mód m), entonces ak ⌘ bk (mód m). Demostración: Se puede demostrar aplicando reiteradamente el teorema anterior y usando inducción. También se puede dar una demostración directa, como hacemos a continuación. „ Por ser a ⌘ b (mód m), tenemos que m

es un divisor de

a  b.

„ Por otra parte, sabemos que para todo k 2 Z+ ak  bk = (a  b)(ak−1 + ak−2 b + · · · + abk−2 + bk−1 ) „ Así, m

también es divisor de

„ Por tanto,

ak  bk .

ak ⌘ bk (mód m).

Mariam Cobalea (UMA)

Matemática Discreta, Curso 18/19

Teoría de números. Aritmética modular

16 / 72

Aritmética Modular Aritmética de las congruencias

Ejercicio Encuentra el resto de dividir 328 entre 11. Aplicando el teorema y el corolario anterior 32 ≡ −2

(mód 11) =⇒ 34 ≡ 4

(mód 11) =⇒ 3 · 34 ≡ 3 · 4

(mód 11)

Luego, 35 ⌘ 1 (mód 11). De donde, 325 ⌘ 15 (mód 11). Por otra parte, 32 ⌘ 2 (mód 11) =) 3 · 32 ⌘ 3 · (2) (mód 11) Así, 33 ⌘ 5 (mód 11). Aplicando el teorema 25

3 33

⌘ ⌘

1 5

5

(mód 11) (mód 11)

)

=) 328 ⌘ 5

(mód 11)

Por lo tanto, el resto de dividir 328 entre 11 es 5. Mariam Cobalea (UMA)

Matemática Discreta, Curso 18/19

Teoría de números. Aritmética modular

17 / 72

Aritmética Modular Aritmética de las congruencias

¿Cómo combinar congruencias de dos números con diferentes módulos? Teorema 10 Sean a, b, m1 , m2 , . . . , mk enteros, donde cada mj > 1, para j : 1, 2, ..., k. Si a ⌘ b (mód m1 ), a ⌘ b (mód m2 ), . . . , a ⌘ b (mód mk ), entonces a ⌘ b (mód m.c.m.(m1 , . . . , mk )) Demostración: „ Ya que a ⌘ b (mód m1 ), a ⌘ b (mód m2 ), . . . , a ⌘ b (mód mk ), sabemos que m1 |(a  b), m2 |(a  b), . . . , mk |(a  b). „ De aquí se deduce que mcm(m1 , . . . , mk ) es divisor de (a  b). „ Por consiguiente, a ⌘ b (mód (m.c.m.(m1 , . . . , mk ))) Mariam Cobalea (UMA)

Matemática Discreta, Curso 18/19

Teoría de números. Aritmética modular

18 / 72

Aritmética Modular Aritmética de las congruencias

Corolario 11 Sean a, b, m1 , m2 , . . . , mk enteros, donde cada mj > 1, para j : 1, 2, ..., k y tales que m1 , m2 , . . . , mk son coprimos dos a dos. Si a ⌘ b (mód m1 ), a ⌘ b (mód m2 ), . . . , a ⌘ b (mód mk ), entonces a ⌘ b (mód m1 · · · mk ) Demostración: „ Por ser m1 , . . . , mk primos relativos, mcm(m1 , . . . , mk ) = m1 · m2 · mk . „ Luego, por el teorema anterior a ⌘ b (mód m1 · · · mk ) Ejercicio Encuentra un entero que deja un resto igual a 1 cuando se divide por cada uno de los siguientes enteros: 2, 3, 5, 7 . Mariam Cobalea (UMA)

Matemática Discreta, Curso 18/19

Teoría de números. Aritmética modular

19 / 72

Aplicación: Criterios de divisibilidad Una de las aplicaciones de la aritmética de congruencias es obtener criterios de divisibilidad; es decir, reglas que permiten deducir si un número es divisible por otro a partir de los dígitos que lo forman. El punto de partida es: n es divisible por p si y sólo si [n]p = [0]p Si ak ak−1 . . . a1 a0 es la expresión decimal de un número n, entonces n=

k X

aj · 10j

(aj 2 {0, . . . , 9}).

j=0

Para saber si n es divisible por p, utilizamos de las 3 2 las propiedades k X 4 aj · 10j 5 congruencias y simplificamos la expresión j=0

p

Para ello, expresamos las potencias de 10 en la clase de congruencia módulo p. Mariam Cobalea (UMA)

Matemática Discreta, Curso 18/19

Teoría de números. Aritmética modular

20 / 72

Aplicación: Criterios de divisibilidad Criterio de divisibilidad por p = 3 Observamos en primer lugar que [10]3 = [1]3 , y por lo tanto [10j ]3 = [1j ]3 = [1]3 para cada potencia j. A partir de ahí, deducimos que: 2 3 2 3 k k X X 4 aj 10j5 = 4 aj 5 j=0

3

j=0

3

Por lo tanto, un número es divisible por 3 si y sólo si la suma de sus dígitos también es divisible por 3.

Mariam Cobalea (UMA)

Matemática Discreta, Curso 18/19

Teoría de números. Aritmética modular

21 / 72

Aplicación: Criterios de divisibilidad Ejercicio Utiliza la congruencia módulo 9 para encontrar el dígito x en el producto: 89878 · 58965 = 5299x56270 .

Ejercicio Determina la máxima potencia de 2 que divide a cada uno de los enteros siguientes: a) 1423408 b) 41578912246

Mariam Cobalea (UMA)

Matemática Discreta, Curso 18/19

Teoría de números. Aritmética modular

22 / 72

Aritmética Modular Congruencias Lineales

Definición 2 Una congruencia lineal de una variable es una expresión ax ⌘ b (mód m) donde x es un entero desconocido y a, b, m 2 Z,

m > 1.

Ejemplo 11 1

6x ⌘ 22 (mód 27)

2

8x ⌘ 9 (mód 25)

3

4x ⌘ 18 (mód 26)

Mariam Cobalea (UMA)

Matemática Discreta, Curso 18/19

Teoría de números. Aritmética modular

23 / 72

Aritmética Modular Congruencias Lineales

En primer lugar, observamos que si x = x0 es una solución de la congruencia ax ⌘ b (mód m), y si x1 ⌘ x0 (mód m), entonces ax1 ⌘ ax0 ⌘ b (mód m), por lo que x1 también es una solución. De ahí, si un elemento de una clase de congruencia módulo m es una solución, entonces todos los miembros de esa clase son soluciones. Por tanto, podemos preguntarnos cuántas de las m clases de congruencia módulo m son soluciones.

Mariam Cobalea (UMA)

Matemática Discreta, Curso 18/19

Teoría de números. Aritmética modular

24 / 72

Aritmética Modular Congruencias Lineales

El siguiente teorema nos enseña cuando tiene solución una congruencia lineal de una variable y, si la tiene, nos dice exactamente cuantas soluciones hay en Zm . Teorema 12 (Brahmagupta) Sean a, b y m enteros con m > 1 y mcd(a, m) = d. Si d 6 |b, entonces ax ⌘ b (mód m) no tiene solución. Si d|b, entonces ax ⌘ b (mód m) tiene exactamente d soluciones en Zm .

Mariam Cobalea (UMA)

Matemática Discreta, Curso 18/19

Teoría de números. Aritmética modular

25 / 72

Aritmética Modular Congruencias Lineales

Demostración: „ El entero x es una solución de ax ⌘ b (mód m) si y sólo si hay un entero k tal que ax  mk = b. „ Y tomando y = k, nos queda la ecuación diofántica ax + my = b. „ Por el teorema de existencia de soluciones de tales ecuaciones, sabemos que si d 6 |b, dicha ecuación no tiene solución; „ mientras que si d|b hay infinitas soluciones dadas por ⇣ a⌘ ⇣ m⌘ t, y = y0  t, t 2 Z x = x0 + d d

donde x = x0 e y = y0 es una solución particular de la ecuación.

„ Y estos valores de x son las soluciones de la congruencia lineal.

Mariam Cobalea (UMA)

Matemática Discreta, Curso 18/19

Teoría de números. Aritmética modular

26 / 72

Aritmética Modular Congruencias Lineales

Demostración: (cont.) „ Para determinar cuántas soluciones hay en Zm , buscamos la condición ⇣ ⌘ m que describe cuando dos de las soluciones x1 = x0 + t1 y d ⇣ ⌘ m x2 = x0 + t2 son congruentes módulo m. d „ Si estas soluciones son congruentes x0 +

⇣m⌘ d

t1 ⌘ x0 +

⇣m⌘ d

t2

(mód m)

„ entonces t1 ⌘ t2 (mód d) „ Esto muestra que un conjunto completo de soluciones módulo m se ⇣ ⌘ m obtiene tomando x = x0 + t, donde t toma los valores en d {0, 1, . . . , d  1}. Mariam Cobalea (UMA)

Matemática Discreta, Curso 18/19

Teoría de números. Aritmética modular

27 / 72

Aritmética Modular Congruencias Lineales

Resolución de congruencias lineales Dada una congruencia lineal ax ⌘ b (mód m) encontramos todas las soluciones aplicando el teorema de Brahmagupta. 1

2

3

Estudiamos si tiene soluciones enteras, comprobando si mcd(a, m) = d es un divisor de b Hallamos una solución particular: x0 resolviendo la ecuación diofántica ax + my = b Damos las d soluciones a partir de la solución particular x0 + t(

Mariam Cobalea (UMA)

m ), d

t 2 { 0, 1, ..., d  1}

Matemática Discreta, Curso 18/19

Teoría de números. Aritmética modular

28 / 72

Aritmética Modular Congruencias Lineales

Ejemplo 12 Resuelve la congruencia lineal 9x ⌘ 12 (mód 15) 1

Estudiamos si tiene soluciones enteras, mcd(9, 15) = 3 | Luego

2

3 12

)

9x ⌘ 12 (mód 15) tiene 3 soluciones en Z15

Convertimos la congruencia lineal en una ecuación diofántica 9x ⌘ 12 (mód 15) =) 9x + 15y = 12 =) 3x + 5y = 4 Hallamos una solución particular:

x0

mcd(3, 5) = 1 = 3 · 2 + 5 · (1) =) 4 = 3 · 8 + 5 · (4) =) x0 = 8 La solución general es {x 2 Z | x = 8 + 5t, t 2 Z} Mariam Cobalea (UMA)

Matemática Discreta, Curso 18/19

Teoría de números. Aritmética modular

29 / 72

Aritmética Modular Congruencias Lineales 3

[8]5

La solución general {x 2 Z | x = 8 + 5t, t 2 Z} es la clase [8]5

=

{. . . , 27, 22, 17, 12, 7, 2, 3, 8, 13, 18, 23, 28, 33, 38, 43 . . . }

=

{. . . , 22  7, 8 , 23, 38 . . . } [ {. . . , 17, 2, 13 , 28, 43 . . . } [ {. . . , 27, 12, 3 , 18, 33, . . . }

Como nos dice el teorema, el conjunto de enteros de todas las soluciones de 9x ⌘ 12 (mód 15) está formado por 3 clases de equivalencia módulo 15 : [8 + 0 ·

15 ]15 = [8]15 , 3

Mariam Cobalea (UMA)

[8 + 1 ·

15 ]15 = [13]15 , 3

Matemática Discreta, Curso 18/19

[8 + 2 ·

15 ]15 = [18]15 = [3]15 3

Teoría de números. Aritmética modular

30 / 72

Aritmética Modular Inverso módulo m

Ahora consideramos congruencias de la forma ax ⌘ 1 (mód m) Por el teorema anterior, existe solución si y sólo si mcd(a, m) = 1, y todas las soluciones son congruentes módulo m. Definición ...