Algoritmo de Euclides estendido: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
m grafia |
m + interwiki |
||
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 |
||
Linha 36: | Linha 36: | ||
'''MDC(120,23)''' = <math>120*(-9) + 47*23</math> |
'''MDC(120,23)''' = <math>120*(-9) + 47*23</math> |
||
[[de:Erweiterter euklidischer Algorithmus]] |
|||
[[fr:Algorithme d'Euclide étendu]] |
|||
[[lt:Išplėstinis Euklido algoritmas]] |
|||
[[nl:Uitgebreid algoritme van Euclides]] |
|||
[[vi:Giải thuật Euclid mở rộng]] |
|||
[[en:Extended Euclidean algorithm]] |
|||
[[Categoria:Teoria dos números]] |
[[Categoria:Teoria dos números]] |
Revisão das 02h00min de 1 de outubro de 2007
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 Navemente 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) =