GCD

LCM

lcm(a,b)=a*b/gcd(a,b)

Euclid's Method

/**
 * greatest common demonimator
 * @param a
 * @param b
 * @return the gcd
 */
public int greatestCommonDenominator( int a, int b ){
	while( b != 0 ){
		int t = a%b;
		a = b;
		b = t;
	}
	return a;
}

Extended Euclid

Does some cool stuff like finds the simplified fraction which is closest in value to a given fraction...i have a proof somewhere...

/**
 * solves for (x,y) in Bezout's Identity: ax+by = gcd(a,b)
 * @param a
 * @param b
 * @return int[2] containing x,y
 */
public int[] bezoutIdentitySolve( int a, int b ){
	int x = 0, lx = 1, y = 1, ly = 0;
	while( b != 0 ){
		int t = a%b, q = a/b;
		a = b; b = t;
		t = x; x = lx-q*x; lx = t;
		t = y; y = ly-q*y; ly = t;
	}
	return new int[]{ lx, ly };
}