整数整除
整数整除（integer divisibility）研究一个整数是否是另一个整数的整数倍。对整数 ，若存在整数 使 ，就记 ，读作“ 整除 ”，并称 是 的因数。整除关系把因数、倍数、最大公因数和整数方程连接起来，是素数与同余理论的基础。本文始终在整数范围内讨论，除特别说明外，最大公因数取正值。
“除得开”为什么必须指定整数范围
十二能够按每组三个分成四组，对应 ，所以 。十二除以五也能得到一个有理数，但商不是整数，所以 。如果允许任意有理数商，任何非零整数都能“除”任何整数，整除关系就失去了区分作用。定义中的整数系数正是实质条件。
负数不会改变因数的绝对大小：，因为商为负四； 也成立。每个整数都整除零，因为零是它的零倍。按本条采用的存在性定义， 成立，而零不整除任何非零整数。这不表示可以进行除以零的运算；整除是一个乘法关系，不是已经求出的除法值。
整除符号有方向。 表示右侧是左侧的倍数，不能因为中文“被整除”的不同说法而反过来读取。对正整数，若 则 ，但大小关系并不充分，例如五小于十二却不整除十二。整除描述的是乘法结构，而不是普通数轴顺序。
一个整数也可能同时有许多因数。寻找它们不等于寻找唯一分解中的素因子；全部因数与素因数是两种不同列表。以十二为例，正因数是 ，素因子只有二和三。最大公因数使用所有共同因数定义，之后才可以用素因数分解来计算。
线性组合保持共同因数
若 且 ，那么对任意整数 都有 。证明直接来自定义：写 ，便有 ，括号中的数仍是整数。这条性质是欧几里得算法与裴蜀等式的共同基础。
整除还满足传递性：若 、，把两个整数倍表达式相接，就得到 。对正整数，互相整除迫使相等；在全部整数中则只能推出绝对值相同，因为一个数与其相反数互相整除。讨论整除偏序时常限制正整数，正是为了排除这个符号歧义。
整除与加法配合较好，却不能随意拆开乘积。六整除 ，但既不整除二，也不整除三。只有当因数是素数，或附加适当互素条件时，才有更强的结论。“整除一个乘积就整除某个因子”不是一般整数的性质；这一边界解释了素数为何值得单独研究。
同样，两个数都整除某个整数，不能直接断言它们的积也整除该整数。四和六都整除十二，但二十四不整除十二。问题在于两者共享了素因子，直接相乘会重复要求这些因子。最小公倍数正是组织共同倍数而不重复计算的合适对象。
带余除法给出唯一的商和余数
对于任意整数 和正整数 ，存在唯一整数 满足 这称为带余除法定理。商可以是负数，但余数统一取非负且小于除数。这一区间条件使表示唯一；若不限制余数，把商增加一、余数减去除数，会得到无限多个同样正确的等式。
例如 ，所以按上述约定，商为负四、余数为三。写成 虽然等式成立，但余数为负，不符合本条规范。有些编程语言的取余符号对负数采用不同约定，数学公式与代码对应时需要明确检查，不能只看操作符名称相似。
存在性可用最小非负剩余量证明。在所有形如 的非负整数中选最小者 ；这样的数总存在，因为把整数 取得足够负即可。如果 ，则 仍非负、仍有同样形式而且更小，矛盾，所以 。这里使用了非负整数的良序性。
唯一性也要证明。若 ，相减得到 。右侧绝对值小于 ，而非零的 倍数绝对值至少为 ，因此两侧只能为零，商与余数分别相同。定理不仅告诉算法可以算出答案，也说明不同正确算法应当得到同一规范结果。
欧几里得算法为什么不会改变答案
不全为零的整数 的最大公因数记为 ，定义为最大的正公因数。负号不影响结果，可先取绝对值。对非零 ，；本文不为 规定值，以免把不同扩充约定混入入门定义。
若 ，则 与 拥有完全相同的公因数：共同整除前两者，就整除差 ；共同整除后两者，也整除和 。所以把大数换成余数不改变最大公因数。算法的核心是不变量，而不是“不断除”这个表面动作。
计算二百五十二与一百九十八： 非零余数逐步变小，最后一个非零余数为十八，因此最大公因数是十八。验证原数分别为十八的十四倍与十一倍，可确认它确实是公因数；它是最大的理由来自每一步保持完整公因数集合，而不只是最后一次除法。
算法一定停止，因为正余数严格下降，不能形成无限下降的正整数序列。这个终止理由与结果正确性是两件事：严格下降保证会算完，不变量保证算完的是所求对象。可靠的算法说明应同时交代二者。相对于逐个枚举所有可能因数，余数过程通常大幅缩小数字规模，尤其适合大整数计算。
回代得到裴蜀等式及其意义
把上面的余数关系倒着代入，可得 这不仅给出最大公因数，还把它表示成原来两数的整数线性组合。一般地，不全为零的整数 总存在整数 ，使 这称为裴蜀等式。扩展欧几里得算法就是在求余过程中同步追踪这些系数，或者计算结束后回代恢复它们。
等式中的系数未必正，也通常不唯一。上例的负五完全正常，因为整数线性组合允许相减。若问题要求非负整数解，就附加了新的限制，裴蜀等式本身不保证满足。它说明整除约束下哪些整数可以由加减组合得到，而不是任何实际配比都能采用这种组合。
还可以反向刻画最大公因数：原两数的所有取正值的整数线性组合中，最小者就是最大公因数。取最小正组合 ，分别用它去除原两数；余数仍是整数线性组合，若为正就比 更小，矛盾，所以余数为零。于是 是公因数；任何公因数又整除每个线性组合，所以也整除 。这一论证把“最大公因数”与“最小正组合”两种看似相反的描述联系起来。
若最大公因数为一，两数称为互素。互素不是说两者都为素数，例如八和九都是合数，却互素；也不是说两个数相差一才可能互素。相邻整数确实总互素，因为共同因数整除它们的差一，但这只是一个充分条件。
整数方程的有解条件与全部解
线性整数方程 有整数解，当且仅当 整除 。必要性来自共同因数整除每个线性组合；充分性来自裴蜀等式：把表示 的系数一起乘以 ，就得到目标右端。
例如 有解，因为十八整除三十六。将上述裴蜀系数乘二，得到一个特解 。全部整数解为 代回时两个含参数项相消，常数部分为 。要证明没有漏解，将任意解与特解相减，得到 ；十四与十一互素，迫使 是十一的倍数，随后得到另一式。
若额外要求两个未知量非负，则第一式要求整数参数至少为零，第二式要求参数至多为负一，没有交集。因此方程有整数解，却没有非负整数解。这个完整例子说明“存在代数解”与“符合情境限制的解”并不相同。若把右端改为三十五，则连整数解也没有，因为十八不整除三十五。
一般的全部解公式在 都非零时写为 、。如果某个系数为零，应直接按剩余单个整除条件处理，避免机械套用推导中隐含的非零假设。参数必须是整数，不能把实数方程解直线上的所有点都当成整数解。
互素条件怎样恢复乘积消去
若 且 ，则 。由裴蜀等式取 ，乘以 得 ；左边两项都被 整除，所以右边也是。这个证明精确指出互素条件的用途：它让一被写成适当的整数线性组合。
素数整除乘积必整除某个因子的结论，可以从这里推出：若素数不整除第一个因子，它与该因子就互素，因而整除第二个。素数条目将用这一点证明唯一分解；同余条目则用它解释什么时候可以约去一个乘数。三个主题共享同一个整除机制，而不是三套互不相关的技巧。
正整数 的最小公倍数记为 ，满足 把两数分别写成 ，其中 互素，则最小公倍数是 。任何共同倍数除以 后，同时含有互素的两个因子，因而必被它们的积整除，这证明了最小性。对十二与十八，最大公因数为六，最小公倍数为三十六，乘积关系为 。
约分、分割与周期各自使用什么量
分数二百五十二除以一百九十八的分子分母共同除以十八，得到十四除以十一。约分保持商不变，但为什么已经最简，还要说明新分子分母互素：若它们另有大于一的共同因数，乘回十八就会得到比原最大公因数更大的公因数，矛盾。因此最大公因数不仅给出一次可行约分，也保证已经完成全部约分。
同一组数字可以表示长二百五十二厘米、宽一百九十八厘米的矩形。若只允许用边与矩形边平行、边长为整数厘米的相同正方形无缝铺满，正方形边长必须同时整除两边。最大可行边长因此为十八厘米，沿两边分别放十四块和十一块，共需一百五十四块。这里的方向与整边铺排假设不可省略，不能把结论不加条件地推广到任意旋转或不同大小的拼铺。
周期重合则使用最小公倍数。两个理想事件从同一时刻开始，分别每十二分钟和十八分钟发生一次，下一次共同发生要等到三十六分钟，因为它是两个周期的最小正公共倍数。如果初始时刻不同，单独计算周期的最小公倍数不够，还需要检查相位是否相容；那属于同余方程的问题。
这些解释也反映了验证方式的区别。最大公因数要验证“同时是因数”并排除更大公因数，最小公倍数要验证“同时是倍数”并排除更小正公共倍数。只代入得到一次成功配对，只能证明可行，不能证明最大或最小；最优性需要对应的整除论证。
算法记载与现代语言
《几何原本》第七卷命题二记载了寻找两个数最大公度量的过程，采用反复相减的表达。现代带余除法把连续减去若干次合并成一步，构成今天常用的欧几里得算法。原文及解释可见 David Joyce 编注的《几何原本》VII.2。文献中的古代“数”与今天包括负数、零的整数范围并不完全相同。
因此“欧几里得算法”是明确的历史归名，却不等于能够据此断言欧几里得首次发现了所有整除思想。本条使用的负数约定、函数式记号和整数线性组合语言，是现代组织方式。历史说明应区分可见的文献记载、后来的命名与现代一般化，不把它们压缩成一个未经证实的发明日期。
English overview
An integer a divides an integer b when b is an integer multiple of a. Divisibility is a relation defined through multiplication, so statements involving zero must not be confused with division by zero. Common divisors are preserved under integer linear combinations.
The division theorem gives a unique quotient and a remainder between zero and a positive divisor. The Euclidean algorithm repeatedly replaces a pair by the divisor and remainder. This preserves all common divisors, while decreasing positive remainders guarantee termination. Back substitution expresses the greatest common divisor as an integer linear combination, known as Bézout's identity.
A linear equation ax + by = c has integer solutions exactly when gcd(a,b) divides c. A worked example derives every integer solution and then shows why none satisfies an added nonnegativity requirement. Coprimality also explains valid cancellation in products and supports the theory of primes and congruences. The least common multiple records shared multiples without counting common factors twice. Historical discussion distinguishes Euclid's recorded subtraction procedure from its modern remainder formulation and from later integer notation.
编者评注（AI 辅助）
本条把欧几里得算法的“保持公因数不变”与“余数下降所以停止”分开证明，再用同一个算例完成回代和整数方程求解，避免算法步骤只是口令。零、负数与非负解限制均单独说明，因为它们最容易被默认约定遮蔽。内容由 AI 辅助整理；编者的取舍是先解释整数系数为什么重要，再连接素数和同余，不能据计算方便而扩大未说明的数域。
参考资料与后续阅读
- Thomas W. Judson，Abstract Algebra: Theory and Applications，The Division Algorithm：带余除法、最大公因数和整数论基础。
- Euclid，Elements，VII.2，David Joyce 编注：最大公度量算法原文与解释。
- 后续可读素数、同余、群；与逻辑中的存在性证明和反证法相联系。