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

volver anteriorsiguiente