一、基本概念                                             

　　带余除法（division algorithm，除法定理）：a∈Z，d∈Z*，有唯一的整数 q 和 r，并且0≤r＜d₀，满足 a= d q+r。q 称为商，r  称为余数。通俗说法：整数除以正整数得到唯一的商（quotient）和余数（residue）。

　　 整除（divide exactly）：称 a 整除 b ，当整数 a 除以非零整数 b ，商为整数，且余数为零， 我们就说a能被b整除（或说b能整除a），记作 b|a。b 称为 a 的约数（因数，common divisor）。  

　　最大公约数（great common divisor）：两个不同时为零的整数a与b的公约数中最大的称为其最大公约数，记作d=gcd（a，b）。

　　丟翻图方程：整系数多项式方程的统称。

二、gcd欧几里得算法

　　GCD递归定理：对任意非负整数a和任意正整数b，gcd(a,b) = gcd(b,a mod b) 。证明见附录。

三、裴属定理

 　　裴属定理：对任意整数a，b，关于变量x，y的线性丟翻图方程 ax+by=m（裴属等式），有整数解当且仅当 m 是 d=gcd（a，b）的整数倍。证明见附录。

附录、

GCD递归定理的证明

　　gcd(a,b) = gcd(b,a mod b) ，先证gcd(a,b)|gcd(b,a mod b)，设d=gcd(a,b)，有d|a且d|b。令

　　r=（a mod b），则

　　r=a-qb，q为a/b向下取整。

　　（a mod b）是 a 与 b 的线性组合，所以 d|（a mod b）。

　　d|b，d|（a mod b），所以，d|gcd（b，a mod b）。

　　反过来证gcd(b,a mod b)|gcd(a,b)，方法相同，不再赘述，

　　gcd(a,b)=gcd(b,a mod b)。

裴属定理的证明

　　在 ax+by=m 中，

　　1. ab=0，不失一般性，令

　　　　b=0，则

　　　　ax=m。由

　　　  d=gcd（a，0）=a ，得

　　　　dx=m，

　　　　它有解当且仅当 m 是 d 的整数倍。

　　2. ab≠0，

　　　　设A是a，b的线性组合，即A={xa+yb| x，y∈Z}，

　　　　令d₀是A中最小正元素，即d₀=min{x| x∈A∩Z*}= x₀ a+ y₀ b，

　　　　下面将首先证明 d₀= gcd（a，b），进而构造裴属等式一组解，从而证明了命题的

　　充分性：

　　　　设 p 是 A 中任意一个正数，p=x₁a+ y₁b，

　　　　我们可以证明 d₀|p：

　　　　　　考虑p对d₀的带余除法，

　　　　　　p= d₀q+r，0≤r＜d₀，则

　　　　　　r  = p - d₀q 

　　　　　　　　=x₁a+y₁b-( x₀a+y₀b )q 

　　　　　　　　=（x₁-qx₀）a +（y₁-qy₀）b ∈A，

　　　　　　因为d₀是A中最小的正元素，所以r只能等于0，即d₀|p。

　　　　　　d₀ 是A中正整数的公约数。

　　　　　　假设d∈A且d是A中任意正整数的最大公约数，d|d₀，又d₀|d，所以d₀=d。特别地

　　　　　　d₀ =gcd（|a|，|b|）

　　　　　　=gcd（a，b）。

　　　设m=m₀d₀，d₀=gcd（a，b）= x₀ a+ y₀ b，则

　　　 m₀（ x₀ a+ y₀ b）=m，

　　　我们构造了裴属等式的一组可行解 x=m₀x₀，y=m₀y₀。

　　　实际上解可以有有无穷多组：x=（m₀x₀+kb/d₀）, y=（m₀y₀-ka/d₀）, k∈Z。

　必要性：如果xa+yb=m成立，那么m∈A，d₀||m|，d₀|m。