/**
	 * Euclidean algorithm to find the greatest common divisor (gcd)
	 * @param a
	 * @param b
	 * @return
	 */
	public static int gcd(int a, int b){
		if(b == 0) return a;
		else return gcd(b, a % b);
	}
	
	/**
	 * Extended euclidean algorithm to find the greatest common divisor (gcd)
	 * @param a
	 * @param b
	 * @return
	 */
	public static int[] egcd(int a, int b) {
		int x = 0;
		int y = 1;
		int u = 1;
		int v = 0;
		
		while(b != 0)
		{
			int buffer = b;
			int q = a / b;
			b = a % b;
			a = buffer;
			buffer = x;
			x = u - q* x;
			u = buffer;
			buffer = y;
			y = v - q*y;
			v = buffer;
		} return new int[]{u,v,a};
	}