[code]
<?php

/**	Getting the greatest common divisor of $a and $b:
	$a = $b * $x + $q
	@param	integer, see above
	@param	integer, see above
	@param	reference to $x (Array), so those can be stored
	@return	return the $q, always 1 or 0
	@require	$a > $b, $a && $b to be integer, $x != null, $x == Array()
	@ensure	return = 0 or 1, &$x has all $x versions stored like this:
		$x[0] = $x from first line $a = $b * $x + $q
		$x[1] = $x from second line $a = $b * $x + $q
		
	@info		This function is recursive
*/
function getGCD($a,$b,&$x) {
	$new_b = $a % $b;
	$x[count($x)] = floor($a / $b);
	
	return ($new_b == 0 || $new_b == 1) ? $new_b : getGCD($b,$new_b,$x);
}

/**	Printing the lineair combination of $a and $b
	(0 || 1) = $y[0]*$a + $y[1]*$b;
	@param	integer, see above
	@param	integer, see above
	@return	null
	@require	$a > $b, $a && $b to be integer
	@ensure	print as above is correct and is the lineair combination of $a and $b
*/
function LineairCombination($a,$b) {
	$x = Array();
	$y = Array(1,0);
	
	$gcd = getGCD($a,$b,$x);
	
	for($i = count($x)-1; $i >= 0; $i--)
		if ($i % 2 == 0)
			$y[1] = $y[1] + $y[0] * -1 * $x[$i];
		else
			$y[0] = $y[0] + $y[1] * -1 * $x[$i];	
	
	printf("%d = %d x %d %d x %d",$gcd,$y[0],$a,$y[1],$b);
}

// just a test
(isset($_GET['a']) && isset($_GET['b'])) ? LineairCombination($_GET['a'],$_GET['b']) : LineairCombination(42,11);

?>
[/code]