Jia Tse
www.egr.unlv.edu/~jjtse


long extended_gcd(long a, long b){
	//ax + yb = d , d = gcd of a,b
    long x = 0;    
	long lastx = 1;
    long y = 1;    
	long lasty = 0;
	
    while (b != 0){
        long temp = b;
        long quotient = a / b;
        b = a % b;
        a = temp;
        
        temp = x;
        x = lastx-quotient*x;
        lastx = temp;
        
        temp = y;
        y = lasty-quotient*y;
        lasty = temp;
	}
	pairs[0][0] = lastx;	
	pairs[0][1] = lasty;
	
	return a;	//gcd
}