从带余数除法谈起的知识点(从带余数除法谈起的知识)

来源|《数学通报》，1985年第10期

[编者按]本文原是北京师范大学严士健老师在北京市海淀区教师进修学校组织的报告会上所作的演讲的讲演稿。本文从带余数除法出发，推广到多项式环，欧氏环等讨论了类似问题，最后回过头来讨论了小学整数除法的理论根据。这对教师进修和教学都有参考价值。

余数除法是一个比较古老的初等数论公式，但是非常有用。它不仅是整数可约性理论的基础，而且可以用来进一步求解多元线性不定方程、同余式、连分数等许多其他数论问题。然而，这并不旨在以这种方式进行。如果有兴趣，可以系统学习初等数论的书籍。

在本文中，我们首先介绍除法的余数，然后直接推导定理2，这是可约性基本理论的起点。那么我们就从这些基本的东西出发，看看现代的一些内容和它有什么相似之处。比如多项式环、欧几里德环等等。最后看看小学算术中整数除法的理论基础也很有趣。

1带余数除法

【定理1】（除余数）：如果是两个整数，其中>，则有两个整数and，这样，为真，且和唯一。注意这个性质告诉我们，当我们用b测量a时，有可能完全测量a，并且不会有余数，即r=0——。也可能是不完全的，余数会在0之间b，即0rb——不可整除。证明：(i)存在是一个整数序列.-3b,-2b,-b,0,b,2b,3b,那么a一定在上述序列的两项之间，即，有一个整数q，令qba(q+1)b成立，令a-qb=r，则a=bq+r，且0rb。(ii)唯一性如果存在另一对整数且使得thenthenif,then,then矛盾，因此。因此它是独一无二的。示例：将1270除以某个数，得到商74。求除数b和余数r。注意，通常做除法的时候，除数是已知的，但这里b是未知的，所以需要考虑条件。解：因为，其中所以

因此，[引理]如果它是该形式的数中最小的正数（是任意整数，是两个不全为零的整数）；那么对于任意整数，

在此及此后，“”一词用于表示整数除法。证明要证明，只需除以余数（向左滑动查看完整公式）并证明即可。因为，是一个整数，所以它是一个整数。因此，由上式可知，形式为r=0的数中最小的正整数为r=0。因此，[定义]如果、都是整数，且、则d称为的公因数，几个数的公因数中最大的一个称为这些数的最大公因数，最大公因数用()表示。[定理2]如果引理的条件是，则和的因数与的公因数相同。证明：如果我们可以证明的所有公因数与的所有因数相同，则的最大公约数与最大除数相同，因此

(i)由引理可知(,为任意整数)，故即

因此，的任意因数都是的公因数。(ii)假设d是a和b的任意公因数，则因此，a和b的任意公因数也是的因数。因此，a和b的所有公因数与的所有因数相同。当然，a和b的最大公因数也与(a,b)的最大因数相同，即，a和b的公因数与(a,b)的因数相同。整数的可约性理论可以由定理2推导出来，具体请参考闵思和、严世坚：《初等数论》第一章3推论1.1（第10页）至4推论3.3（第15页），但该书应重复本文采用除法推导定理2的优点在于它指出了求最大公因数的方法，而本文推导定理2的过程则更加直接和抽象。2抽象代数的概括。而且这种方法和思想在抽象代数中得到了普及，对于抽象代数的发展有着重要的启发。本节的目的是对这方面进行一些介绍。首先，我们将介绍利用建立余数除法的方法可以建立有理数系数的多项式和余数除法的高斯（代数）整数，然后将它们综合起来，介绍欧氏环的概念和相关问题。[定理1]假设

,

