CHINESE REMAINDER THEOREM

<?php

/*
    CHINESE REMAINDER THEOREM
   théorème des restes chinois

  Résolution de l'équation
	a = x mod m
	b = x mod n

  Condition initiale: gcd(m,n) = 1

*/

function crt($a,$m,$b,$n){

	$res = ($a*$n*eea($n,$m)+$b*$m*eea($m,$n))%($m*$n);

	if ($res<0){
		while ($res<0)
			$res += $m*$n;
	}

	return $res;
}

// extended Euclid Algorithm pour le calcul de l'inverse

function eea($a,$b){

	$x = array($a,1,0);
	$y = array($b,0,1);

	while ($y[0] > 0){
		$rq = ed($x[0],$y[0]);
		$temp = $x;
		$x = $y;
		$y[0] = $temp[0] - $rq[1]*$y[0];
		$y[1] = $temp[1] - $rq[1]*$y[1];
		$y[2] = $temp[2] - $rq[1]*$y[2];
	}
	

	return $x[1];
}

// division euclidienne

function ed($x,$y){
	$rq[0] = $x % $y;
	$rq[1] = ($x-$rq[0])/$y;

	return $rq;
}

/*
	3 = x mod 5
	4 = x mod 7
 
        => x = 18
*/

echo $res = crt(3,5,4,7); // $res = 18
?>