{"id":7507,"date":"2013-07-23T20:54:27","date_gmt":"2013-07-23T23:54:27","guid":{"rendered":"http:\/\/clubes.obmep.org.br\/blog\/?page_id=7507"},"modified":"2025-06-22T21:44:30","modified_gmt":"2025-06-23T00:44:30","slug":"sala-de-estudos-algoritmo-de-euclides-para-determinacao-de-mdc","status":"publish","type":"page","link":"https:\/\/clubes.obmep.org.br\/blog\/sala-de-estudos-algoritmo-de-euclides-para-determinacao-de-mdc\/","title":{"rendered":".Sala de Estudos: Algoritmo de Euclides para determina\u00e7\u00e3o de MDC"},"content":{"rendered":"

\n\n\n
\n

• MDC<\/strong> eu sei que significa o M<\/strong>\u00e1ximo D<\/strong>ivisor C<\/strong>omum entre dois ou mais n\u00fameros naturais.
\n• Algoritmo <\/strong>\u00e9 uma sequ\u00eancia finita de passos a serem seguidos para a execu\u00e7\u00e3o de uma tarefa.
\n• Euclides <\/strong><\/span><\/a>foi um importante matem\u00e1tico grego da antiguidade.
\nMas eu n\u00e3o conhe\u00e7o o Algoritmo de Euclides para determina\u00e7\u00e3o de MDC . . .<\/strong><\/span> <\/p>\n

<\/td>\n

\"Probleminha2\"<\/td>\n<\/tr>\n<\/table>\n\n\n
\"\"<\/td>\n\n

Esse algoritmo \u00e9 uma importante ferramenta da Teoria de N\u00fameros e \u00e9 muito simples de ser executado.
\nVamos estud\u00e1-lo; mas, antes, \u00e9 bom recordar que o m\u00e1ximo divisor comum de dois n\u00fameros naturais [tex]a[\/tex] e [tex] b [\/tex] \u00e9 o maior dos n\u00fameros que dividem tanto [tex]a[\/tex] quanto [tex] b [\/tex]<\/strong><\/span>.
\nNas nossas discuss\u00f5es, vamos indicar o MDC de [tex]a[\/tex] e [tex]b[\/tex] por [tex]mdc(a,b)[\/tex].<\/span><\/p>\n

<\/td>\n<\/tr>\n<\/table>\n

\n

\n

\n

Algoritmo de Euclides para determina\u00e7\u00e3o de MDC<\/strong><\/span><\/p>\n

\n
\n

\n

\"F1\"
\n <\/p>\n

\n<\/p>\n

Antes de prosseguirmos, observe que, no c\u00e1lculo do MDC dos n\u00fameros naturais [tex]a[\/tex] e [tex]b[\/tex], n\u00e3o precisamos nos preocupar quando a condi\u00e7\u00e3o [tex]\\boxed{a>b>0}[\/tex] n\u00e3o for satisfeita, uma vez que:
\n[tex] \\, \\, \\, (i) \\, \\, mdc(0,0)[\/tex] n\u00e3o est\u00e1 definido;
\n[tex] \\, \\, \\, (ii) \\, \\, mdc(n,n) = n[\/tex], para qualquer natural n\u00e3o nulo [tex]n[\/tex];
\n[tex] \\, \\, \\, (iii) \\, \\, mdc(m,n) = mdc(n,m)[\/tex], para quaisquer n\u00fameros naturais n\u00e3o ambos nulos [tex]m[\/tex] e [tex]n[\/tex];
\n[tex] \\, \\, \\, (iv) \\, \\, mdc(n,0) = n[\/tex], para qualquer n\u00famero natural n\u00e3o nulo [tex]n[\/tex].<\/span><\/p>\n

Voc\u00eas saberiam justificar essas quatro afirma\u00e7\u00f5es?<\/strong><\/span><\/p>\n<\/div>\n

\n\n\n
\n

T\u00e1…
\nMas como calcular o m\u00e1ximo divisor comum de n\u00fameros naturais [tex]m[\/tex] e [tex]n[\/tex], com [tex]m \\gt n\\gt0[\/tex], sabendo que se [tex]r[\/tex] \u00e9 o resto da divis\u00e3o de [tex]m[\/tex] por [tex]n[\/tex], ent\u00e3o [tex]mdc(m,n)=mdc(n,r)[\/tex]?<\/span><\/p>\n

<\/td>\n

\n\"Desafio2\"<\/td>\n<\/tr>\n<\/table>\n\n\n
\n\"\"<\/td>\n\n

O primeiro passo voc\u00ea j\u00e1 deu: entendeu a propriedade que gera o algoritmo…
\nE, neste momento, n\u00e3o \u00e9 necess\u00e1rio saber justificar essa propriedade. Basta entend\u00ea-la e aplic\u00e1-la com cuidado, conforme veremos a seguir.
\nMas, antes, vamos destacar mais uma vez essa propriedade, pois \u00e9 ela que garante o sucesso do processo! <\/span><\/p>\n

<\/td>\n<\/tr>\n<\/table>\n

\n

\n

IMPORTANTE<\/strong><\/u><\/p>\n

O m\u00e1ximo divisor comum entre dois n\u00fameros naturais n\u00e3o nulos e distintos \u00e9 igual ao m\u00e1ximo divisor entre o menor e o resto da divis\u00e3o do maior pelo menor.
\nEm s\u00edmbolos, se [tex]x \\, [\/tex] e [tex] \\, y \\, [\/tex] s\u00e3o n\u00fameros naturais tais que [tex] \\, x\\gt y\\gt 0 \\, [\/tex], e se <\/p>\n

\n\n\n\n
[tex]x[\/tex] <\/td>\n [tex]y[\/tex] <\/td>\n<\/tr>\n
[tex]r [\/tex]<\/td>\n [tex]q[\/tex] <\/td>\n<\/table>\n<\/div>\n

ent\u00e3o [tex]\\fcolorbox{black}{#CDC9C9}{$mdc(x,y)=mdc(y,r)$}[\/tex].\n<\/p><\/div>\n

<\/p>\n

\n

O Processo <\/strong><\/p>\n

\n
\n

\n

1) Pelo at\u00e9 agora exposto, para calcularmos o MDC de dois n\u00fameros naturais [tex]a[\/tex] e [tex]b \\, [\/tex] tais que [tex]a \\gt b \\gt 0[\/tex], fazemos a divis\u00e3o euclidiana de [tex]a[\/tex] por [tex]b \\, [\/tex]:<\/p>\n

\n\n\n\n
[tex]a[\/tex] <\/td>\n [tex]b[\/tex] <\/td>\n<\/tr>\n
[tex]r_1 [\/tex]<\/td>\n [tex]q_1[\/tex] <\/td>\n<\/table>\n

com [tex]0\\le r_1 \\le b[\/tex].<\/p><\/div>\n

[tex] \\, \\, \\bullet[\/tex] Se o resto dessa divis\u00e3o for zero, ent\u00e3o [tex]mdc(a,b) = mdc(b,0)=b[\/tex] e acabou o problema. (veja [tex](iv)[\/tex])
\n[tex] \\, \\, \\bullet[\/tex] Caso o resto [tex]r_1[\/tex] seja diferente de zero, ent\u00e3o [tex]mdc(a,b) = mdc(b, r_1)[\/tex] e passamos a nos preocupar agora com o MDC de [tex]b[\/tex] e [tex]r_1[\/tex].
\n 
\n2) Fa\u00e7amos, ent\u00e3o, a divis\u00e3o euclidiana de [tex]b[\/tex] por [tex]r_1[\/tex]: <\/p>\n

\n\n\n\n
[tex]b[\/tex] <\/td>\n [tex]r_1[\/tex] <\/td>\n<\/tr>\n
[tex]r_2 [\/tex]<\/td>\n [tex]q_2[\/tex] <\/td>\n<\/table>\n

com [tex]0\\le r_2 \\le r_1[\/tex].<\/p><\/div>\n

[tex] \\, \\, \\bullet[\/tex] Se o resto dessa divis\u00e3o for zero, ent\u00e3o [tex]mdc(a,b) = mdc(b, r_1)= mdc(r_1, 0)=r_1[\/tex] e acabou o problema.
\n[tex] \\, \\, \\bullet[\/tex] Caso o resto [tex]r_2[\/tex] seja diferente de zero, ent\u00e3o [tex]mdc(b, r_1)= mdc(r_1, r_2)[\/tex] e agora vamos determinar o MDC de [tex]r_1[\/tex] e [tex]r_2[\/tex].
\n 
\n3) Fa\u00e7amos, pois, a divis\u00e3o euclidiana de [tex]r_1[\/tex] por [tex]r_2[\/tex]: <\/p>\n

