裴蜀定理【Besout's identity】

2021-01-16 本文已影响0人摇摆苏丹

描述

给定两个整数 $a,b$ ，假设它们的最大公约数为 $p$ ,也就是 $gcd(a,b)=p$ ，那么关于数对 $(x,y)$ 的方程 $ax+by=n$ 有整数解，当且仅当 $n$ 是 $p$ 的倍数。

证明

设集合 $A = \{ax+by\mid a,b,x,y\in \mathbb{Z}\}$ ，显然 $2a-3b,-5a-6b,0a+b=b,a+0b=a,0a+0b=0$ 等整数都是集合 $A$ 中的元素。
设集合 $B = \{n \mid n=zp,p=gcd(a,b),z \in \mathbb{Z}\}$ ，如果能证明 $A=B$ ，那么裴蜀定理成立。
首先总能找到 $A$ 中的最小正整数，设其为 $sa+tb$ ，对于 $A$ 中任意的元素 $s'a+t'b$ ，都有 $s'a+t'b=k(sa+tb)$ 。否则，必有 $s'a+t'b=k(sa+tb)+r$ ，显然 $r<sa+tb$ 。但是 $s'a+t'b=k(sa+tb)+r \iff r=(s'-ks)a+(t'-kt)b$ ，可得 $r \in A$ ，且 $r$ 是比 $A$ 中最小正整数 $sa+tb$ 更小的正整数，与假设矛盾，故 $A$ 中所有元素都是 $sa+tb$ 的倍数。
设 $m$ 是数对 $(a,b)$ 的公约数，那么 $m|a,m|b$ ，可得 $m|(sa+tb)$ ，显然 $m \leq sa+tb$ ，则 $sa+tb$ 就是 $m$ 的最大值。即 $sa+tb$ 就是数对 $(a,b)$ 的最大公约数。
令 $sa+tb=p$ ，则 $B=A$ ，裴蜀定理得证。