是一个具有有理系数（即有理数）的多项式，那么存在一个唯一的具有有理数的多项式，使得。(1)次数<次数或r(x)0。证明：首先对f(x)的n次应用第二归纳法，证明q(x)、r(x)的存在性。当n [定义2] 若集合R是加法“+”和乘法“”的环，且(i)乘法满足交换律：即对于任意a和b都成立； (ii) R 具有单位1：即，对于任意，(iii)R 没有零因子：即，如果，则a=0 或b=0。则称R是一对“+”，“”是一个完整的环。不难验证：所有整数与整数的加法和乘法是一个完全环，所有高斯整数与复数的加法和乘法是一个完全环，多项式与有理系数多项式的加法和乘法是一个完整的环。它们分别称为整数。环、高斯整数环、有理系数多项式环。 [定义3] 积分环R称为欧几里德环，如果： (i) 存在从R的非零元素集合到非负整数集合的映射，即对于任意，有一个唯一的非负整数。 (ii) 对于任意，则存在a=bq+r，r=0 或整数环为欧氏环，只需取即可。有理系数多项式环是欧氏环，只需取a的次数即可。高斯整数的环是欧几里得环，只需要对高斯整数取。根据1中指出的方法和参考书，可以建立欧氏环的可约性理论和标准分解公式，甚至可以讨论更一般的主理想环的相应问题。不过，由于篇幅所限，这里不再赘述。有兴趣的读者可以自己讨论或者参考张和睿：《近世代数基础》第4章。还需要指出的是，高斯整数环只是代数整数环的一种特例。关于代数整数有丰富的理论。有兴趣的读者可以参考华罗庚：《数论导引》第十六章。3小学算术中的除法1定理1中提到的余数除法只是存在性结果，并没有给出具体算法。事实上，求商和求余的具体方法仍然是小学课本上讲授的算法。但是该算法的理论基础是什么？答案：就是1中的乘法表和定理1。本节的目的是澄清这个问题。这或许可以帮助中小学老师理解课本上的整数除法。这也表明中学教师学习了一些初等数论。有利。下面的推论和分析可能看起来有些复杂，但本质上是小学里所教授的除法的概括和代数化。只要牢牢抓住这一点，并在必要时举例帮助你理解，你就不会被那些复杂的公式所迷惑了。

假设a和b是两个正整数b1，将它们写成十进制：

0,0\leqslanta_{i}\leqslant9'data-formula-type='inline-equation'style='',

0,0\leqslantb_{i}\leqslant9'data-formula-type='inline-equation'style='',(1)

下面分几种情况讨论

情况1，nm此时ab，则令q=0，r=a，即a=qb+r,0rb情况2，n=m且此时ab，仍令q=0，r=a，案例3。和。（不妨假设，否则令q=0，r=a。）此时，我们从九十九乘法表中得知，有这样的（2）这里是小学算术中的试商，所以应该分为两种情况（即尝试讨论充分约简和约简不足两种情况）讨论：(i)此时可以证明：(3)现在我们来证明(3)。从(1)和(2)我们知道(ii)当时，那么和是。所以存在正整数使得(4)很容易找到。注：(3)、(4)表示在and的情况下，b除以a求商时，商的最高位为n-m+1，第一位例如a=310，则b=103，商为个位数，第一位为3；b=110时第一位为2；当b=165时，第一位数字为1。此时情况4nm和(2)不成立，所以我们考虑消除问题（即小学算术第一人考不出商的情况）。那么我们从乘法表可知，存在(5)与情况3类似，然后将其分为两种情况讨论：(i)那么可以证明：(6)其证明也类似于(3)的证明：从(1)和(5)我们知道(ii)此时，类似于(4)的证明有一个正确的整数使得(7)总结了情况3和4的讨论。从(3)(4)(6)(7)，我们得到以下[命题]设a，b由(1)表示且，则有二正整数使(8)其中分别为以b除a所得商数的位数及首位数码。若，且记，将上述命题应用于a’，b，即知有二正整数使（9）由(8)，(9)知故得(10)反复应用上述命题及上一段的论证知：存在两列正整数及使令，利用上式则得由引中的定理知以b除a所得的余数为r，商另一方面，由上述讨论知就是按小学算术中的算法求出的商，因此我们从理论上证明了小学算术中给出的求商和余数就是带余除法中的商和余数.