Introducci on a la Matem atica Discreta - personal.us.es

Introducción a la Matemática Discreta ´tica Entera Aritme Luisa Mar´ıa Camacho

Camacho

Introd. a la Matem´ atica Discreta

1 / 36

Introducción a la Matemática Discreta Temario

Tema 1. Teor´ıa de Conjuntos. Tema 2. Lógica proposicional y ´ algebras de Boole. Tema 3. Técnicas de contar. Tema 4. Recursión. Tema 5. Aritmética entera. Tema 6. Aritmética modular.

Camacho


2 / 36

Tema 5. Aritmética Entera El conjunto de los n´ umeros enteros, Z. Divisi´ on en Z. Divisibilidad y propiedades. Principio de Inducci´ on. M´ aximo Com´ un Divisor. Algoritmo de Euclides. Identidad de Bezout. Algoritmo de Euclides extendido. N´ umeros coprimos. Ecuaciones diof´ anticas. Resoluci´ on de ecuaciones diof´ anticas lineales con dos inc´ ognitas. N´ umeros primos. Teorema Fundamental de la Aritm´ etica. Distribuci´ on de primos. Teorema de Euclides. La funci´ on π(x). N´ umero primos de Fermat y de Mersenne. La criba de Erat´ ostenes. El problema de la factorizaci´ on. Camacho


3 / 36

Aritmética Entera.

Introducci´ on.

¿Qué es la Teor´ıa de N´ umeros?

El estudio de los n´ umeros enteros.

Ejemplos de N´ umeros N´ umeros pares N´ umeros impares N´ umeros naturales N´ umeros triangulares N´ umeros primos

Camacho


4 / 36


Introducci´ on.

¿Para qué usamos los n´ umeros primos? Criptograf´ıa: RSA Ciframos y desciframos mensajes de manera relativamente f´ acil. La seguridad del sistema radica en la elecci´ on adecuada de la clave p´ ublica. ¿Es 25478512753524632765756437563656529853685639856349856475467576751 primo? NO (es divisible por 3). ¿Es 25478512753524632765756437563656529853685639856349856475467576903 primo? SÍ. ¿Es 25478512753524632765756437563656529853685639856349856475467577041 primo? SÍ. ¿Es 64915461213151736423520935185384753946442377358854872449165109 4469224065674417028369864303126429603800928587351648815624744684023 primo? NO.

Camacho


5 / 36

Aritmética entera.

El conjunto Z.

A1 La suma y el producto son leyes de composici´ on internas. ∀a, b ∈ Z ⇒ a + b ∈ Z, ab ∈ Z A2 Ambas leyes son asociativas. ∀a, b, c ∈ Z ⇒ a + (b + c) = (a + b) + c = a + b + c, a(bc) = (ab)c = abc A3 Existen elementos neutro 0 y unidad 1 tales que: ∀a ∈ Z ⇒ a + 0 = 0 + a = a a · 1 = 1 · a = a A4 Existen elementos opuestos. Es decir: ∀a ∈ Z ∃ − a ∈ Z : a + (−a) = −a + a = 0 A5 Ambas leyes son conmutativas. ∀a, b ∈ Z ⇒ a + b = b + a

ab = ba

A6 El producto es distributivo respecto de la suma. ∀a, b, c ∈ Z ⇒ a(b + c) = ab + ac A7 Propiedad cancelativa. Si a 6= 0 y ab = ac, entonces b = c

Camacho


6 / 36


El conjunto Z.

En el conjunto Z de los n´ umeros enteros se define la relaci´ on de orden “ ≤ ”, la cual cumple los siguientes propiedades: A8 Propiedad reflexiva: ∀a ∈ Z =⇒ a ≤ a a≤b A9 Propiedad antisimétrica: =⇒ a = b b≤a a≤b A10 Propiedad transitiva: =⇒ a ≤ c b≤c A11 a ≤ b =⇒ a + c ≤ b + c A12 a ≤ b y 0 ≤ c =⇒ ac ≤ bc

