浅谈裴蜀定理
永远爱循环
·
·
算法·理论
裴蜀定理
1. 介绍
裴蜀定理取名于法国数学家\mathcal{Bézout's identity}，是一个关于最大公约数的数学定理：对于二元一次不定方程ax+by=c，有解的充分必要条件是gcd(a,b)|c
2. 证明:
(1). 充分性证明:
充分性：若gcd(a,b)|c，则 a x + b y = c有整数解
\text {设}d=gcd(a,b)\text{，由于整除的性质，}\forall x,y\in Z \text{，可得}d|(ax+by)
\text{设}s\text{为}ax+by\text{的最小正值，}q\text{为} \lfloor \frac{a}{s} \rfloor\text{，则}r=a \bmod s = a - qs =a-q(ax+by)=(1-qx)a+(-qy)b
\because a,b,c,y \in Z
\therefore r\in Z
\because r =a \bmod s
\therefore 0\le r <s
\because s \text{为}ax+by \text{的最小正值}
\therefore r=0
\therefore s|a\text{，同理} s|b
\therefore s\text{为}a,b\text{的公约数}
\therefore s\le d
\because d|(ax+by)
\therefore d|s
\therefore d\le s
\because s\le d
\therefore s=d
\because d|c
\therefore s|c
\therefore (ax+by)\frac{c}{s}= \frac{xc}{s}a+\frac{yc}{s}b= c
\because a,b,\frac{c}{s}\in Z
\therefore \frac{xc}{s},\frac{yc}{s} \in Z
\therefore \text{当}gcd(a,b)|c\text{，存在整数解}x,y\text{满足二元一次不定方程}ax+by=c
\text{证毕。}
(2). 必要性证明:
必要性：若 a x + b y = c有整数解，则gcd(a,b)|c
\text{设}d=gcd(a,b)
\therefore d|a,d|b
\because x,y \in Z
\therefore d|ax,d|by
\therefore d|(ax+by)
\therefore gcd(a,b)|c
\text{证毕。}
(3). 推论证明:
推论：对于二元一次不定方程ax+by=1，只有当整数a,b互质时，方程才有整数解
\text{假设}a,b\text{不互质}
\therefore \text{设}a=qd,b=pd,(d>1)
\therefore xqd+ypd=1
\therefore xq+yp= \frac{1}{d}
\because \text{方程}ax+by=1\text{有整数解}
\therefore \frac{1}{d} \in Z
\therefore d=1
\because d=1 \text{与} d>1\text{矛盾}
\therefore \text{当}a,b\text{互质时，不定方程}ax+by=1\text{才有整数解}
\text{证毕。}
3.推广：
对于不定方程x_1y_1+x_2y_2+x_3y_3+x_4y_4+......+x_ny_n=k，方程有整数解的充分必要条件为:gcd\{x_i\}|k。
证明略。
练习：裴蜀定理模板题
4. 总结:
裴蜀定理是一个关于最大公约数的数学定理，为扩展欧几里得算法的求解定下了基础，证明ax+by=gcd(a,b)一定有解