Algoritmo de Euclides estendido

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Text document with red question mark.svg
Este artigo ou secção contém uma ou mais fontes no fim do texto, mas nenhuma é citada no corpo do artigo, o que compromete a confiabilidade das informações. (desde novembro de 2013)
Por favor, melhore este artigo introduzindo notas de rodapé citando as fontes, inserindo-as no corpo do texto quando necessário.

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)  = 120*(-9) + 23*47 

Entendendo o algoritmo[editar | editar código-fonte]

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) = 120*(-9) + 47*23

O algoritmo[editar | editar código-fonte]

Uma implementação do algoritmo em JavaScript:


/*********************************************
*  Recebe dois inteiros não negativos a e b
* e devolve um vetor cuja primeira posição
* é o mdc(a,b), a segunda posição é o valor u
* e a terceira o valor v tais que
*   a*u + b*v = mdc(a,b)
**********************************************/
function euclides (a, b){
	var r = a;
	var r1 = b;
	var u = 1;
	var v = 0;
	var u1 = 0;
	var v1 = 1;
        // variáveis auxiliares para efetuar trocas
	var rs, us, vs, q;
 
	while (r1 != 0){
		q = parseInt (r / r1); // pega apenas a parte inteira
		rs = r;
		us = u;
		vs = v;
		r = r1;
		u = u1;
		v = v1;
		r1 = rs - q *r1;
		u1 = us - q*u;
		v1 = vs - q*v1;
	}
 
	return [r, u, v]; // tais que a*u + b*v = r et r = pgcd (a, b)
}

Referências[editar | editar código-fonte]

  • Coutinho, Severino Collier. Números inteiros e criptografia RSA. Rio de Janeiro: IMPA, 2005. 226 pp. ISBN 8524401249
  • Knuth, D. E.. The art of computer programming: Seminumerical algorithms (em inglês). 3 ed. [S.l.]: Addilson-Wesley Publishing Company. vol. 2. ISBN 9780201896848
Í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.