Camacho


7 / 36


El conjunto Z.

Definici´ on Dado S ⊂ Z un subconjunto, se dice que c ∈ Z es una cota inferior del conjunto S si c ≤ a cualquiera que sea el elemento a ∈ S. Si adem´ as, c ∈ S recibe el nombre de primer elemento. An´ alogamente, se dice que d ∈ Z es una cota superior del conjunto S si a ≤ d cualquiera que sea el elemento a ∈ S. Si adem´ as, d ∈ S recibe el nombre de u ´ ltimo elemento. ´ n] A13 [Buena ordenacio Todo subconjunto de Z no vac´ıo y acotado inferiormente (superiormente) posee un primer (´ ultimo) elemento.

Camacho


8 / 36


Divisi´ on en Z.

Teorema de la Divisi´ on. Sean a, b ∈ Z con b > 0 existe un u ńico par de enteros q, r ∈ Z tal que a = b · q + r con 0 ≤ r < b.

Al entero q se le llama cociente y a r resto. Teorema de la Divisi´ on. Si a y b son dos enteros con b 6= 0 existe un u ńico par de enteros q y r tales que a = qb + r

Camacho

0 ≤ r < |b|


9 / 36


Divisibilidad.

Definici´ on Diremos que a divide a b si el resto de la divisi´ on de a entre b es 0. Diremos también que b es divisible por a o b es m´ ultiplo de a. Es decir, a divide a b ⇔ ∃q ∈ Z tal que b = q · a lo denotaremos por a | b o b = a. ˙ Dado un entero n, se denominan divisores propios a sus divisores distintos de 1 y del propio n, a los cuales se les denomina divisores impropios.

Camacho


10 / 36


Divisibilidad.

Si a | b y c ∈ Z ⇒ a | b · c Si a | b ∧ b | c ⇒ a | c Si a | b ∧ a | c ⇒ a | (αb + βc) Si a | b1 , a | b2 , . . . , a | bk ⇒ a | (α1 b1 + · · · + αk bk ) Si m 6= 0 y a | b ⇒ m · a | m · b Si b 6= 0 y a | b ⇒ |a| ≤ |b| Si a | b y b | a ⇒ a = ±b

Camacho


11 / 36


Principio de Inducci´ on

Tenemos unas filas de fichas de domin´ o. Supongamos que tenemos las siguientes afirmaciones: Enunciado 1: Alguien ha derribado la primera ficha. Enunciado 2: Si una ficha es derribada, entonces ésta tira la siguiente.

De 1 y 2 podemos concluir que todas las fichas acabar´ an cayendo.

Camacho


12 / 36


Principio de Inducci´ on.

Sea P (n) una propiedad relativa al n´ umero n y k un entero fijo. Supongamos que P (k) es cierta. Si P (n) es cierta, entonces P (n + 1) es cierta también. Entonces P (n) es cierta para cualquier valor n ≥ k.

Camacho


13 / 36



¿C´ omo demostrar algo usando el principio de inducci´ on simple? Comenzamos enunciando la propiedad que queremos probar. Es decir, decimos cu´ al es la propiedad P (n) y cu´ al es el entero k. Probamos que P (k) es cierta (este paso es llamado la etapa base). Probamos que para cualquier n ≥ k tal que P (n) sea verdad, entonces P (n + 1) es tambi´ en verdad (este paso es llamado la etapa de inducci´ on). Finalmente concluimos que, usando el principio de inducci´ on simple, P (n) es cierta para cualquier n ≥ k.

Nota: En la etapa de inducci´ on, a la suposici´ on de que P (n) es cierta se le llama hip´ otesis de inducci´ on.

Camacho


14 / 36



A veces la inducci´ on simple no basta... ¿Cu´ ales son los enteros que podemos obtener como sumas de 3 y de 5 (con repeticiones)? 3 8 11

= = =

3 3+5 5+3+3

5 9 12

= = =

5 3+3+3 3+3+3+3

6 10

= = ...

3+3 5+5

Sea P (n) la propiedad: “el n´ umero n es una suma de 3 y de 5”, y queremos demostrar que P (n) es cierto para todo n ≥ 8. Para demostrar la etapa base P (8) basta comprobar que: 8 = 5 + 3 Si P (n) es cierta entonces P (n + 1) es cierta también. n + 1 = (n − 2) + 3 No podemos seguir, s´ olo sabemos que P (n) es cierto . . .

Camacho


15 / 36



Sea P (n) una propiedad matem´ atica. Queremos probar que P (n) es cierta para cualquier n ≥ n0 . Si se verifica que: P (n0 ), P (n0 + 1), . . . , P (n1 ) son ciertas. Si P (k) es cierta para cualquier k ≥ n1 , entonces P (k + 1) es cierta. Entonces P (n) es cierta para cualquier n ≥ n0 .

Camacho


16 / 36



¿C´ omo demostrar algo usando inducci´ on completa? Comenzamos por enunciar la propiedad que queremos probar. Es decir, cu´ al es la propiedad y cu´ ales son los enteros n0 y n1 . Probamos que P (n0 ), P (n0 + 1), P (n0 + 2), . . . P (n1 ) son ciertas. Probamos que si para cualquier k ≥ n1 se tiene que P (n1 ), P (n1 + 1), . . . , P (k) son ciertas, entonces P (k + 1) es también cierta. Finalmente, concluimos que usando el principio de inducci´ on completa, P (n) es cierta para cualquier n ≥ n0 .

Camacho


17 / 36


M´ aximo Com´ un Divisor.

M´ aximo Com´ un Divisor. El m´ aximo com´ un divisor de dos n´ umeros a y b es el mayor entero d > 0 tal que d | a y d | b.

M´ aximo Com´ un Divisor. El m´ aximo com´ un divisor es el u ńico entero d que cumple d | a y d | b. si c | a y c | b ⇒ c | d Escribimos mcd(a, b) = d.

Camacho


18 / 36


M´ aximo Com´ un Divisor.

Lema Las dos definiciones son equivalentes.

M´ınimo Com´ un M´ ultiplo. El m´ınimo com´ un m´ ultiplo de a y b es el m´ ultiplo com´ un m´ as peque˜ no de a y b.

Lema mcm(a, b) =

Camacho

a·b mcd(a, b)


19 / 36


Algoritmo de Euclides.

Lema. Dados dos enteros a y b se verifica que mcd(a, b) = mcd(b, r) siendo a = b · q + r con 0 ≤ r < b.

Algoritmo de Euclides Sean a y b dos enteros queremos calcular d = mcd(a, b) (a > b > 0) a = q1 b + r1 con 0 ≤ r1 < b b = q2 r1 + r2 con 0 ≤ r2 < r1 r1 = q3 r2 + r3 con 0 ≤ r3 < r2 . . . rn−2 = qn rn−1 + rn con 0 ≤ rn < rn−1 rn−1 = qn+1 rn + 0 Se trata de una sucesi´ on de n´ umeros naturales decreciente

b > r1 > r2 > · · · > rk > · · · ≥ 0

mcd(a, b) = mcd(b, r1 ) = · · · = mcd(rn−2 , rn−1 ) = mcd(rn−1 , 0) = rn−1

Camacho


20 / 36


Algoritmo de Euclides.

Ejemplo Sean a = 250 y b = 111. Hallar el mcd(a, b) 250 = 111 · 2 + 28, 0 < 28 < 111 111 = 28 · 3 + 27, 0 < 27 < 28 28 = 27 · 1 + 1, 0 < 1 < 27 27 = 1 · 27 Por tanto, el mcd(a, b) = 1. Algorimo de Euclides. P 1 Leer a y b. P2

n = 1, q = b ab c, r = a − b · q.

P 3 Mientras r > 0. n=n+1 a=b b=r q = b ab c r =a−b·q P 4 Retorna n y b. Camacho


21 / 36


Identidad de Bezout.

Teorema Si d = mcd(a, b) entonces existen enteros α y β tal que d = αa + βb.

Identidad de Bezout

Demostraci´ on a = q1 b + r1 con 0 ≤ r1 < b b = q2 r1 + r2 con 0 ≤ r2 < r1 r1 = q3 r2 + r3 con 0 ≤ r3 < r2 .. . rn−2 = qn rn−1 + rn con 0 ≤ rn < rn−1 rn−1 = qn+1 rn + 0

Camacho


22 / 36


Identidad de Bezout.

Propiedades. Si a, b son enteros, no nulos, tal que mcd(a, b) = d, y sea c un entero cualquiera, entonces ∃x, y ∈ Z tal que c = a · x + b · y ⇔ c es m´ ultiplo de d Si d = mcd(a, b) entonces d es el menor entero de la forma a · x + b · y con x, y ∈ Z Si d = mcd(a, b) entonces mcd(ma, mb) = md para todo m > 0 Si d = mcd(a, b) entonces mcd( ad , db ) = 1 Si mcd(a, b) = 1 y a | c ∧ b | c entonces a · b | c Si mcd(a, b) = 1 y a | b · c entonces a | c Dos enteros a y b son primos entre s´ı (coprimos) ⇔ ∃x, y ∈ Z tales que a · x + b · y = 1

Camacho


23 / 36


Algoritmo de Euclides extendido.

El algoritmo extendido de euclides nos permite calcular el mcd de dos n´ umeros as´ı como la identidad de Bezout.

Pseudoc´ odigo. P 1. Leer a y b. P 2. Hacer u0 = 1, v = 1, u = 0, v 0 = 0, q = b a c, r = a − q ∗ b. b P 3. Mientras r > 0 hacer n=n+1 % Actualizamos los valores de u0 y de u % t = u0 u0 = u u=t−q∗u % Actualizamos los valores de v 0 y de v % t = v0 v0 = v v =t−q∗v % Actualizamos los valores de a, b, q, y r % a=b b=r q = ba c b r =a−q∗b Fin mientras P 4. Retorna b, u, v.

Camacho


24 / 36


Ecuaciones diof´ anticas.

Problema. Se trata de realizar la tarea x en 6 minutos y la tarea y en 10 minutos trabajando durante 104 minutos. ¿Cu´ antas tareas x e y se pueden terminar?

Soluci´ on.

6x + 10y = 104 =⇒ Encontrar soluciones enteras y positivas.

Camacho


25 / 36


Ecuaciones Diof´ anticas.

Definici´ on Una Ecuaci´ on Diof´ antica es una ecuaci´ on con coeficientes enteros en una o varias variables que requiere soluciones enteras. Nos centraremos en las lineales y de dos inc´ ognitas. Problema Dados a, b, c ∈ Z no nulos a la vez, hallar las soluciones enteras de la ecuaci´ on ax + by = c.

Camacho


26 / 36


Ecuaciones Diof´ anticas

Teorema Si a, b y c son enteros con a y b no nulos, la ecuaci´ on diof´ antica ax + by = c tiene soluci´ on si y s´ olo si el m´ aximo com´ un divisor de a y b divide a c. En este caso, si x0 e y0 es una soluci´ on particular, entonces todas las soluciones vienen dadas por: x = x0 +

b k; mcd(a, b)

y = y0 −

a k, mcd(a, b)

∀k ∈ Z

Demostraci´ on La demostraci´ on del teorema anterior da un procedimiento para resolverlas.

Camacho


27 / 36


Resoluci´ on de la ecuaci´ on diofántica.

Ecuaci´ on diof´ antica lineal ax + by = c con a, b, c enteros.

Método Calculamos mcd(a, b) = d, y la identidad de Bezout (Algoritmo de Euclides extendido). αa + βb = d

a. Si d divide a c entonces existe soluci´ on. b. Si d no divide a c entonces no existe soluci´ on.

Camacho


28 / 36


Resoluci´ on de la ecuaci´ on diofántica.

M´ etodo Dividimos toda la ecuaci´ on por d. Dividimos la identidad de Bezout tambi´ en por d. b c a x+ y = , d d d

(1)

b a α + β = 1, d d

(2)

Multiplicamos la ecuaci´ on (2) por

a c b c c c . ⇒ (α ) + (β ) = . d d d d d d

c c Una soluci´ on particular de la ecuaci´ on (1) : x0 = α , y0 = β d d Hallamos la soluci´ on general.

b x = x0 − k , d a y = y0 + k , d

Camacho

k∈Z


29 / 36


N´ umeros primos

Dado un n´ umero natural n, ¿Es n primo? En caso de no ser, factorizar n.

Camacho


30 / 36


N´ umeros primos.

N´ umero primo. Un n´ umero p > 1 es primo si sus u ńicos divisores son 1 y p. Un n´ umero n se dice compuesto si admite divisores propios.

Propiedades de los n´ umeros primos. Sean a y b enteros y p primo. p|a o p y a son primos entre s´ı Si p|a · b =⇒ p|a o p|b Si p|a1 · a2 · · · ak =⇒ p|ai para alg´ un i (Si p no primo, esta propiedad no es cierta.) Camacho


31 / 36


Teorema Fundamental de la Aritmética.

Teorema Fundamental de la Aritmética. Todo n´ umero n entero puede escribirse de la forma u ńica (excepto en el orden de los factores) como producto de primos: e

n = pe11 · pe22 · · · pkk donde p1 , . . . , pk son primos y e1 , . . . , ek son enteros positivos.

Demostraci´ on n compuesto natural a primo

−→

a no primo

−→

existe p1 primo tal que n = p1 · a. F IN existe p2 tal que a = p2 · b

−→

b primo b no primo

como ninguno es nulo y n > a > b > c · · · llegaremos a uno que sea primo. Camacho


32 / 36


Distribuci´ on de primos.

¿Con qué frecuencia aparecen los n´ umeros primos? Sea pn el n-ésimo n´ umero primo, es decir, p1 = 2, p2 = 3, p3 = 5, etc. Se cumple que n−1 p n ≤ 22 para todo n ≥ 1. ¿Es buena aproximaci´ on? NO 3

p4 = 7 ≤ 22 = 28 = 256

Camacho


33 / 36


Teorema de Euclides.

Teorema de Euclides. Existen infinitos n´ umeros primos. Propiedades. Si p primo, p ≥ 5 entonces p es de la forma 4q + 1 o 4q + 3. Existen infinitos primos de la forma 4q + 3. Si a y b son enteros primos entre s´ı, existen infinitos primos de la forma a · q + b.

Camacho


34 / 36


Funci´ on π(x).

Funci´ on π(x) El n´ umero de n´ umeros primos menores o iguales a x, se denota por π(x) y a la funci´ on π se conoce como funci´ on de n´ umeros primos.

Camacho


35 / 36


Bibliograf´ıa.

1 N. L. Biggs, Matem´ atica discreta. Editorial Vicens Vives, 1994. 2 E. Bujalance, J. A. Bujalance, A. F. Costa, E. Mart´ınez, Elementos de

matem´ atica discreta. Editorial Sanz y Torres, 3a Edici´ on. 2005. 3 F. Garc´ıa Merayo, Matem´ atica Discreta.

Editorial Thomson, 2a Edici´ on, 2005. 4 R. P. Grimaldi, Matem´ aticas discreta y combinatoria.

Editorial Addison Wesley Iberoamericana, 1997. 5 G.A. Jones y M. Jones, Elementary number theory. Editorial Springer, 1998. 6 R. Kumanduri y C. Romero, Number Theory with Computers Applications.

Prenticell Hall, 1998. 7 K. H. Rosen, Discrete Mathematics and its applications.

Editorial McGraw-Hill, 2003.

Camacho


36 / 36

Introducci on a la Matem atica Discreta - personal.us.es

Recommend Documents