\n\n\n\n
[tex]r_1[\/tex] <\/td>\n [tex]r_2[\/tex] <\/td>\n<\/tr>\n
[tex]r_3 [\/tex]<\/td>\n [tex]q_3[\/tex] <\/td>\n<\/table>\n

com [tex]0\\le r_3 \\lt r_2[\/tex].<\/p><\/div>\n

[tex] \\, \\, \\bullet[\/tex] Se o resto dessa divis\u00e3o for zero, ent\u00e3o [tex]mdc(a,b) = mdc(b, r_1)= mdc(r_1, r_2)= mdc(r_2, 0)=r_2[\/tex] e acabou o problema.
\n[tex] \\, \\, \\bullet[\/tex] Se o resto [tex]r_3[\/tex] for diferente de zero, ent\u00e3o [tex]mdc(r_1, r_2)= mdc(r_2, r_3)[\/tex] e agora passamos a nos preocupar com o MDC de [tex]r_2[\/tex] e [tex]r_3[\/tex].
\n 
\n4) Fa\u00e7amos, agora, a divis\u00e3o euclidiana de [tex]r_2[\/tex] por [tex]r_3[\/tex]: <\/p>\n

\n\n\n\n
[tex]r_2[\/tex] <\/td>\n [tex]r_3[\/tex] <\/td>\n<\/tr>\n
[tex]r_4 [\/tex]<\/td>\n [tex]q_4[\/tex] <\/td>\n<\/table>\n

