貝祖等式，依艾蒂·貝祖命名，是線性丟番圖方程。
它說明若有整數a、b和其最大公因子d，必存在整數x、y使得：
ax + by = d
x、y稱爲貝祖數，可用擴展版輾轉相除法求得，但結果不是唯一的。
例如12和42的最大公因子是6，便可以寫(-3)×12 + 1×42 = 6及4×12 + (-1)×42 = 6。
d其實就是最小可以寫成ax + by形式的正整數。
輾轉相除法是用來求最大公約數的．我們用代數的形式來表達(實質上，算術形式也是可以完全講得清楚的)．給出兩個正整數a和b，用b除a得商a0，餘數r，寫成式子
a=a0b+r，0≤r＜b． (1)
這是最基本的式子，輾轉相除法的靈魂．如果r等於0，那麼b可以除盡a，而a、b的最大公約數就是b．
如果r≠0，再用r除b，得商a1，餘數r1，即
b=a1r+r1，0≤r1＜r．
(2)如果r1=0，那麼r除盡b，由(1)也除盡a，所以r是a、b的公約數．反之，任何一齔、b的數，由(1)，也除盡r，因此r是a、b的最大公約數．
如果r1≠0，則用r1除r得商a2，餘數r2，即
r=a2r1+r2，0≤r2＜r1． (3)
如果r2=0，那麼由(2)可知r1是b、r的公約數，由(1)，r1也是a、b的公約數．反之，如果一數除得盡a、b，那末由(1)，它一定也除得盡b、r，由(2)，它一定除得盡r、r1，所以r1是a、b的最大公約數．
如果r2≠0，再用r2除r1，如法進行．由於b＞r＞r1＞r2＞…逐步小下來，而又都是正整數，因此經過有限步驟後一定可以找到a、b的最大公約數d(它可能是1)．這就是有名的輾轉相除法，在外國稱爲歐幾里得算法．這個方法不但給出了求最大公約數的方法，而且幫助我們找出x、y，使
ax+by=d．
品位站
