CLASE AUXILIATURA
Auxiliar: Marcos Canedo
Fecha: 31-05-21
Hora: 16:00-18:00
MÁXIMO COMÚN DIVISOR Y MÍNIMO COMÚN MÚLTIPLO
Recordemos que la divisibilidad nos proporciona un orden en los enteros positivos, por
ejemplo para los divisores de 70:
70
Retícula de los divisores de 70
En esta retícula, se tiene qu
10 14 35
70 es el máximo y que 1 e
el mínimo.
2 5 7
Cuando estudiamos divisores comunes podíamos ver que se generaba una retícula común:
Divisores del 70 Divisores del 110
70 110
35 10 22 55
10 14
2 5 7 2 5 11
1 1
Se tiene una retícula común, justamente la retícula de los divisores del 10.
Esta retícula, de los divisores comunes tiene un máximo y un mínimo.
El máximo es 10, el mínimo es 1.
Observación: Todo par de números a, b tiene como mínimo común divisor al 1.
Es un divisor trivial. No tiene importancia.
Estaremos interesados mas bien en el máximo común divisor, puede variar.
Definición. (Máximo común divisor)
Sean a, b ∈ Z decimos que d es el máximo común divisor de a, b si:
1. d es divisor común de a y b, es decir: d|a, d|b
2. d es el mayor divisor común en el sentido del orden, esto es, si x es un divisor común
entonces x|d, es decir:
x|a, x|b → x|d
Se denota el mcd de a, b por (a, b). Es el máximo común divisor positivo.
12. Sea n un numero natural. Dados los n enteros consecutivos,
a, a + 1, a + 2, . . . , a + n − 1
mostrar que uno de ellos es divisible por n.
Observar que dividiendo a entre n:
a = qn + r donde 0 ⩽ r < n
Como 0 ⩽ r < n entonces 0 < n - r ⩽ n luego sea k = n - r , r + k = n
Luego se tiene que:
0⩽r<n
0<k⩽n
Tal que r + k = n
Luego observe que:
a + k = qn + (r + k) = qn + n = n(q + 1)
Luego a + k = n(q + 1) es decir n divide a a + k .
Si k = n entonces n|a + n luego como n|n entonces n|a.
En otras palabras si k = n entonces r = 0 luego n|a.
En otro caso:
Luego vea que 0 < k < n, entonces a + k es uno de los siguientes números:
a + 1, a + 2,..., a + (n - 1)
De ambos casos se concluye que n divide a alguno de los siguientes números:
a, a + 1, a + 2,..., a + (n - 1)
LEMA
La divisibilidad cumple las siguietes propiedades:
1. Si a|b entonces a|bc donde c ∈ Z.
2. Si a|b y a|c entonces a|b ± c
n
3. Si a|b i para i = 1,..., n entonces a|∑ 𝛼 i b i
i=1
Demostración
1. Si a|b entonces b = ka para algún k ∈ Z.
Luego bc = (kc)a donde kc ∈ Z puesto que k, c ∈ Z
Esto significa que a|bc.
2. Si a|b y a|c entonces b = k 1 a, c = k 2 a para k i ∈ Z con i = 1, 2
Luego b ± c = k 1 a ± k 2 a = (k 1 ± k 2 )a
Entonces b ± c = (k 1 ± k 2 )a observar que k 1 ± k 2 ∈ Z .
Luego a|b ± c
3. Si a|b i para i = 1,..., n entonces por 1) a|𝛼i bi con 𝛼i ∈ Z.
Luego observar que:
𝛼i bi = ki a donde ki ∈ Z
Sumando todo:
∑ 𝛼i bi = ∑ ki a = a∑ ki
Luego a| ∑ 𝛼i bi .
13. Probar que n 2 − 2 (n un entero) no es divisible por 4.
Dividimos n entre 4.
Por el algoritmo de la división:
n = 4q + r , 0 ⩽ r < 4
Luego:
n 2 = (4q + r) 2 = 16q 2 + 8qr + r 2 = 4 4q 2 + 2qr + r 2
Si r = 0 entonces n 2 es múltiplo de 4, deja resto 0
Si r = 1 entonces n 2 deja resto 1.
Si r = 2 entonces n 2 = 4 4q 2 + 2qr + 2 2 = 4 4q 2 + 2qr + 4 = 4 4q 2 + 2qr + 1 deja
resto 0.
Si r = 3 entonces n 2 = 4 4q 2 + 2qr + 3 2 = 4 4q 2 + 2qr + 9 = 4 4q 2 + 2qr + 8 + 1
= 4 4q 2 + 2qr + 2 + 1 deja resto 1.
Esto significa que n 2 siempre deja resto 0 ó 1.
Por tanto n 2 - 1 es múltiplo o n 2 es múltiplo de 4.
Los otros casos son imposibles puesto que si n 2 - 2 fuese múltiplo de 4 entonces
n 2 - 2 = 4q
luego:
n 2 = 4q + 2
El resto sería 2 lo cual es imposible.
14. Dados los enteros a y x, con a > 1, a|(11x + 3) y a|(55x + 52) , encontrar a.
Observar que:
a|(11x + 3) por tanto a|5(11x + 3) es decir a|(55x + 15)
Luego a|(55x + 15) y a|(55x + 52) luego también divide la resta de ambos:
a|37
Pero 37 es primo, entonces a = 37 ó a = 1.
Pero a > 1 entonces a = 37.
Lema. Si a|b y b|a entonces a = ±b
Demostración.
Como a|b entonces b = ka para algún k ∈ Z
Como b|a entonces a = qb para q ∈ Z
Luego b = ka = k(qb) = (kq)b si b ≠ 0 entonces cancelamos b y nos queda:
1 = kq
Luego k = q = 1 ó k = q = -1
Esto significa que a = ±b.
Si b = 0 entonces b = ka entonces ka = 0 luego a = 0 ó k = 0.
Pero a = qb = q ⋅ 0 = 0 entonces a = 0. Entonces a = ±0 = ±b
Siempre a = ±b
TEOREMA: Dados a, b enteros se tiene que (a, b) = (b, a ± qb) con q ∈ Z.
Demostración.
Sea d = (a, b) , d' = (b, a ± qb)
d|a, d|b luego d|qb , luego d|(a ± qb)
Luego d|b, d|a ± qb por tanto d|d'
Luego d'|b, d'|a ± qb como d'|b entonces d'|qb, luego d'|(a ± qb) ∓ qb es decir d'|a
Luego d'|a, d'|b por tanto d'|d
En conclusión d|d' y d'|d por el lema d = ±d' como ambos son positivos entonces d = d'.
Esto es (a, b) = (b, a ± qb)
Corolario
Por el algoritmo de la divisón:
a = bq + r
Luego (a, b) = (b, a - bq) = (b, r)
Hallar (a, b) es lo mismo que hallar (b, r).
Ejemplo. Hallar (174, 42)
(174, 42) = (42, 6) = (6, 0) = 6
Nota (a, 0) = a siempre que a ≠ 0.
Sin usar calcuadora:
(174, 42) = (42, 174 - 42 × 3) = (42, 174 - 126) = (42, 48) = (48, 42 - 48) = (48, -6) = 6
Teorema
Sean a, b enteros no ambos cero, entonces existen x, y enteros tal que:
ax + by = (a, b)
Ejemplo.
(2, 3) = 1 y observar que: 3(1) + 2(-1) = 1
Ejemplo.
Hallar el mcd de los siguientes números y expresarlo como combinación lineal.
a = 93, b = 119
119 = (1) × 93 + 26
93 = 26 × 3 + 15
26 = 15 × 1 + 11
15 = 11 × 1 + 4
11 = 4 × 2 + 3
4 = 3×1+1
3 = 1×3+0
Luego: (119, 93) = 1
Queremos expresar 119x + 93y = 1
De la igualdad:
4 = 3×1+1
4-3×1 = 1
Pero:
11 = 4 × 2 + 3
11 - 4 × 2 = 3
Reemplazo 3:
4 - (11 - 4 × 2) = 1
-11 + 4 × 3 = 1
Pero de la igualdad 15 = 11 × 1 + 4 se tiene que 4 = 15 - 11 reemplazando:
-11 + (15 - 11) × 3 = 1
15 × 3 - 11 × 4 = 1
Pero de la igualdad 26 = 15 × 1 + 11 nos queda: 11 = 26 - 15 reemplazando:
15 × 3 - 11 × 4 = 1
15 × 3 - (26 - 15) × 4 = 1
15 × 3 - 26 × 4 + 15 × 4 = 1
-26 × 4 + 15 × 7 = 1
Pero de la igualdad: 93 = 26 × 3 + 15 se tiene que 15 = 93 - 26 × 3
Reemplazando:
-26 × 4 + (93 - 26 × 3) × 7 = 1
93 × 7 - 26 × 25 = 1
Pero de la igualdad 119 = (1) × 93 + 26 se tiene que: 26 = 119 - 93
93 × 7 - (119 - 93) × 25 = 1
-119 × 25 + 93 × 32 = 1
Nos queda:
119(-25) + 93(32) = 1
Hemos hallado que x = -25, y = 32