擴展歐幾里得算法是歐幾里得算法（也稱為輾轉相除法）的擴展，它不僅用於計算兩個整數a和b的最大公約數（GCD），還能找到整數x和y（其中一個可能是負數），使得ax+by=GCD(a,b)的等式成立。
在數學中，這基於裴蜀定理，該定理指出對於任何整數a和b，存在整數x和y，使得ax+by=GCD(a,b)，如果a和b的最大公約數為d，那麼一定存在整數x和y，使得ax+by=d。擴展歐幾里得算法通過在輾轉相除法的過程中記錄額外的信息，可以找到滿足這一條件的x和y值。
算法的實現通常涉及到在每一步遞歸中保存x和y的值，以便在計算過程中更新它們。這樣，當算法完成時，就可以得到所需的x和y值。