带余除法, 也称为欧几里德除法, 英語, euclidean, division, 是数学中的一种基本算术计算方式, 给定一个被除数a, displaystyle, 和一个除数b, displaystyle, 给出一个整数q, displaystyle, 和一个介于一定范围的余数r, displaystyle, 使得下面等式成立, 17个点五个五个排列, 可以排3列, 剩余两个, 用来说, 17除以5等于3, 余数是2, displaystyle, 一般所称, 欧几里德除法, 限定余数的范围在0与b, displa. 带余除法 也称为欧几里德除法 英語 Euclidean division 是数学中的一种基本算术计算方式 给定一个被除数a displaystyle a 和一个除数b displaystyle b 带余除法给出一个整数q displaystyle q 和一个介于一定范围的余数r displaystyle r 使得下面等式成立 17个点五个五个排列 可以排3列 剩余两个 用带余除法来说 17除以5等于3 余数是2 a b q r displaystyle a bq r 一般所称 欧几里德除法 限定余数的范围在0与b displaystyle b 之间 还有叫做 居中除法 的变体 限定余数在 b 2 displaystyle frac b 2 与b 2 displaystyle frac b 2 之间 这种余数称为 居中余数 这样的限定都是为了使得满足等式的q displaystyle q 有且仅有一个 这时候的q displaystyle q 称为带余除法的商 带余除法一般表示为 a b q r displaystyle a div b q dots r 表达为 a displaystyle a 除以b displaystyle b 等于q displaystyle q 余r displaystyle r 最常见的带余除法是整数与整数的带余除法 被除数a 和除数b 都是整数 但实数与整数乃至实数与实数的带余除法也有应用 对一般的抽象代数系统 能够进行带余除法的都是具有欧几里德性质的系统 如果余数为零 则称b displaystyle b 整除a displaystyle a 一般约定除数b displaystyle b 不能为0 带余除法的计算有长久的历史 有各种计算工具和计算方法 最常用的是长除法 竖式除法 带余除法在数论中有不少用途 比如说辗转相除法的基本步骤就是带余除法 目录 1 例子 1 1 不同的带余除法 2 基本定理 2 1 证明 3 计算 3 1 算法 3 1 1 原始算法 3 1 2 使用二分法 4 推广 4 1 多项式的带余除法 4 2 欧几里德整环 5 参见 6 参考来源例子 编辑 source source source source source 如何将30个苹果尽可能地分给7个人 并且使每人一样多 以下是整数带余除法的例子 依照公历 一年中的四月份有30天 每星期有7天 从四月的第一天开始 可以数出有四个星期 此外还有2天 如果要数出5个星期 则还差了5天 带余除法表示 就是 30 7 4 2 displaystyle 30 div 7 4 dots 2 nbsp 里面的30是被除数 7是除数 4是带余除法得到的商 2是带余除法得到的余数 日常生活中说 四月份有四个多星期 是带余除法的结果 另一个例子是分配问题 假设有30个苹果要分给7个人 每人分的要一样多 那么可以使用带余除法 30 7 4 2 displaystyle 30 div 7 4 dots 2 nbsp 这说明每人可以分到4个 还剩余2个 如果每人分5个 则是不够的 每人如果只分3个 则还剩余9个 可以继续分 带余除法说明了在人人分到的要一样多的条件下 每人可以分到的最多苹果数目 不同的带余除法 编辑 最基本的带余除法是整数与整数的带余除法 这时商和余数都是整数 实数与整数的带余除法 或实数与实数的带余除法 余数是实数 但不一定是整数 比如说讨论使用正弦函数构造的数列 sin n n Z displaystyle sin n mid n in mathbb Z nbsp 时 就需要使用除数为2 p displaystyle 2 pi nbsp 的带余除法 来讨论每一项具体的取值 基本定理 编辑带余除法限定了余数的范围 使得商唯一存在 整数与整数的带余除法中 余数的范围通常是 0 1 b 1 displaystyle 0 1 dots b 1 nbsp 这样的b displaystyle b nbsp 个元素的集合 被除数为实数的带余除法中 常常会使用介于0和除数 b displaystyle left vert b right vert nbsp 之间 大于等于0 严格小于 b displaystyle left vert b right vert nbsp 的半开闭区间作为余数的范围 另一种常见的范围是大于等于 b 2 displaystyle frac left vert b right vert 2 nbsp 严格小于 b 2 displaystyle frac left vert b right vert 2 nbsp 带余除法的基本定理说明 整数与整数的带余除法中 只要余数的范围是 b displaystyle left vert b right vert nbsp 个整数 并且任何两个数之差都不是b 的倍数 那么带余除法的商唯一存在 被除数为实数的除法中 只要余数的范围是一个如同长度为 b displaystyle left vert b right vert nbsp 的半开半闭区间 那么带余除法的商唯一存在 1 25最常见的带余除法中用到的是整数除以整数的一个版本 对任何给定的整数a displaystyle a nbsp 和非零整数b displaystyle b nbsp 都存在唯一的整数q displaystyle q nbsp 以及属于集合 0 1 b 1 displaystyle 0 1 dots b 1 nbsp 的整数r displaystyle r nbsp 使得 a b q r displaystyle a bq r nbsp 证明 编辑 定理的证明是将整数集合或实数轴分割成长度为 b 的区间段 證明由兩部分組成 首先證明q displaystyle q nbsp 和r displaystyle r nbsp 的存在性 其次證明q displaystyle q nbsp 和r displaystyle r nbsp 的唯一性 整数除以整数的情况 假设余数的范围是R r 1 r 2 r b displaystyle R r 1 r 2 dots r b nbsp 其中任两个数的差都不是b displaystyle b nbsp 的倍数 那么可以将全体整数分割成以下集合的不交并集 Z k Z r 1 k b r 2 k b r b k b k Z R k displaystyle mathbb Z sqcup k in mathbb Z r 1 kb r 2 kb dots r b kb sqcup k in mathbb Z R k nbsp 其中的 displaystyle sqcup nbsp 指两两不相交的并集 这样的划分方式下 不会有两个集合有交集 反设有两个集合R k displaystyle R k nbsp 和R l displaystyle R l nbsp 有交集 r i k b r j l b displaystyle r i kb r j lb nbsp 那么 r i r j l k b displaystyle r i r j l k b nbsp 这说明有两个元素的差是b displaystyle b nbsp 的倍数 矛盾 另一方面 任何一个整数都必然属于某个R k displaystyle R k nbsp 设有整数s displaystyle s nbsp 那么存在整数q s displaystyle q s nbsp 使得q s b s lt q s b b displaystyle q s b leq s lt q s b b nbsp 也就是说存在 0 1 b 1 displaystyle 0 1 dots b 1 nbsp 里的一个数t s displaystyle t s nbsp 使得s q s b t s displaystyle s q s b t s nbsp 同样地 对r 1 r 2 r b displaystyle r 1 r 2 dots r b nbsp 里的每一个数r i displaystyle r i nbsp 也各自存在 0 1 b 1 displaystyle 0 1 dots b 1 nbsp 的一个数t i displaystyle t i nbsp 和一个整数q i displaystyle q i nbsp 使得r i q i b t i displaystyle r i q i b t i nbsp 由于有b 1 displaystyle b 1 nbsp 个属于集合 0 1 b 1 displaystyle 0 1 dots b 1 nbsp 的整数 根据抽屉原理 必然有两个整数相同 而由前所证 不可能有t i t j displaystyle t i t j nbsp 的情况 所以只能是存在某个i displaystyle i nbsp 使得t i t s displaystyle t i t s nbsp 所以 s q s b t s q s b t i q s b r i q i b displaystyle s q s b t s q s b t i q s b r i q i b nbsp s r i q s q i b R q s q i displaystyle s r i q s q i b in R q s q i nbsp 因此 任何一个整数都唯一地属于某个R k displaystyle R k nbsp 而对应的这个整数k displaystyle k nbsp 就是带余除法唯一确定的商 2 18 22 被除数是实数的情况 假设余数的范围是 x x b displaystyle x x b nbsp 那么将实数轴R displaystyle mathbb R nbsp 分割为 R k Z x k b x k 1 b displaystyle mathbb R sqcup k in mathbb Z x kb x k 1 b nbsp 这个分割方式构成了实数的一个分划 每个实数都唯一地属于其中的某一个区间段 所以被除数a displaystyle a nbsp 也必然唯一地属于其中的某一个区间段 假设a displaystyle a nbsp 属于区间段 I q x q 0 b x q 0 1 b displaystyle I q x q 0 b x q 0 1 b nbsp 则说明 x a q 0 b lt x b displaystyle x leq a q 0 b lt x b nbsp 所以带余除法的商唯一确定 就是q 0 displaystyle q 0 nbsp 计算 编辑计算带余除法和计算除法的手段基本相同 手工计算时常常使用长除法 与除法不同之处是到个位即停止 剩余的即是余数 计算机运算中使用的带余除法一般耗费的时间比相同位数的乘法更久 所以编程时为了减少机器运算量 常常会尽力避免除法运算 一般的编程语言和数学 统计软件中 带余除法运算符 指令 和取模运算符 指令 可能是分开的 也可能是合并的 如在进行带余除法时尽管默认返回的是商 但实际上余数也储存在运算结果中 除数是2的幂次的时候 可以使用右移的位移运算代替带余除法 这是因为计算机储存数据使用的是二进制 取一个长度为n displaystyle n nbsp 的二进制数的前k displaystyle k nbsp 位 实际上就是它除以2的n k displaystyle n k nbsp 次幂後的商 而後n k displaystyle n k nbsp 位则是其余数 算法 编辑 原始算法 编辑 原始的带余除法算法可以视为是重复使用减法的过程 设要计算a displaystyle a nbsp 除以b displaystyle b nbsp 则在a displaystyle a nbsp 里面不断地扣除b displaystyle b nbsp 直到不能继续扣除 满足余数范围 为止 以a displaystyle a nbsp b displaystyle b nbsp 都是正整数 余数范围为 0 1 b 1 displaystyle 0 1 dots b 1 nbsp 的除法为例 伪代码如下 function Division a b q 0 r a while r gt b do r r b q q 1 end while return q r 这样的算法复杂度是a b displaystyle frac a b nbsp 的级别 3 使用二分法 编辑 更为优化的算法是使用二进制以及二分法的结合 算法大致分为两个部分 首先用不断倍增的方式找出一个a displaystyle a nbsp 所属的区间 然后用二分法不断收窄区间 直到将a displaystyle a nbsp 限制在一个长度为b displaystyle b nbsp 的区间为止 举例来说 要计算237除以9 可以首先列出如下表格 0 1 2 3 4 51 2 4 8 16 329 18 36 72 144 288也就是从小到大逐个列出2的幂次与9的乘积 直到超过237为止 其中 24 9 144 是小于等于237的最大数 之後的288就比237更大了 接下来反过来利用2的幂次与9的乘积来计算237除以9 过程如下 设q 16 displaystyle q 16 nbsp p 32 displaystyle p 32 nbsp 237介于144与288之间 而144和288的平均数是216 比237小 令q 16 32 2 24 displaystyle q frac 16 32 2 24 nbsp p 32 displaystyle p 32 nbsp 216和288的平均数是252 比237大 令q 24 displaystyle q 24 nbsp p 24 32 2 28 displaystyle p frac 24 32 2 28 nbsp 216和252的平均数是234 比237小 令q 24 28 2 26 displaystyle q frac 24 28 2 26 nbsp p 28 displaystyle p 28 nbsp 234和252的平均数是243 比237大 令q 26 displaystyle q 26 nbsp p 26 28 2 27 displaystyle p frac 26 28 2 27 nbsp 最后得到q displaystyle q nbsp 的值为26 这就是237除以9的商 237减去234剩余的3就是余数 伪代码如下 function QuickDivision a b counter 0 power 1 mid 0 appr 0 zh hans 找到2的幂次与除数b的乘积中比被除数a大的最小数对应的幂次 zh hant 找到2的冪次與除數b的乘積中比被除數a大的最小數對應的冪次 while power b lt a do counter counter 1 power power 2 end while p power q power 2 p和q乘以b以後分别是a的上界和下界 以下用二分法不断收窄上下界 直到上下界之差等于b 即p与q之差等于1 为止 for k from 1 to counter 1 do 计算上下界的平均值 comp p q 2 mid comp b 如果平均值小于等于a 则调高下界 同时记录平均值 否则调低上界 if mid lt a then appr mid q comp else p comp end if end for 结束后q乘以b的积就是小于等于a的b的倍数中最大的 这说明q就是商 appr是最後一个小于等于a的平均值 所以它和a的差就是余数 r a appr return q r 以上的算法的复杂度在log 2 a b displaystyle log 2 left frac a b right nbsp 级别 当a b displaystyle frac a b nbsp 较大时 远远比原始的算法快捷 3 推广 编辑多项式的带余除法 编辑 更多信息 多項式長除法 以域K displaystyle mathbb K nbsp 为系数的多项式构成的多项式整环K X displaystyle mathbb K X nbsp 中也可以定义带余除法 设有A displaystyle A nbsp B displaystyle B nbsp 两个多项式 其中B displaystyle B nbsp 不是零多项式 则存在由A displaystyle A nbsp 和B displaystyle B nbsp 唯一确定的多项式Q displaystyle Q nbsp 和R displaystyle R nbsp 使得 A B Q R displaystyle A BQ R nbsp 并且多项式R displaystyle R nbsp 是零多项式或者它的次数严格小于B displaystyle B nbsp 的次数 称为多项式带余除法的余元 4 10 欧几里德整环 编辑 主条目 歐幾里得整環 普通的整数或实数之间的带余除法可以良好定义 在更广泛的代数结构中 能够定义带余除法的代数结构被称为欧几里德整环 定义如下 设有整环D displaystyle D nbsp 和从D displaystyle D nbsp 到自然数的映射v D 0 D N 0 displaystyle v D setminus 0 D to mathbb N cup 0 nbsp 使得 若a b D displaystyle a b in D nbsp 而b 0 D displaystyle b neq 0 D nbsp 则存在q r D displaystyle q r in D nbsp 使得a b q r displaystyle a bq r nbsp 而且要么有r 0 D displaystyle r 0 D nbsp 或者 v r lt v b displaystyle v r lt v b nbsp dd 则称D displaystyle D nbsp 为欧几里德整环 1 141欧几里德整环中 使用一个额外的函数来比较两个元素之间的 大小 关系 从而能够定义带余除法 这个函数也称为范数 欧几里德整环必然是主理想整环因而也必然是唯一分解整环 1 141 4 16 17参见 编辑除法 同余参考来源 编辑 1 0 1 1 1 2 胡冠章 王殿军 应用近世代数 北京 清华大学出版社 2006 ISBN 9787302125662 David M Burton Elementary Number Theory McGraw Hill 2010 ISBN 9780073383149 英语 3 0 3 1 Christian Blanchet Division euclidienne et consequences PDF Groupes et arithmetique chapitre 1 Universite Paris 7 2013 11 18 原始内容存档 PDF 于2011 02 06 法语 4 0 4 1 张贤科 许甫华 高等代数学 北京 清华大学出版社 2004 ISBN 9787302082279 取自 https zh wikipedia org w index php title 带余除法 amp oldid 79537374, 维基百科,wiki,书籍,书籍,图书馆,