Algoritmo de Euclides para calcular el m.c.d. de dos números

Cálculo del m.c.d. (máximo cómun divisor).

Relación de divisibilidad
 → múltiplo & divisor: ser múltiplo de; ser divisor de; o, dividir a.

Si dos números tienen relación de divisibilidad, uno de ellos contiene un numero exacto de veces al otro.

Ejemplo: 6 y 18  sí  tienen  relación de divisibilidad.

Si tienen relación de divisibilidad porque uno de ellos, el 18, contiene al otro, al 6, un número exacto de veces: en concreto 18 contiene tres veces al 6 

       → 6 x 3 = 18
           o bien 

       → 18 : 6 = 3 (con división entera exacta, ¡¡sin decimales!!)

Como 6 x 3 = 18 entonces 18 es múltiplo de 6 → hay algún entero que multiplicado por 6 da 18

Como 18 : 6 = 3 entonces 6 es un divisor de 18 → si la división de 18 entre 6 es exacta y entera.

Por tanto estas expresiones "a", "b" y "c" son equivalentes, son expresión de una misma relación de divisibilidad:

(a) 6 es divisor de 18, y, (b) 18 es múltiplo de 6, o bien, (c)  '6 divide a 18' (un número exacto de veces)

Contraejemplo: 6 y 9,  no  tienen  relación de divisibilidad.

6 y 9 no tienen relación de divisibilidad porque uno no contiene al otro un número exacto de veces.

9 sólo contiene al 6 una vez y media, o sea, 9 : 6 = 1'5  :-(

¿Cómo saberlo? ... si te sabes muy muy bien la tabla... de cualquier número...

o ¡dividiendo! → si 9 : 6 no da exacto (ni 6 : 9 tampoco da exacto) entonces no tienen esa relación

Los Divisores de un número

Todo número tiene al menos dos divisores. Por lo menos el 1 y el propio número.

Ejemplo: Divisores de 13

13 tiene el divisor 1 y el divisor 13, se anotan así: Div(13) = {1, 13}

y se lee... Todos los divisores de trece son el uno y el trece

Ejemplo: divisores de 14

14 tiene el divisor 1, el divisor 2, el divisor 7, y el divisor 14, se anota Div (14) = {1,2,7,14}

y se lee... todos los divisores de 14 son el uno, el dos, el siete y el catorce.

     ¡Siempre tienen al menos DOS divisores! y a veces tienen más de de dos divisores

Algunos números tienen más de dos divisores.

    → Los números son compuestos si tienen más de dos divisores, por ejemplo el 4 es compuesto.

   → Los números son primos si sólo tienen dos divisores, por ejemplo el 5 es primo.

Calculo de los divisores de un número

Para hallar todos los divisores de un número, basta ir dividiendo hasta que se encuentren todos.

¿Son muchos? Pues depende del número.

Pero como dividir suele costar trabajo, se ha estudiado mucho, y al final, se hacen 'pocas divisiones'

Ejemplo: Todos los divisores de 36

Divido 36:1= ; 36:2=; 36:3=;36:4=; 36:5=; 36:7=; 36:8=; ... ¿son muchas divisiones?

pues como mucho, la última que nos vale será 36:36=, porque desde ahi en adelante ninguna nos servirá porque no será exacta, ¿verdad?  36 : 37 = 0' algo;   36 : 38 = 0' algo menos, etc... !no vale ninguna mayor!

Propiedades que nos ayudan

a) Si el número no es divisible entre alguno, tampoco lo será entre los múltiplos, así que, nos podremos saltar todas las divisiones entre sus múltiplos.

Ejemplo: como 36 : 5 = 7'2 entonces 36 no es divisible entre cinco → tampoco lo será entre 10 ni entre 15 ni entre 20 ni entre 35 → ¡nos saltaremos cuatro divisiones! ¿esto anima?

Comprobamos si alguno de ellos es divisor de 36, con el 10, 15, 20, 25, 30, 35.-

36 : 10 = 3'6 ¡no sirve, 10 no es divisor de 36!;  

36 : 15 = 2'4 ¡tampoco sirve, 15 no es divisor de 36!; 

