接前面一小节 扩展欧几里德算法的推导。

前面提到了扩展欧几里德算法的证明和推导，对于这些定理，我们主要关心的是它的应用，是吧。定理用不着，价值就很难体现。扩展欧几里得算法的用途非常广，比如RSA加密算法中求私钥d。

这里我们要用程序来感受扩展欧几里德算法。还是前面小节的问题：已知等式 47x + 30y = 1; 求x,y的整数解。

设扩展欧几里德算法为gcdEx(a,b,x,y) 其中a,b为已知,x,y为所求。那么gcdEx(a,b,x,y)函数就有如下的计算过程：

解释一下这个过程：

1. 左边是利用朴素欧几里德算法相除得到一系列中间值，gcdEx(47,30,x,y)，a = 47，b = 30，所以 gcd(47, 30) = gcd(b, a%b) = gcd(30, 17)，直到b=0。

2. 当b=0时，可以得知x=1，y=0，当知道这两个值的时候，就可以开始根据扩展欧几里德算法倒推了。还记得那个定理吗？这里再说一次：

x1 = y2
y1 = x2 - (int)(a/b) * y2

3. 往上一步的x,y看作x1,y1，下面“旧”的x,y看作x2,y2，利用朴素欧几里德算法推导出的结论,x1=y2,y1=x2-(a/b)*y2。其中a,b就是当前gcdEx中的a,b.当这样递归回去到了第一个调用点时,所得到的x,y就是结果,即x=-7,y=11;

理解了吧？下面我们用程序验证一下。网上一大把其它语言的实现，就是没PHP的，这里就PHP实现一下吧：

<?php
$a = 47;
$b = 30;
$x;
$y;
$re = exgcd($a, $b, $x, $y);

function exgcd($a, $b, &$x, &$y)
{
	if($b == 0)
    {
        $x = 1;
        $y = 0;
        return $a;
    }
	echo 'exgcd() paras $b ='.$b.', $a%$b = '.$a%$b.', $x = '.$x.', $y = '.$y.'<br />';
	$r = exgcd($b, $a%$b, $x, $y);
	echo '--exgcd() paras $b ='.$b.', $a%$b = '.$a%$b.', $x = '.$x.', $y = '.$y.'<br />';
	$t = $x;
	$x = $y;
	$y = $t - floor($a/$b)*$y;
	return $r;
}

echo '$x = '.$x;
echo "<br />";
echo '$y = '.$y;
echo "<br />";

?>

程序运行结果：

exgcd() paras $b =30, $a%$b = 17, $x = , $y = 
exgcd() paras $b =17, $a%$b = 13, $x = , $y = 
exgcd() paras $b =13, $a%$b = 4, $x = , $y = 
exgcd() paras $b =4, $a%$b = 1, $x = , $y = 
exgcd() paras $b =1, $a%$b = 0, $x = , $y = 
--exgcd() paras $b =1, $a%$b = 0, $x = 1, $y = 0
--exgcd() paras $b =4, $a%$b = 1, $x = 0, $y = 1
--exgcd() paras $b =13, $a%$b = 4, $x = 1, $y = -3
--exgcd() paras $b =17, $a%$b = 13, $x = -3, $y = 4
--exgcd() paras $b =30, $a%$b = 17, $x = 4, $y = -7
$x = -7
$y = 11

扩展欧几里得算法就是不断地的将b放小，直至b等于0，最后反推求回x和y。前面不断的递归求解一定会有个时候 b=0，所以递归可以结束。结束之后再利用定理反推。

如果还不清楚，对着程序执行结果和图再仔细想想。