Algoritmo de Euclides estendido: diferenças entre revisões
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) |
(1) 120/23 = 5 resta 5 |
||
(2) |
(2) 23/5 = 4 resta 3 |
||
(3) |
(3) 5/3 = 1 resta 2 |
||
(4) |
(4) 3/2 = 1 resta 1 |
||
(5) |
(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
- Coutinho, Severino Coller. Números inteiros e criptografia RSA. Rio de Janeiro: IMPA, 2005. 226 p. ISBN 8524401249
- Knuth, D. E. The art of computer programming: Seminumerical algorithms. Vol. 2. 3ed. Addilson-Wesley Publishing Company. ISBN 9780201896848