MA265 Valores y Vectores propios[Diapo]

UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 1 División en los enteros CONTENIDO Unidad 1: PRELIMINARES 1.3 División de enteros: ▪ Introducción ▪ División entera ▪ Máximo Común Divisor ▪ Algoritmo de Euclides ▪ Mínimo común Múltiplo UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 2 División en los enteros Introducción En matemáticas, y más precisamente en la aritmética, la división euclidiana, también llamada algoritmo de la división, es un teorema que asegura que «el proceso habitual de división entre números enteros» puede llevarse a cabo y que se obtiene un cociente y un residuo únicos. Un «algoritmo de división entera» es cualquier método efectivo que produce un cociente y un residuo. Existen numerosos métodos para efectuar estos cálculos, como por ejemplo la división larga, la factorización de enteros o la aritmética modular. División entera Dado 𝑎 y 𝑏 dos enteros no negativos, con 𝑏 ≠ 0 , existe un único par de enteros no negativos 𝑞 , 𝑟 tal que: 𝒂 = 𝒃𝒒 + 𝒓 , 𝟎 ≤ 𝒓 < 𝒃 Ejemplos: • Dado 𝑎 = 16 , 𝑏 = 3 ⇒ 16 = 3𝑞 + 𝑟 , se cumple para 𝑞 = 5 y 𝑟 = 1 • Dado 𝑎 = 3 , 𝑏 = 10 ⇒ 3 = 10𝑞 + 𝑟 , se cumple para 𝑞 = 0 y 𝑟 = 3 • Dado 𝑎 = 240 , 𝑏 = 48 ⇒ 240 = 48𝑞 + 𝑟 , se cumple para 𝑞 = 5 y 𝑟 = 𝟎 . Definición: Sean n y d enteros , d ≠ 0 . Se dice que d divide a n si existe un entero q que satisface n = dq . Se llama cociente y d , el divisor o factor de n . Si d divide a n , se escribe d | n . Ejemplos: • 5|30 porque 30=5(6) • 7|84 porque 84=7(12) • Los divisores positivos de 30 son: 1, 2, 3, 5, 6, 10, 15, 30 • Los divisores positivos de 63 son: 1, 3, 7, 9, 21, 63 Teorema: Sean 𝑎 , 𝑏 y 𝑐 números enteros no negativos con 𝑎 ≠ 0 . 1. Si 𝑎|𝑏 y 𝑎|𝑐 , entonces 𝑎|(𝑏 + 𝑐) 2. Si 𝑎|𝑏 y 𝑎|𝑐 , donde 𝑏 > 𝑐 , entonces 𝑎|(𝑏 − 𝑐) 3. Si 𝑎|𝑏 o 𝑎|𝑐 , entonces 𝑎|(𝑏𝑐) 4. Si 𝑎|𝑏 y 𝑏|𝑐 y 𝑏 ≠ 0 , entonces 𝑎|𝑐 Ejemplos 1. Si 3 | 6 y 3 | 9 , entonces: 2. Si 2 | 8 y 2 | 6, entonces: UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 3 3. Si 2 | 6 o 2 | 4 , entonces: 4. Si 2 | 6 y 6 | 12 , entonces: Máximo común divisor (MCD) El Máximo Común Divisor de dos números enteros m y n (diferentes de cero) es el entero positivo más grande que divide a los dos. Ejemplo: Divisores positivos de: 36: 1, 2, 3, 4, 6, 9, 12, 18, 36 45: 1, 3, 5, 9, 15, 45 Los divisores comunes son: 1, 3, 9 Por tanto, MCD (36, 45) = 9 Ejercicio: Calcular el MCD de 576 y 600. Algoritmo de Euclides Sea a un entero no negativo y b un entero positivo a = bq + r donde 𝟎 ≤ 𝒓 < 𝒃 MCD ( a , b ) = MCD ( b , r ) Ejemplo 1: Calcular el MCD de 324 y 252 324 = 252(1) +72 entonces MCD (324, 252) =MCD (252, 72) 252 = 72(3) +36 entonces MCD (252, 72) = MCD (72, 36) 72 = 36(2) +0 entonces MCD (72, 36) = 36 MCD (324, 252) = 36. Ejemplo 2: Calcular el MCD de 270 y 198 270 = 198(1) +72 198 = 72(2) +54 72 = 54(1) +18 54 = 18(3) +0 MCD (270, 198) = 18. Ejercicios: 1. Calcular el MCD de 462 y 756 2. Calcular el MCD de 4200 y 10560 UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 4 Teorema: Si 𝒅 es el 𝑴𝑪𝑫(𝒂, 𝒃) , entonces: 1. 𝑑 = 𝑠 ∙ 𝑎 + 𝑡 ∙ 𝑏 para algunos enteros 𝑠 y 𝑡 . 2. Si 𝑐 es cualquier otro divisor común de 𝑎 y 𝑏 , entonces 𝑐|𝑑 . Mínimo común múltiplo (MCM) Sean 𝑎 , 𝑏 y 𝑘 son enteros positivos tales que 𝒂|𝒌 y 𝒃|𝒌 . Diremos que 𝒌 > 𝟎 es un múltiplo común de 𝒂 y 𝒃 . Al menor valor 𝒌 de estas se le denomina: Mínimo Común Múltiplo de 𝒂 y 𝒃 , y se escribe 𝑴𝑪𝑴(𝒂, 𝒃) . Teorema: Si 𝒂 y b son dos enteros positivos, entonces : 𝑴𝑪𝑫(𝒂, 𝒃) ∙ 𝑴𝑪𝑴(𝒂, 𝒃) = 𝒂𝒃 Ejemplos: 1. Determine 𝑀𝐶𝐷(1032,180) Solución: 1032 = 180(5) + 132 180 = 132(1) + 48 132 = 48(2) + 36 48 = 36(1) + 12 → 𝑟 𝑛 36 = 12(3) + 0 → 𝑟 𝑛+1 ∴ 𝑀𝐶𝐷(1032,180) = 12 2. Exprese el 𝑀𝐶𝐷(1032,180) en la forma 𝑠 ∙ 1032 + 𝑡 ∙ 180 Solución: 1032 = 180(5) + 132 → 132 = 1032 − 180(5) 180 = 132(1) + 48 → 48 = 180 − 132(1) 132 = 48(2)…