裴蜀定理

· · 个人记录

裴蜀定理

在数论中，裴蜀定理是一个关于最大公约数（或最大公约式）的定理，裴蜀定理得名于法国数学家艾蒂安·裴蜀。

裴蜀定理说明了对任何整数a,b和它们的最大公约数d，关于未知数x和 y的线性丢番图方程（称为裴蜀等式）。

1. 简介

裴蜀定理（或贝祖定理，Bézout's identity）得名于法国数学家艾蒂安·裴蜀，说明了对任何整数a、b和它们的最大公约数d，关于未知数x和y的线性不定方程（称为裴蜀等式）：

若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。

它的一个重要推论是：a,b互质的充要条件是存在整数x,y使ax+by=1.

2. 证明

法1：

设 则。由整除的性质，，有d|(ax+by)。

设s为ax+by最小正值，首先有d|s,令，

可见r也为a,b的线性组合。由于s为a,b的线性组合的最小正值,，可知r=0,则s|a，同理s|b，则s|d，因此可得d=s，命题得证。

法2：

⑴若b=0，则(a,b)=a.这时定理显然成立。

⑵若a,b不等于0.

记d=(a, b),对ax+by=d，两边同时除以d，可得(a_1)x+(b_1)y=1，

其中(a_1,b_1)=1。

　　转证(a_1)x+(b_1)y=1。由带余除法：

　　① (a_1)=(q_1)(b_1)+(r_1), 其中0<r_1<b_1

　　② (b_1)=(q_2)(r_1)+(r_2), 其中0<r_2<r_1

　　③ (r_1)=(q_3)(r_2)+(r_3),其中0<r_3<r_2

　　.....

　　④ (r_n-4) = (q_n-2)(r_n-3) + (r_n-2)

　　⑤ (r_n-3) = (q_n-1)(r_n-2) + (r_n-1)

　　⑥ (r_n-2) = (q_n)(r_n-1) + (r_n)

　　⑦ (r_n-1) = (q_n+1)(r_n) + 1

　　故，由⑦和⑥推出(r_n-2)A_n-2 + (r_n-1)B_n-1 = 1

　　再结合⑤推出(r_n-3)A_n-3 + (r_n-2)B_n-2 = 1

　　再结合④推出(r_n-4)A_n-4 + (r_n-3)B_n-3 = 1 　　.....

　　再结合③推出(r_1)A_1 + (r_2)B_2 = 1

　　再结合②推出(b_1)A_0 + (r_1)B_0 = 1

　　再结合①推出(a_1)x + (b_1)y = 1

　　证毕QED。