com [tex]0\\le r_4 \\lt r_3[\/tex].<\/p><\/div>\n

[tex] \\, \\, \\bullet[\/tex] Se o resto dessa nova divis\u00e3o for zero, ent\u00e3o o problema est\u00e1 resolvido, pois
\n[tex]~~mdc(a,b) = mdc(b, r_1)= mdc(r_1, r_2)=mdc(r_2, r_3)=mdc(r_3, 0)=r_3[\/tex].
\n[tex] \\, \\, \\bullet[\/tex] Se o resto [tex]r_4[\/tex] for diferente de zero, ent\u00e3o [tex]mdc(r_2, r_3)= mdc(r_3, r_4)[\/tex] e agora passamos a nos preocupar com o MDC de [tex]r_3[\/tex] e [tex]r_4.[\/tex]<\/p>\n

Esse processo de divis\u00f5es sucessivas n\u00e3o ter\u00e1 fim?<\/strong><\/p>\n

Observe que, se nas nossas divis\u00f5es obtivermos um resto [tex]r_{n+1}[\/tex] igual a zero, o processo termina pois
\n[tex] \\, \\, \\, \\, \\, \\, mdc(a,b) = mdc(b, r_1)= mdc(r_1, r_2)=mdc(r_2, r_3)=\\cdots=\\\\
\n \\, \\, \\, \\, \\, \\, \\, \\, \\, \\, \\, \\, \\, \\, \\qquad \\; \\; \\; =mdc(r_{n-1}, r_{n})=mdc(r_{n}, r_{n+1})=mdc(r_{n}, 0)=r_ n[\/tex]
\nAssim, esse processo de divis\u00f5es sucessivas s\u00f3 n\u00e3o ir\u00e1 terminar se n\u00e3o obtivermos um resto nulo<\/strong>.
\nEnt\u00e3o, cabe a pergunta: \u00e9 poss\u00edvel n\u00e3o obtermos um resto zero?<\/strong>
\nObservemos os restos obtidos at\u00e9 a quarta divis\u00e3o: [tex]0\\lt r_4 \\lt r_3 \\lt r_2 \\lt r_1 \\lt b[\/tex].
\nDe maneira geral, quando encontramos um resto n\u00e3o nulo efetuamos uma divis\u00e3o cujo resto \u00e9 menor do que o resto anterior, que j\u00e1 era menor que o seu anterior.
\nAssim, se n\u00e3o encontrarmos um resto zero, obteremos uma sequ\u00eancia decrescente de infinitos n\u00fameros naturais n\u00e3o nulos, todos menores do que [tex]b [\/tex]:
\n[tex] \\, \\, \\, \\, \\, \\, b>r_1>r_2>r_3>r_4>\\cdots>0[\/tex]
\no que n\u00e3o \u00e9 poss\u00edvel, pois sabemos que existem apenas [tex]b-1[\/tex] n\u00fameros naturais n\u00e3o nulos que s\u00e3o menores do que [tex]b[\/tex].<\/p>\n

Ufa…., ent\u00e3o o processo acaba e o [tex]mdc(a,b)[\/tex] \u00e9 o \u00faltimo resto n\u00e3o nulo do processo de divis\u00f5es sucessivas.<\/strong><\/p>\n<\/p><\/div>\n

\n\n\n
\n

Hummmmm, acho que entendi…
\nA ideia \u00e9 dividir o maior n\u00famero pelo menor, e depois fazer divis\u00f5es sucessivas do \u00faltimo divisor pelo \u00faltimo resto, at\u00e9 obtermos uma divis\u00e3o exata. <\/span><\/p>\n

