擴展歐幾里得算法是歐幾里得算法（又叫輾轉相除法）的擴展。除了計算a、b兩個整數的最大公約數，此算法還能找到整數x、y（其中一個很可能是負數），使它們滿足貝祖定理。
通常談到最大公因子時,我們都會提到一個非常基本的事實:給予二整數a與b,必存在有整數x與y使得ax+by=gcd(a,b)[1]。
有兩個數a,b，對它們進行輾轉相除法，可得它們的最大公約數——這是眾所周知的。然後，收集輾轉相除法中產生的式子，倒回去，可以得到ax+by=gcd(a,b)的整數解。
a x y
擴展歐幾里得算法是歐幾里得算法（又叫輾轉相除法）的擴展。除了計算a、b兩個整數的最大公約數，此算法還能找到整數x、y（其中一個很可能是負數），使它們滿足貝祖定理。
通常談到最大公因子時,我們都會提到一個非常基本的事實:給予二整數a與b,必存在有整數x與y使得ax+by=gcd(a,b)[1]。
有兩個數a,b，對它們進行輾轉相除法，可得它們的最大公約數——這是眾所周知的。然後，收集輾轉相除法中產生的式子，倒回去，可以得到ax+by=gcd(a,b)的整數解。