Algoritmo de Euclides estendido: diferenças entre revisões

Origem: Wikipédia, a enciclopédia livre.
Conteúdo apagado Conteúdo adicionado
m r2.7.1) (Robô: A adicionar: cs:Rozšířený Eukleidův algoritmus
Linha 10: Linha 10:
== Entendendo o algoritmo ==
== Entendendo o algoritmo ==
Para encontrar o MDC(120,23) usando o [[Algoritmo de Euclides]], coloca-se da seguinte forma:
Para encontrar o MDC(120,23) usando o [[Algoritmo de Euclides]], coloca-se da seguinte forma:
(1) 120÷23 = 5 resta 5
(1) 120/23 = 5 resta 5
(2) 23÷5 = 4 resta 3
(2) 23/5 = 4 resta 3
(3) 5÷3 = 1 resta 2
(3) 5/3 = 1 resta 2
(4) 3÷2 = 1 resta 1
(4) 3/2 = 1 resta 1
(5) 2÷1 = 2 resta 0
(5) 2/1 = 2 resta 0


'''MDC(120,23)''' = 1
'''MDC(120,23)''' = 1

Revisão das 11h26min de 19 de outubro de 2012

O Algoritmo de Euclides estendido é uma das formas de se encontrar o máximo divisor comum (MDC) de dois números inteiros. Nele, ao invés de retornar um valor único, fornece a combinação linear, muito útil quando os inteiros são primos entre si. Por exemplo:

MDC(120,23) = 1

120 e 23 são inteiros primos entre si porque não existe um divisor maior do que 1 que divida ambos. O Algoritmo de Euclides estendido retorna:

ax + by = MDC(a, b)

ou seja:

MDC(120,23) 

Entendendo o algoritmo

Para encontrar o MDC(120,23) usando o Algoritmo de Euclides, coloca-se da seguinte forma:

(1)    120/23 = 5 resta 5
(2)    23/5 = 4 resta 3
(3)    5/3 = 1 resta 2
(4)    3/2 = 1 resta 1
(5)    2/1 = 2 resta 0 
MDC(120,23) = 1

Levando-se em conta apenas os restos encontrados, pode-se dizer que:

(1)     5 = 1*120 - 5*23
(2)     3 = 1*23 - 4*5   Substituindo o 5 temos
        3 = 1*23 - 4*(1*120 - 5*23)
        3 = -4*120 + 21*23
(3)     2 = 1*5 - 1*3    Substituindo o valor de 5 e 3 temos
        2 = 1(1*120 - 5*23) - 1(-4*120 + 21*23)
        2 = 5*120 - 26*23
(4)     1 = 1*3 - 1*2   Novamente substituindo 3 e 2
        1 = 1(-4*120 + 21*23) - 1(5*120 - 26*23)
        1 = -9*120 + 47*23

portanto, x = -9 e y = 47 e temos:

MDC(120,23) = 

Referências

Ícone de esboço Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.
Ícone de esboço Este artigo sobre informática é um esboço. Você pode ajudar a Wikipédia expandindo-o.