擴展歐幾裏德算法是用來在已知a, b求解壹組x，y，使它們滿足貝祖等式： ax+by = gcd(a, b) =d（解壹定存在，根據數論中的相關定理）。擴展歐幾裏德常用在求解模線性方程及方程組中。
下面是壹個使用C語言的實現：
intexGcd(int?a,int?b,int?&x,int?&y){
if(b==0)//當b==0時，得到解
{
x=1;y=0;
return?a;
}
intr=exGcd(b,a%b,x,y);//遞歸調用自身，求解
intt=x;x=y;y=t-a/b*y;
return?r;
}