查看“︁带余除法”︁的源代码

[[分类:整除理论]]
[[分类:同余理论]]
{{InfoBox
|name=带余除法
|eng_name=Euclidean division
|aliases=欧几里得除法,欧氏除法
}}
{{InfoBox
|name=被除数
|eng_name=dividend
}}
{{InfoBox
|name=除数
|eng_name=divisor
}}
{{InfoBox
|name=商
|eng_name=quotient
|aliases=不完全商,incomplete quotient
}}
{{InfoBox
|name=余数
|eng_name=remainder
}}
'''带余除法'''或'''<ins>欧几里得</ins>除法'''('''Euclidean division''')指对两个[[整数]]，计算一个除不尽的“不完全”商和余数的算法。

[[自然数]]上也可以定义带余除法。

由于整数上取余数的范围有一定可调整范围，在说带余除法时，有时可能有不同的余数范围定义。

== 定义 ==

{{Operation
|name=带余除法
|operand=整数,非零整数
|result=整数
|domain=<math>\mathbb{Z}\times\mathbb{Z}^{*}</math>
|codomain=<math>\mathbb{Z}\times\mathbb{Z}</math>
}}
对整数 <math>a \in \mathbb{Z}</math> 和非零整数 <math>b \in \mathbb{Z}^*</math> ，若 <math>(\exists q \in \mathbb{Z}) (\exists r \in \mathbb{Z}) (a = b q + r \land 0\leq r < |b|)</math> ，则可证明 <math>q</math>、 <math>r</math> 唯一。此时 <math>a</math> 和 <math>b</math> 之间的这种运算，称为整数的'''带余除法'''或'''<ins>欧几里得</ins>除法'''('''Euclidean division''')。类比于[[除法]]， <math>a</math> 称为'''被除数'''('''dividend''')， <math>b</math> 称为'''除数'''('''divisor''')， <math>q</math> 称为'''不完全商'''('''incomplete quotient''')或仍称为'''商'''('''quotient''')， <math>r</math> 称为'''余数'''('''remainder''')。

在自然数上，则定义对应变为 <math>(\exists q \in \mathbb{Z}) (\exists r \in \mathbb{Z}) (a = bq+r \land 0\leq r < b)</math> 。

注： <math>r=0</math> 时就是[[整除]]。

=== 一般的带余除法 ===

一般地，对整数 <math>a \in \mathbb{Z}</math> 和非零整数 <math>b \in \mathbb{Z}^*</math> ，对任意的 <math>d\in\mathbb{Z}</math> ，必 <math>(\exists q \in \mathbb{Z}) (\exists r \in \mathbb{Z}) (a = b q + r \land d \leq r < |b| + d)</math> ，其中 <math>q</math>、 <math>r</math> 唯一。

{{InfoBox
|name=最小非负余数
|eng_name=least nonnegative remainder
|aliases=余数,remainder
}}
{{InfoBox
|name=最小正余数
|eng_name=least positive remainder
}}
{{InfoBox
|name=绝对最小余数
|eng_name=least absolute remainder
}}
将任意 <math>d</math> 时的 <math>r</math> 统称为'''余数'''('''remainder''')。特别地：
* 上述 <math>0 \leq r < |b|</math> 即 <math>d=0</math> 的情况，称为'''最小非负余数'''('''least nonnegative remainder''')，通常直接称为'''余数'''('''remainder''')；
* 若 <math>0 < r \leq |b|</math> 即 <math>d=1</math> ，称为'''最小正余数'''('''least positive remainder''')；
* 若 <math>-\tfrac{|b|}{2} \leq r < \tfrac{|b|}{2}</math> 或 <math>-\tfrac{|b|}{2} < r \leq \tfrac{|b|}{2}</math> ，称为'''绝对最小余数'''('''least absolute remainder''')。

注：利用[[取整函数]]，也可以通过有理数上的除法定义为 <math>q = \lfloor \frac{a}{b} \rfloor, r = a - b q </math> 。

== 性质 ==

有 <math>\operatorname{gcd}(a, b) = \operatorname{gcd}(b, r)</math> 。

由于余数取值有限，往往可以通过[[抽屉原理]]证明其中有相等的情况。
* 奇数 <math>a > 2</math> 有 <math>(\exists d < a)(a \mid 2^d - 1)</math> ，且满足这一条件的最小 <math>d_0</math> ，有 <math>(\forall h\in \mathbb{N})(a \mid 2^h - 1 \leftrightarrow d_0 \mid h)</math> 。


{{整除与质数}}