36 : 20 = 1'8 ¡tampoco, 20 no es divisor de 36!; 

36 : 25 = 1'44 ¡tampoco sirve, tampoco 25 es divisor de 36!

36 : 30 = 1'2 ¡tampoco, el 30 tampoco es divisor de 36!

36 : 35 = 1'0285... ¡tampoco!

Como esto pasa con cualquier número... esta propiedad nos conviene recordarla y la usaremos mucho.

¡Vamos que so!  Div(36) ={1, 2, 3, 4, 6, 9, 12, 18, 36} pero que bastan menos de 6 divisiones

y los divisores aparece emparejados. Div(36)={1-36, 2-18, 3-12, 4-9, 6-6} pero solo es u SEIS

b) Si vas dividiendo en orden... llega un momento en que los divisores que encuentras, ya los tenías: se repiten, y puedes para de hacer divisiones. ¿Te interesa?

Veamos

36 : 1 = 36 ¡bien! ya tengo un divisor de 36 que es el 1

    pero si divido 36 : 36 = 1, así que también el 36 es divisor de 36 ¡¡ya tengo DOSdivisores de 36!!

        ¡Ya tengo dos divisores! ¿habrá más?

Sigo dividiendo, en orden:   36 : 2 = 18 → el 2, y el 18 también son divisores de 36 ¡¡ya tengo 4 divisores!!

Sigo dividiendo, en orden:  36 : 3 = 12 → el 3 y el 12 también son divisores de 36 ¡¡Ahora tengo 6 divisores!!

Sigo dividiendo, en orden: 36 : 5 = 7'2 → el 5 no es divisor; pero TAMPOCO el 10, 15, 20, 25, 30, ni 35, ni los mayores de 36

Sigo dividiendo, en orden: 36 : 6 = 6 → el 6 y el 6 son divisores de 36, ¡ya tengo otro, 7 divisores!

Sigo dividiendo, en orden: 36 : 7 = 5'1428... → el 7 no es divisor, ni el 14, ni 21, ni 28, ni 35 (del 35 ya lo sabíamos), ni los mayores de 36

Sigo dividiendo, en orden: 36 : 8 = 4'5 → el 8 no es divisor, ni el 16, ni el 24, ni el 32, ni los mayores de 36

Sigo dividiendo, en orden: 36 : 9 = 4 → el 9 es un divisor, pero ¡ya lo teníamos! (cuando dividimos entre 4, lo encontramos)

Si sigues dividiendo, encontrarás que los que encuentres, ya los conocías.

Cuando se repetía el primero, ¡ya podíamos parar!, ¡¡ya los teníamos todos!!

¿Se podía parar antes?

Sí, se podia parar... cuando el cociente es menor que el divisor. Allí está

Veamos.

36 : 1 = 36; ¡dos!, el 1 y el 36, ¿sigo buscando? Como 36 >1 debo seguir buscando

36 : 2 = 18; como 18 > 2, debo seguir buscando más divisores

36 : 3 = 12; como ves cada vez toca a menos, pero como 12 > 3, debo seguir buscando

36 : 4 = 9; como 9 > 4, debo seguir buscando

36 : 5 = 7.5 ... debo seguir

36 : 6 = 6; como 6 = 6  ¡FIN!, no necesito seguir buscando, ya los tengo todos

36 : 7 = 5.14..., como 5'1 < 7, no debo seguir buscando, ya tengo todos los divisores: los demás se repetirán

Aún menos divisiones

Para hacer sólo las divisiones que tengan éxito... que den cociente entero exacto...

hay 'trucos' que nos adelantan si será o no será una división exacta: los Criterios de divisibilidad

Recordemos

Será divisibles entre dos si el número es múltiplo de 2 → usaré 'ser múltiplo' en lugar de 'ser divisible'

Será múltiplo de 2 si lo es la cifra de las uidades

Será múltiplo de 3 si lo es la suma de sus cifras

Será múltiplo de 4 si lo es el número formado por las deceanas y unidades

Será múltiplo de 5 si lo es la cifra de las unidades

Será múltiplo de 6 si es múltiplo de 2 y a la vez también de 3

Será múltiplo de 7 si ... (mejor haz la división)