<\/td>\n

\n\"carinha4\"<\/td>\n<\/tr>\n<\/table>\n\n\n
\n\"\"<\/td>\n\n

Isso mesmo!
\nPodemos, ent\u00e3o, aplicar o processo.<\/span><\/p>\n

<\/td>\n<\/tr>\n<\/table>\n

\n

\n

Dois exemplos <\/strong><\/p>\n

\n
\n1) Calcular mdc(32,12) <\/strong>.
\n 
\nPara tanto executaremos o processo das divis\u00f5es sucessivas, iniciando pela divis\u00e3o euclidiana de 32 por 12:<\/p>\n
\n\n\n\n
32 <\/td>\n 12 <\/td>\n      <\/td>\n 12 <\/td>\n 8 <\/td>\n      <\/td>\n 8 <\/td>\n 4 <\/td>\n<\/tr>\n
8<\/td>\n 2 <\/td>\n      <\/td>\n4<\/td>\n 1 <\/td>\n      <\/td>\n0<\/td>\n 2 <\/td>\n<\/tr>\n<\/table>\n<\/div>\n

Assim, podemos afirmar que mdc(32, 12)=mdc(12, 8)=mdc(8,4)=mdc(4,0)=4 <\/strong> e, dessa forma, mdc(32,12)=4<\/strong>.
\n 
\n2) Calcular mdc(1320,25) <\/strong>.
\n 
\nMais uma vez, vamos executar o processo das divis\u00f5es sucessivas:<\/p>\n

\n\n\n\n
1320 <\/td>\n 35 <\/td>\n      <\/td>\n 35 <\/td>\n 25 <\/td>\n      <\/td>\n 25 <\/td>\n 10 <\/td>\n      <\/td>\n 10 <\/td>\n 5 <\/td>\n<\/tr>\n
25<\/td>\n 37 <\/td>\n      <\/td>\n10<\/td>\n 1 <\/td>\n      <\/td>\n5<\/td>\n 2 <\/td>\n      <\/td>\n0<\/td>\n 2 <\/td>\n<\/tr>\n<\/table>\n<\/div>\n

Assim,
\n mdc(1320, 35)=mdc(35, 25)=mdc(25,10)=mdc(10,5)=mdc(5,0)=5 <\/strong>
\ne, ent\u00e3o, mdc(1320,35)=5<\/strong>.\n<\/div>\n

\n\n\n
\n\"\"<\/td>\n\n

Podemos simplificar um pouco o processo.
\nVeja como, na pr\u00f3xima sala…
\n\u00c9 s\u00f3 clicar AQUI<\/strong><\/a>!<\/span><\/p>\n<\/td>\n<\/tr>\n<\/table>\n

\n

\n
\n

Sonia Regina Di Giacomo<\/strong>
\nEquipe COM – OBMEP<\/span><\/p>\n<\/div>\n

Setembro de 2016.<\/p>\n","protected":false},"excerpt":{"rendered":"

• MDC eu sei que significa o M\u00e1ximo Divisor Comum entre dois ou mais n\u00fameros naturais. • Algoritmo \u00e9 uma sequ\u00eancia finita de passos a serem seguidos para a execu\u00e7\u00e3o de uma tarefa. • Euclides foi um importante matem\u00e1tico grego da antiguidade. Mas eu n\u00e3o conhe\u00e7o o Algoritmo de Euclides para determina\u00e7\u00e3o de MDC . … <\/p>\n

Continue lendo<\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"template-onecolumn.php","meta":{"footnotes":""},"class_list":["post-7507","page","type-page","status-publish","hentry","nodate","item-wrap"],"_links":{"self":[{"href":"https:\/\/clubes.obmep.org.br\/blog\/wp-json\/wp\/v2\/pages\/7507","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/clubes.obmep.org.br\/blog\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/clubes.obmep.org.br\/blog\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/clubes.obmep.org.br\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/clubes.obmep.org.br\/blog\/wp-json\/wp\/v2\/comments?post=7507"}],"version-history":[{"count":190,"href":"https:\/\/clubes.obmep.org.br\/blog\/wp-json\/wp\/v2\/pages\/7507\/revisions"}],"predecessor-version":[{"id":222843,"href":"https:\/\/clubes.obmep.org.br\/blog\/wp-json\/wp\/v2\/pages\/7507\/revisions\/222843"}],"wp:attachment":[{"href":"https:\/\/clubes.obmep.org.br\/blog\/wp-json\/wp\/v2\/media?parent=7507"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}