Máximo divisor comum (m.d.c.) Algoritmo de Euclides, e números primos entre si...

O  Máximo divisor comum de dois ou mais números é o mesmo que encontrar o maior divisor comum entre os números.


 Por exemplo, para calcular o mdc de 15 e 20, temos que encontrar os divisores de cada número:

• Divisores de 15  (D₁₅₎ = {1,3,5,15.}
• Divisores de 20 (D₂₀₎ = {1,2,4,5,10,20}

 O Maior divisor comum entre 15 e 20 é  então 5, portanto, 

o mdc (15,20) = 5.




Vejamos  outro exemplo:
mdc (20,30,60) = 10

• D₂₀ = {1,2,4,5,10,20}
• D₃₀ = {1,2,3,5,6,10,15,30}
• D₆₀ = {1,2,3,4,5,6,10,12,15,20,30,60}

verificamos que   o maior divisor comum entre esses números é 10, 

portanto mdc(20,30,60) = 10.

Algoritmo de Euclides para determinar o m.d.c:

A aplicação do algoritmo de Euclides é outra forma de determinar  o máximo divisor comum entre dois números. Embora o nome possa meter-te medo, na verdade, trata-se de um processo simples para encontrar o m.d.c...se a este método chamarmos o método das divisões sucessivas, já é mais simples para ti, provavelmente! Imagina que queres encontrar o máximo divisor comum entre 70 e 42. Pelo processo que já aprendeste seria assim: D70={ 1, 2, 5, 7 ,10 ,14, 35, 70} D42={ 1, 2, 3, 6, 7, 14, 21, 42} 14  seria então o máximo divisor comum entre 70 e 42. No entanto, o algoritmo de Euclides, ou das divisões sucessivas permite calcular de forma mais rápida,  o máximo divisor comum entre dois números.  Mas antes de tudo lembras-te que  numa divisão temos: Observa a imagem abaixo e segue os passos que te vou indicando: Consegues calcular o m.d.c. (70,42)? 1º - Faz uma grelha como a que observas na imagem seguinte; 2º - Colocas o 70 (o teu primeiro dividendo) na segunda linha,  na coluna mais à esquerda e logo do seu lado direito o 42 (o teu primeiro divisor, ou seja, na primeira, linha segunda coluna); 3º - Divides o 70 pelo 42 e colocas o quociente obtido,  na primeira linha da tua grelha, por cima do teu primeiro divisor (42). Nesta primeira linha vão ser sempre colocados todos os quocientes  obtidos nas tuas divisões sucessivas. 70: 42=  1 +  28 4º - O resto da tua primeira divisão (28), vai ser colocado  por baixo do número maior (70). 5º- O resto "salta" para o lado do primeiro divisor  (ou seja, salta para o lado do 42) e será o teu próximo divisor! A próxima divisão a realizar, será então, 42:28 (sempre o maior número a servir de dividendo e, o resto anteriormente obtido, é o divisor); 42:28= 1 + 14 6º - E, novamente o resto vai para baixo do 42 (maior número agora) e também "salta" para o lado do anterior divisor (28),  que agora passa a dividendo! 7º - O processo pára quando se obtém o resto igual a zero e  nesta última divisão (neste caso 28:14) diz-se que este divisor  é o máximo divisor comum entre os dois números, ou seja 14. 28:14= 2 + 0 Agora é só treinar muito, para conseguires interiorizar este processo.  OBS: Será bem mais prático calcular o m.d.c desta forma quando os números são da ordem das centenas (por exemplo)... Consegues calcular o m.d.c. (259,182)? Experimenta e depois dá uma espreitadela no quadro a giz!

Vejamos agora a forma reduzida  de apresentação:

Como calcular o m.d.c. (848,656) através do Algoritmo de Euclides?

m.d.c. (848,656) = 16  ( pois o resto da última divisão é 0.)





OBS: Dois Números  são primos entre si quando o seu máximo divisor comum é 1.


Exemplo: como já vimos  o  mdc (15,20) = 5.

15:5=3  e   20:5= 4

Dividindo dois números pelo seu máximo divisor comum, obtém-se dois números primos entre si.

Dizemos que 4 e 5 são primos entre si, pois o seu máximo divisor comum é 1.

•  (D₅₎ = {1,5.}
•  (_D4) = {1,2,4}