如果一个整数同时是几个整数的因数,称这个整数为它们的“公因数”;公因数中最大的称为最大公因数。


定理:如果 ,则

证明:

根据 贝祖定理,对于任意两个整数 ,存在整数 使得它们的最大公约数 可表示为

假设 ,那么存在整数 使得

我们可以看到, 的线性组合,由于 能整除 也必然能整除 (或者 )。