裴蜀定理，也被稱為貝祖定理，是數論中的一個重要定理。它表明對於任意整數a和b，以及它們的最大公約數d，存在整數x和y，使得ax+by=d。這個定理可以推廣到任意整數a和b，以及它們的最大公約數d，ax+by一定是d的倍數。特別地，當a和b互質（即它們的最大公約數為1）時，一定存在整數x和y，使ax+by=1成立。
裴蜀定理的證明可以通過反證法來實現。假設ax+by=c有一組正整數解c，其中c不是a,b的最大公約數d的倍數。那麼存在另一個正整數d'=gcd(c,d)，d'除以d不能整除。定義e=c/d'並將c表示為d'e，則可得: d' = ax'+by' d = ax'' + by'' 那麼,我們可以推導出: e=cx''/dd' + cy''/dd'=(ae+b)/d'x'' + (be+a)/d'y'' 根據這個等式可以看出,ae和be都是d'的倍數,其和也是d'的倍數。但是,因為d'和d沒有公因數,所以ae和be只有d的倍數(ax和by也是一樣的)。因此,我們得出矛盾:e本應是d的倍數,但它既然可以表示為不同的單部分之和,則必須是d和d'的公共倍數。這與我們一開始的假設不符,因此ax+by=d在所有正整數x和y中具有最小的正整數解，即為裴蜀定理。
擴展歐幾里得算法是求解裴蜀定理的一種方法。該算法理論上只能求解a、b互質的情況，但是在實際操作中，我們也可以通過在計算過程中保證x和y的絕對值之和最小來避免出現問題。