Será múltiplo de 8 si lo es el número formado por las centenas, decenas y unidades

Será múltiplo de 9 si lo es el resultado de sumar sus cifras

Será múltiplo de 10 si lo es la cifra de sus unidades

Será múltiplo de 11 si... lo es la diferecia etre la suma de las cifras que ocupan lugar par menos la suma de las cifras que ocupa lugar impar.

Será múltiplo de 12 si lo es de 3 y a la vez de 4

...podríamos seguir pero con los más sencillos es suficiente

Aimando:

Para hallar todos los divisores de un número...
¿y son muchas divisiones?
Como mucho tantas divisioes como la raíz cuadrada del número
Por ejemplo, para hallar todos los divisores de 100 tendremos que hacer como mucho 10 divisioes,que o so tantas.

Divisores comunes de varios números

Se pueden hallar de al menos tres formas

a) Hallando todos los divisores de cada número y luego fijarse en los que son divisores comunes en los dos números, El más importate es el mayor de los comues.

b) Factorizando y tomando sólo ... comunes con el menor expoete

c) Usando el Algoritmo de Euclides

Primero lo probamos

Luego hacemos ejercicios

y al final daremos una idea de por qué funciona tan bien.

Ejercicio. Hallar todos los divisores comunes de 144 y 360

Porque tenemos dos excursiones de 144 personas de Portugal y 360 de Francia y queremos agruparlos en grupos más pequeños, que sean iguales y no quede nadie descolgado.

Solución:

Divido el mayor entre el menor, sin sacar decimales. 360 : 144 = 2 y resto 72

Divido el cociete,144, entre el resto de la división, sin sacar decimales: 144 : 72 = 2 y resto 0

Cuado el resto es cero FIN el mayor divisor común es el último resto distito de cero o ie... si eres duro de etedederas... será  el último divisor :72 es el mcd de 360 y 144

¡Ya! mi número es 72

Si intento dividir 72 entre el resto...72 : 0 = ¡¡math error!! dice mi calculadora...¡o puedo equivocarme!

     Todos los divisores comunes de 360 y 144 son todos los divisores de 72

     Y todos los divisores de 72 son... Div(72) = {1,2,3, 4, 6, 8, 9, 12,18,24,36, 72}

Me quedarán grupos iguales siempre que los haga de un número de estos

y no me quedará gente sin grupo

Es más, puedo mezclarlos juntando de las dos nacionalidades en grupos mixtos:

hago 1 grupo, hago 2 grupos de cada nacionalidad, 3 grupos, 4, 6,8,9 12, ... hasta 72

y cada grupo mezclado tendría: ...

¿Por qué esto es así? Dividiendo y dividiendo ¡sale!

   Recuerda. Si sumas dos múltiplos de 5 el resultado es también un múltiplo de 5. Y si los restas... también obtendrás un  múltiplo de 5. ¿Lo compruebas?

Pues... este es el alma del algoritmo.
Ejemplo:

Si 360 y 144 tienen un divisor común, ambos son múltiplos comunes de ese divisor ¿lo entiendes? Si lo entiedes, ya estás en el coraó del misterio.

....como dividir es restar,y restar, y restar... hasta que ya no se puede restar más:  los multiplos comunes de 144 y 360 no se pierden si los restamos...¡Genial! ueo, estará presetes e todos los resultados de las restas

...y como para restar deprisa, si siempre siempre se resta el mismo úmero el mismo número... es más rápido dividir

360 : 144 = 2 con resto 72 → 360 - 2·144 = 72 y hemos restado dos veces 144 a 360 y o podemos restar más veces... Como quedan 72 de resultado...

¡Ese 72 tiene los mismos divisores comues que 360 y 144!

Si divido 144 etre 72 ... estoy restando a 144 el 72 varias veces, así que como comparten los mismos divisores comues  144 : 72 = 2 co resto 0  entonces... 144 - 72·2 = 0   FIN ya o hay más divisores comues

El mayor divisor comun es ese 72

Todos los divisores de 72, lo so de 360 y también de 144

Colocación de las divisioes e el algoritmo.
a) Divide como quieras y o pierdas el orte,el ojetivofial,que es el último resto distito de cero