R A M A A Z U L
ARITMETICA
MAXIMO COMUN DIVISOR Y MINIMO COMUN MULTIPLO
Sabido es que el máximo común divisor entre a y b es el mayor de los
divisores comunes de a y b; y que el mínimo común múltiplo entre a y b (no am-
bos nulos) es el menor de los múltiplos comunes positivos.
Notamos m.c.d. (a,b) = (a,b)
m.c.m. (a,b) = [a,b]
I- Si a,b son positivos y b es múltiplo de a, vale que
(a,b) = a y [a,b] = b.
II- El máximo común divisor entre a y b es igual al máximo común divisor entre
b y el resto de dividir a por b.
Esto es una consecuencia de que los divisores comunes de a y b son los
mismos que los divisores comunes de b y r(a:b) :
Como a = b.q + r(a:b)
Si d|a y d|b entonces d|b y d|r(a:b) = a-b.q y recíprocamente:
Si d|b y d|r(a:b) entonces d|b y d|( b.q+r(a:b) ) = a.
Se puede aplicar este resultado para calcular el m.c.d. entre números
grandes:
Ej: Calcular (56004,22524)
56004 = 22524.2 + 10956 (56004,22524) = (22524,10956)
22524 = 10956.2 + 612 = (10956,612) =
10956 = 612.17 + 552 = (612,552) =
612 = 552.1 + 60 = (552,60) =
552 = 60.9 + 12 = (60,12) =
60 = 12.5 + 0 = 12.
En las sucesivas divisiones, el divisor y el resto de cada división, pasan
a ser dividendo y divisor, respectivamente, de la siguiente división.
Cuando en una de estas divisiones se obtiene resto cero, el m.c.d. buscado
es el resto obtenido en la división inmediata anterior.
III- (a,b) es el menor de los enteros positivos que puede escribirse como com-
binación lineal entera de a y de b; esto es, existen x î Z, y î Z tales que
(a,b) = x.a + y.b
De aquí se sigue que si d es un divisor común de a y de b, entonces
d|(a,b):
Si d|a y d|b, entonces d|x.a , d|y.b. Luego, d|( x.a + y.b) = (a,b).
Esta posibilidad de escribir el m.c.d. como combinación lineal entera de
a y b, es útil para obtener propiedades del m.c.d.
Ejemplo. PROPIEDAD UTIL: Si a|b.c y (a,b) = 1 entonces a|c.
Como (a,b) = 1, existen r,s î Z tales que
1 = r.a + s.b, luego (multiplicando por c)
c = r.a.c + s.(b.c)
Como a divide a los dos sumandos de la izquierda, se sigue que a|c.
Para obtener enteros x, y tales que (a,b) = x.a + y.b, también podemos
utilizar sucesivas divisiones.
Ejemplo: Encontrar x, y enteros tales que 4 = 12x + 20 y.
Es 4 = (12,20).
(1) 20 = 12.1 + 8
(2) 12 = 8.1 + 4
(3) 8 = 4.1 + 0
De (2) se sigue que 4 = 12 + (-1).8 = (A).
De (1), despejamos el resto (8) y lo reemplazamos:
(A) = 12 + (-1) [ 20 + (-1).12] =
= 12 + (-1).20 + 12 = 2.12 + (-1).20
Por lo tanto, 4 = 2.12 + (-1).20
x = 2 e y = -1 sirven.
¿Cuáles son todas las soluciones?
n Ó(i) n á(i)
IV- Si a = ã p(i) y b = ã p(i) entonces
i=1 i=1
n mín{Ó(i),á(i)} n máx{Ó(i),á(i)}
(a,b) = ã p(i) y [a,b] = ã p(i)
i=1 i=1
V- a.b = (a,b).[a,b].
PROBLEMAS
1. Tres amigos pasean en bicicleta por un camino de una sola mano que bordea
un lago. Para dar una vuelta completa, uno de ellos tarda 15 minutos, otro
tarda 18 y el tercero tarda 20 minutos. Parten juntos y acuerdan interrumpir
el paseo la primera vez que los tres pasen simultáneamente por el punto de
partida. ¿Cuánto tiempo anduvieron en bicicleta? ¿Cuántas vueltas dio cada
uno?
2. Encontrar todos los números enteros a, b tales que (a,b) = 6 y [a,b] = 1200.
3. Encontrar todos los a, b î Z tales que
(a,b) = 2a - b
[a,b] = 73a
4. Calcular (5a+7b,2a+3b), sabiendo que (a,b) = 3 .
n n n+1 n+1
5. Demostrar que ( 2 + 3 , 2 . 3 ) = 1
