带余除法

带余除法（也称为欧几里德除法）是数学中的一种基本算术计算方式。给定一个被除数a和一个除数b，带余除法给出一个整数q和一个介于一定范围的余数r，使得下面等式成立：

一般限定余数的范围在0与b之间，也有限定在-b/2与b/2之间。这样的限定都是为了使得满足等式的q有且仅有一个。这时候的q称为带余除法的商。带余除法一般表示为：

表达为：“a除以b等于q，余r”。最常见的带余除法是整数与整数的带余除法（被除数a和除数b都是整数），但实数与整数乃至实数与实数的带余除法也有应用。对一般的抽象代数系统，能够进行带余除法的都是具有欧几里德性质的系统。如果余数为零，则称b整除a。一般约定除数b不能为0.

带余除法的计算有长久的历史，有各种计算工具和计算方法。最常用的是长除法（竖式除法）。带余除法在数论中有不少用途，比如说辗转相除法的基本步骤就是带余除法。

以下是整数带余除法的例子：依照公历，一年中的四月份有30天。每星期有7天，从四月的第一天开始，可以数出有四个星期，此外还有2天。如果要数出5个星期，则还差了5天。带余除法表示，就是：

里面的30是被除数，7是除数，4是带余除法得到的商，2是带余除法得到的余数。日常生活中说：“四月份有四个多星期”，是带余除法的结果。

另一个例子是分配问题。假设有30个苹果要分给7个人，每人分的要一样多，那么可以使用带余除法：

这说明每人可以分到4个，还剩余2个。如果每人分5个，则是不够的。每人如果只分3个，则还剩余9个，可以继续分。带余除法说明了在人人分到的要一样多的条件下，每人可以分到的最多苹果数目。

最基本的带余除法是整数与整数的带余除法，这时商和余数都是整数。实数与整数的带余除法，或实数与实数的带余除法，余数是实数，但不一定是整数。比如说讨论使用正弦函数构造的数列${\displaystyle \{\sin <!--\; \; -->n\mid <!--\; \mid \; -->n\in <!--\; \in \; -->\mathbb{Z}\}}$使得${\displaystyle t_i=t_s}$的二进制数的前位，实际上就是它除以2的次幂后的商，而后位则是其余数。

原始的带余除法算法可以视为是重复使用减法的过程。设要计算a除以b，则在a里面不断地扣除b，直到不能继续扣除（满足余数范围）为止。以a、b都是正整数，余数范围为${\displaystyle \{0,1,\dots <!--\; \dots \; -->,b-<!--\; -\; -->1\}}$、两个多项式，其中不是零多项式。则存在由和唯一确定的多项式和，使得：

并且多项式是零多项式或者它的次数严格小于的次数，称为多项式带余除法的余元。:10

普通的整数或实数之间的带余除法可以良好定义。在更广泛的代数结构中，能够定义带余除法的代数结构被称为欧几里德整环。定义如下：

欧几里德整环中，使用一个额外的函数来比较两个元素之间的“大小”关系，从而能够定义带余除法。这个函数也称为范数。欧几里德整环必然是主理想整环因而也必然是唯一分解整环。:141:16-17