View
5
Download
0
Category
Preview:
Citation preview
Introduccion a la Matematica DiscretaAritmetica Entera
Luisa Marıa Camacho
Camacho Introd. a la Matematica Discreta 1 / 36
Introduccion a la Matematica DiscretaTemario
Tema 1. Teorıa de Conjuntos.
Tema 2. Logica proposicional y algebras de Boole.
Tema 3. Tecnicas de contar.
Tema 4. Recursion.
Tema 5. Aritmetica entera.
Tema 6. Aritmetica modular.
Camacho Introd. a la Matematica Discreta 2 / 36
Tema 5. Aritmetica Entera
El conjunto de los numeros enteros, Z.
Division en Z.
Divisibilidad y propiedades.
Principio de Induccion.
Maximo Comun Divisor.
Algoritmo de Euclides.
Identidad de Bezout.
Algoritmo de Euclides extendido.
Numeros coprimos.
Ecuaciones diofanticas.
Resolucion de ecuaciones diofanticas lineales con dos incognitas.
Numeros primos.
Teorema Fundamental de la Aritmetica.
Distribucion de primos.
Teorema de Euclides.
La funcion π(x).
Numero primos de Fermat y de Mersenne.
La criba de Eratostenes.
El problema de la factorizacion.
Camacho Introd. a la Matematica Discreta 3 / 36
Aritmetica Entera. Introduccion.
¿Que es la Teorıa de Numeros? El estudio de los numeros enteros.
Ejemplos de Numeros
Numeros pares
Numeros impares
Numeros naturales
Numeros triangulares
Numeros primos
Camacho Introd. a la Matematica Discreta 4 / 36
Aritmetica Entera. Introduccion.
¿Para que usamos los numeros primos? Criptografıa: RSA
Ciframos y desciframos mensajes de manera relativamente facil.La seguridad del sistema radica en la eleccion adecuada de la clave publica.
¿Es 25478512753524632765756437563656529853685639856349856475467576751 primo?
NO (es divisible por 3).
¿Es 25478512753524632765756437563656529853685639856349856475467576903 primo?
SI.
¿Es 25478512753524632765756437563656529853685639856349856475467577041 primo?
SI.
¿Es 649154612131517364235209351853847539464423773588548724491651094469224065674417028369864303126429603800928587351648815624744684023 primo?
NO.
Camacho Introd. a la Matematica Discreta 5 / 36
Aritmetica entera. El conjunto Z.
A1 La suma y el producto son leyes de composicion 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 Introd. a la Matematica Discreta 6 / 36
Aritmetica Entera. El conjunto Z.
En el conjunto Z de los numeros enteros se define la relacion de orden “≤ ”, la cualcumple los siguientes propiedades:
A8 Propiedad reflexiva: ∀a ∈ Z =⇒ a ≤ a
A9 Propiedad antisimetrica:a ≤ bb ≤ a
}=⇒ a = b
A10 Propiedad transitiva:a ≤ bb ≤ c
}=⇒ a ≤ c
A11 a ≤ b =⇒ a+ c ≤ b+ c
A12 a ≤ b y 0 ≤ c =⇒ ac ≤ bc
Camacho Introd. a la Matematica Discreta 7 / 36
Aritmetica Entera. El conjunto Z.
Definicion
Dado S ⊂ Z un subconjunto, se dice que c ∈ Z es una cota inferior del conjunto Ssi c ≤ a cualquiera que sea el elemento a ∈ S. Si ademas, c ∈ S recibe el nombre deprimer elemento.
Analogamente, se dice que d ∈ Z es una cota superior del conjunto S si a ≤ dcualquiera que sea el elemento a ∈ S. Si ademas, d ∈ S recibe el nombre de ultimoelemento.
A13 [Buena ordenacion]
Todo subconjunto de Z no vacıo y acotado inferiormente(superiormente) posee un primer (ultimo) elemento.
Camacho Introd. a la Matematica Discreta 8 / 36
Aritmetica Entera. Division en Z.
Teorema de la Division.
Sean a, b ∈ Z con b > 0 existe un unico par de enteros q, r ∈ Z tal que a = b · q + rcon 0 ≤ r < b.
Al entero q se le llama cociente y a r resto.
Teorema de la Division.
Si a y b son dos enteros con b 6= 0 existe un unico par de enteros q y r tales que
a = qb+ r 0 ≤ r < |b|
Camacho Introd. a la Matematica Discreta 9 / 36
Aritmetica Entera. Divisibilidad.
Definicion
Diremos que a divide a b si el resto de la division de a entre b es 0. Diremostambien que b es divisible por a o b es multiplo 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 ydel propio n, a los cuales se les denomina divisores impropios.
Camacho Introd. a la Matematica Discreta 10 / 36
Aritmetica Entera. 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 | (α1b1 + · · ·+ αkbk)
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 Introd. a la Matematica Discreta 11 / 36
Aritmetica Entera. Principio de Induccion
Tenemos unas filas de fichas de domino. Supongamos que tenemos las siguientesafirmaciones:
Enunciado 1: Alguien ha derribado la primera ficha.
Enunciado 2: Si una ficha es derribada, entonces esta tira la siguiente.
De 1 y 2 podemos concluir que todas las fichas acabaran cayendo.
Camacho Introd. a la Matematica Discreta 12 / 36
Aritmetica Entera. Principio de Induccion.
Sea P (n) una propiedad relativa al numero n y k un entero fijo. Supongamos que
P (k) es cierta.
Si P (n) es cierta, entonces P (n+ 1) es cierta tambien.
Entonces P (n) es cierta para cualquier valor n ≥ k.
Camacho Introd. a la Matematica Discreta 13 / 36
Aritmetica Entera. Principio de Induccion.
¿Como demostrar algo usando el principio de induccion simple?
Comenzamos enunciando la propiedad que queremos probar. Es decir, decimos cual esla propiedad P (n) y cual 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) estambien verdad (este paso es llamado la etapa de induccion).
Finalmente concluimos que, usando el principio de induccion simple, P (n) es ciertapara cualquier n ≥ k.
Nota: En la etapa de induccion, a la suposicion de que P (n) es cierta se le llama hipotesisde induccion.
Camacho Introd. a la Matematica Discreta 14 / 36
Aritmetica Entera. Principio de Induccion.
A veces la induccion simple no basta...¿Cuales son los enteros que podemos obtener como sumas de 3 y de 5 (conrepeticiones)?
3 = 3 5 = 5 6 = 3 + 38 = 3 + 5 9 = 3 + 3 + 3 10 = 5 + 5
11 = 5 + 3 + 3 12 = 3 + 3 + 3 + 3 . . .
Sea P (n) la propiedad: “el numero n es una suma de 3 y de 5”, y queremosdemostrar 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 tambien.
n+ 1 = (n− 2) + 3
No podemos seguir, solo sabemos que P (n) es cierto . . .
Camacho Introd. a la Matematica Discreta 15 / 36
Aritmetica Entera. Principio de Induccion.
Sea P (n) una propiedad matematica. Queremos probar que P (n) es cierta paracualquier 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 Introd. a la Matematica Discreta 16 / 36
Aritmetica Entera. Principio de Induccion.
¿Como demostrar algo usando induccion completa?
Comenzamos por enunciar la propiedad que queremos probar. Es decir, cual esla propiedad y cuales 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 tambien cierta.
Finalmente, concluimos que usando el principio de induccion completa, P (n)es cierta para cualquier n ≥ n0.
Camacho Introd. a la Matematica Discreta 17 / 36
Aritmetica Entera. Maximo Comun Divisor.
Maximo Comun Divisor.
El maximo comun divisor de dos numeros a y b es el mayor entero d > 0 tal qued | a y d | b.
Maximo Comun Divisor.
El maximo comun divisor es el unico entero d que cumple
d | a y d | b.si c | a y c | b ⇒ c | d
Escribimos mcd(a, b) = d.
Camacho Introd. a la Matematica Discreta 18 / 36
Aritmetica Entera. Maximo Comun Divisor.
Lema
Las dos definiciones son equivalentes.
Mınimo Comun Multiplo.
El mınimo comun multiplo de a y b es el multiplo comun mas pequeno de a y b.
Lema
mcm(a, b) =a · b
mcd(a, b)
Camacho Introd. a la Matematica Discreta 19 / 36
Aritmetica Entera. Algoritmo de Euclides.
Lema.
Dados dos enteros a y b se verifica que mcd(a, b) = mcd(b, r) siendo a = b · q + r con0 ≤ r < b.
Algoritmo de Euclides
Sean a y b dos enteros queremos calcular d = mcd(a, b) (a > b > 0)
a = q1b + r1 con 0 ≤ r1 < b
b = q2r1 + r2 con 0 ≤ r2 < r1
r1 = q3r2 + r3 con 0 ≤ r3 < r2
.
.
.
rn−2 = qnrn−1 + rn con 0 ≤ rn < rn−1
rn−1 = qn+1rn + 0
Se trata de una sucesion de numeros 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 Introd. a la Matematica Discreta 20 / 36
Aritmetica Entera. Algoritmo de Euclides.
Ejemplo
Sean a = 250 y b = 111. Hallar el mcd(a, b)
250 = 111 · 2 + 28, 0 < 28 < 111111 = 28 · 3 + 27, 0 < 27 < 2828 = 27 · 1 + 1, 0 < 1 < 2727 = 1 · 27
Por tanto, el mcd(a, b) = 1.
Algorimo de Euclides.
P1 Leer a y b.
P2 n = 1, q = babc, r = a− b · q.
P3 Mientras r > 0.
n = n+ 1a = bb = rq = ba
bc
r = a− b · qP4 Retorna n y b.
Camacho Introd. a la Matematica Discreta 21 / 36
Aritmetica Entera. Identidad de Bezout.
Teorema
Si d = mcd(a, b) entonces existen enteros α y β tal que
d = αa+ βb. Identidad de Bezout
Demostracion
a = q1b+ r1 con 0 ≤ r1 < b
b = q2r1 + r2 con 0 ≤ r2 < r1
r1 = q3r2 + r3 con 0 ≤ r3 < r2
...
rn−2 = qnrn−1 + rn con 0 ≤ rn < rn−1
rn−1 = qn+1rn + 0
Camacho Introd. a la Matematica Discreta 22 / 36
Aritmetica Entera. 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 multiplo 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, bd
) = 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 Introd. a la Matematica Discreta 23 / 36
Aritmetica Entera. Algoritmo de Euclides extendido.
El algoritmo extendido de euclides nos permite calcular el mcd de dos numeros ası como la identidad deBezout.
Pseudocodigo.
P1. Leer a y b.
P2. Hacer u′ = 1, v = 1, u = 0, v′ = 0, q = b abc, r = a− q ∗ b.
P3. Mientras r > 0 hacern = n + 1% Actualizamos los valores de u′ y de u%t = u′
u′ = uu = t− q ∗ u% Actualizamos los valores de v′ y de v %t = v′
v′ = vv = t− q ∗ v% Actualizamos los valores de a, b, q, y r %a = bb = rq = b a
bc
r = a− q ∗ bFin mientras
P4. Retorna b, u, v.
Camacho Introd. a la Matematica Discreta 24 / 36
Aritmetica Entera. Ecuaciones diofanticas.
Problema.
Se trata de realizar la tarea x en 6 minutos y la tarea y en 10 minutos trabajandodurante 104 minutos. ¿Cuantas tareas x e y se pueden terminar?
Solucion.�� ��6x+ 10y = 104 =⇒ Encontrar soluciones enteras y positivas.
Camacho Introd. a la Matematica Discreta 25 / 36
Aritmetica Entera. Ecuaciones Diofanticas.
Definicion
Una Ecuacion Diofantica es una ecuacion con coeficientes enteros en una ovarias variables que requiere soluciones enteras.
Nos centraremos en las lineales y de dos incognitas.
Problema
Dados a, b, c ∈ Z no nulos a la vez, hallar las soluciones enteras de la ecuacionax+ by = c.
Camacho Introd. a la Matematica Discreta 26 / 36
Aritmetica Entera. Ecuaciones Diofanticas
Teorema
Si a, b y c son enteros con a y b no nulos, la ecuacion diofantica ax+ by = c tienesolucion si y solo si el maximo comun divisor de a y b divide a c. En este caso, si x0
e y0 es una solucion particular, entonces todas las soluciones vienen dadas por:
x = x0 +b
mcd(a, b)k; y = y0 −
a
mcd(a, b)k, ∀k ∈ Z
Demostracion
La demostracion del teorema anterior da un procedimiento para resolverlas.
Camacho Introd. a la Matematica Discreta 27 / 36
Aritmetica Entera. Resolucion de la ecuacion diofantica.
Ecuacion diofantica lineal
ax+ by = c con a, b, c enteros.
Metodo
Calculamos mcd(a, b) = d, y la identidad de Bezout (Algoritmo de Euclidesextendido).
αa+ βb = d
a. Si d divide a c entonces existe solucion.
b. Si d no divide a c entonces no existe solucion.
Camacho Introd. a la Matematica Discreta 28 / 36
Aritmetica Entera. Resolucion de la ecuacion diofantica.
Metodo
Dividimos toda la ecuacion por d. Dividimos la identidad de Bezout tambien por d.
a
dx+
b
dy =
c
d, (1)
a
dα+
b
dβ = 1, (2)
Multiplicamos la ecuacion (2) porc
d. ⇒
a
d(αc
d) +
b
d(βc
d) =
c
d.
Una solucion particular de la ecuacion (1) : x0 = αc
d, y0 = β
c
dHallamos la solucion general. �
���
x = x0 − kb
d,
y = y0 + ka
d, k ∈ Z
Camacho Introd. a la Matematica Discreta 29 / 36
Aritmetica Entera. Numeros primos
Dado un numero natural n,
¿Es n primo?
En caso de no ser, factorizar n.
Camacho Introd. a la Matematica Discreta 30 / 36
Aritmetica Entera. Numeros primos.
Numero primo.
Un numero p > 1 es primo si sus unicos divisores son 1 y p. Un numero n se dicecompuesto si admite divisores propios.
Propiedades de los numeros 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 algun i
(Si p no primo, esta propiedad no es cierta.)
Camacho Introd. a la Matematica Discreta 31 / 36
Aritmetica Entera. Teorema Fundamental de la Aritmetica.
Teorema Fundamental de la Aritmetica.
Todo numero n entero puede escribirse de la forma unica (excepto en el orden de losfactores) como producto de primos:
n = pe11 · pe22 · · · p
ekk
donde p1, . . . , pk son primos y e1, . . . , ek son enteros positivos.
Demostracion
n compuesto natural existe p1 primo tal que n = p1 · a.
a primo −→ FIN
a no primo −→ existe p2 tal que a = p2 · b −→{b primob no primo
como ninguno es nulo y n > a > b > c · · · llegaremos a uno que sea primo.
Camacho Introd. a la Matematica Discreta 32 / 36
Aritmetica Entera. Distribucion de primos.
¿Con que frecuencia aparecen los numeros primos?
Sea pn el n-esimo numero primo, es decir, p1 = 2, p2 = 3, p3 = 5, etc. Se cumple que
pn ≤ 22n−1
para todo n ≥ 1.
¿Es buena aproximacion? NO
p4 = 7 ≤ 223
= 28 = 256
Camacho Introd. a la Matematica Discreta 33 / 36
Aritmetica Entera. Teorema de Euclides.
Teorema de Euclides.
Existen infinitos numeros 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 Introd. a la Matematica Discreta 34 / 36
Aritmetica Entera. Funcion π(x).
Funcion π(x)
El numero de numeros primos menores o iguales a x, se denota por π(x) y a lafuncion π se conoce como funcion de numeros primos.
Teorema de los numeros primos.
π(x)x
ln x
−→ 1 cuando x −→∞
Camacho Introd. a la Matematica Discreta 35 / 36
Aritmetica Entera. Bibliografıa.
1 N. L. Biggs, Matematica discreta. Editorial Vicens Vives, 1994.
2 E. Bujalance, J. A. Bujalance, A. F. Costa, E. Martınez, Elementos dematematica discreta. Editorial Sanz y Torres, 3a Edicion. 2005.
3 F. Garcıa Merayo, Matematica Discreta.Editorial Thomson, 2a Edicion, 2005.
4 R. P. Grimaldi, Matematicas 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 Introd. a la Matematica Discreta 36 / 36
Recommended