/* Algoritmo estendido de Euclides 
Uso: exteuclides(a,b)
onde a,b sao naturais
Output: [s,t,d]
onde d=(a,b) e as+bt=d */

\\ Pedro Patricio, 2009


exteuclides(a,b)=

{
	local( \\variaveis locais
	aorig, borig, aaux, qult, 
	qpenult, quoc, spenult, sult, tpenult, tult, 
	flag
	);
	
	aorig=a; borig=b; \\ guardar o input original para calcular o mdc
	if(a%b==0 || b%a==0, \\ caso estranho
		if(a<b,
			return([1,0,a]), \\ else
		        return([0,1,b])),
	/* else */
	flag=0; \\ flag de troca de valores a<b
	if(a<b, 
		aaux=a;
		a=b;
		b=aaux;
		aorig=a; borig=b; flag=1
	);
	spenult=1; sult=0;
	tpenult=0; tult=1;
	qpenult=a\b; print(a " " b " " qpenult); \\ prints de controlo..apagar 
	aaux=a; a=b; b=aaux%b;
	qult=a\b; print(a " " b " " qult);
	aaux=a; a=b; b=aaux%b;
	if(b==0,
		if(flag==0,
		return([-qpenult,1,-qpenult*aorig+borig]),
		/*else*/ return([1,-qpenult,-qpenult*aorig+borig])),
	\\else
	quoc=a\b; 
	resto=a%b;  print(a" "b " "quoc " " qult " " qpenult " resto:"resto);
	while(resto!=0,
		s=spenult-qpenult*sult; 
		t=tpenult-qpenult*tult;
		print("s="s  " qpenult="qpenult " qult="qult " quoc="quoc);
		qpenult=qult;
		qult= quoc;
		spenult=sult;
		tpenult=tult;
		sult=s;  tult=t;
		aaux=a; a=b; b=aaux%b;
		quoc=a\b;  print("a="a " b="b " s="s " qpenult="qpenult " qult="qult " quoc="quoc);
		resto=a%b
	);
	s=spenult-qpenult*sult;
	t=tpenult-qpenult*tult;
	spenult=sult;
	tpenult=tult;
	sult=s; tult=t;
	qpenult=qult;
	s=spenult-qpenult*sult;
	t=tpenult-qpenult*tult;
	if(flag==0,
		return([s,t,aorig*s+borig*t]),
		/*else*/ return([t,s,aorig*s+borig*t])
	)
	))
}