//erweiterter euklidscher Algorithmus
//erzeugt Array(g,s,t) mit g=ggt(a,b) und g=s·a+t·b
function erwGGT(a,b)
{
	var aa=1,bb=1,c;
	if(a<0){aa=-1;a=-a;}
	if(b<0){bb=-1;b=-b;}
	c=extGGT(a,b),g=ggT(a,b);
	return new Array(g,c[0]*aa,c[1]*bb);
}
function extGGT(a,b)
{
	if(b==0)return new Array(1,0);
	if((a%b)==0)return new Array(0,1);
	var c=extGGT(b,a%b),x=c[0],y=c[1];
	return new Array(y,x-y*Math.floor(a/b));
}
function ggT(a,b){while(b!=0){var r=a%b;a=b;b=r;}return a;}
function kgV(a,b){return a*b/ggT(a,b);}
function KGV(A){var i,k=A[0];for(i=1;i<A.length;i++)k=kgV(k,A[i]);return k;}

//chinesischer Restsatz
//erzeugt eine Lösung der simultanen Kongruenz x%mi=ri bzw. x ist kongr. ri mod mi 
//Eingabe: Array(Array(r1,r2,...,rn),Array(m1,m2,...,bn))
function chinRestsatz(r,m)
{
	var K=KGV(m),i,j,M=1,n=r.length,g,x=0,e,c,o,mm=new Array(n),rr=new Array();
	for(i=0;i<n;i++){M*=m[i];mm[i]=m[i];rr[i]=r[i];}
	if(M!=K)  // nicht alle paarweise teilerfremd
	{//alert(M+"  "+K);
		for(i=0;i<n-1;i++)
		{
			do{o=false;
			for(j=i+1;j<n;j++)
			{
				if((m[j]==1)&&(r[j]==0))continue;
				g=ggT(m[i],m[j]);
				if((r[i]%g)!=(r[j]%g))return null; //keine Lösung!
				if(g!=1)
				{
					while((r[i]%m[j])!=r[j])r[i]+=m[i];
					m[i]=kgV(m[i],m[j]);
					r[i]%=m[i];r[j]=0;m[j]=1;M/=g;o=true;
					//alert(r+"\n"+m+"\n"+g+"\n"+M);
				} // Zusammenfassen
			}
			}while(o);
		}if(M!=K)alert("Reduktion mißlungen");
	}
	for(i=0;i<n;i++)
	{
		if((r[i]==0)&&(m[i]==1))continue;
		c=erwGGT(m[i],M/m[i]);
		
		x+=c[2]*M/m[i]*r[i];        // chinesischer Restsatz
	}
	while(x<0)x+=M;
	x%=M;
	//Proben:
	for(i=0;i<n;i++){m[i]=mm[i];r[i]=rr[i];if((x%m[i])!=r[i])alert("Fehler: "+x+"%"+m[i]+" != "+r[i]);}
	return new Array(x%M,M);
}