最小公倍数・最大公約数を求めるにはユークリッドの互除法に基づくアルゴリズムを利用します。
なぜこの式で計算できるのかについては数学に詳しい人に聞いて下さい。

//最大公約数
function gcd($m, $n){
	if($n > $m) list($m, $n) = array($n, $m);
	
	while($n !== 0){
		$tmp_n = $n;
		$n = $m % $n;
		$m = $tmp_n;
	}
	return $m;
}

//最小公倍数
function lcm($m, $n){
	return $m * $n / gcd($m, $n);
}

参考

• 最大公約数（Wikipedia）
• 最小公倍数（Wikipedia）