选修4-6 初等数论初步《第一讲 整数的整除 一 整除 2.带余除法》优秀教案

选修4-6 初等数论初步《第一讲 整数的整除 一 整除 2.带余除法》优秀教案

A = { a ( kb；k(Z },

其中Z表示所有整数的集合，以后，仍使用此记号，并以N表示所有正整数的集合。

在集合A中有无限多个正整数，设最小的正整数是r = a ( k0b，则必有

0 < r < |b|， (2)

否则就有r ( |b|。因为b a，所以r ( |b|。于是r > |b|，即a ( k0b > |b|，a ( k0b ( |b| > 0，这样，在集合A中，又有正整数a ( k0b ( |b| < r，这与r的最小性矛盾。所以式(2)必定成立。取q = ( k0知式(1)成立。存在性得证。

唯一性 假设有两对整数q (，r (与q ((，r ((都使得式(1)成立，即

a = q ((b ( r (( = q (b ( r (，0 ( r (, r (( < |b|，

则

(q(( ( q ()b = r ( ( r ((，|r ( ( r ((| < |b|， (3)

因此r ( ( r (( = 0，r ( = r ((，再由式(3)得出q ( = q ((，唯一性得证。证毕。

定义1 称式(1)中的q是a被b除的商，r是a被b除的余数。

由定理1可知，对于给定的整数b，可以按照被b除的余数将所有的整数分成b类。在同一类中的数被b除的余数相同。这就使得许多关于全体整数的问题可以归化为对有限个整数类的研究。

以后在本书中，除特别声明外，在谈到带余数除法时总是假定b是正整数。

例1 设a，b，x，y是整数，k和m是正整数，并且

a = a1m ( r1，0 ( r1 < m，

b = b1m ( r2，0 ( r2 < m，

则ax ( by和ab被m除的余数分别与r1x ( r2y和r1r2被m除的余数相同。特别地，ak与r1k被m除的余数相同。

解 由

ax ( by = (a1m ( r1)x ( (b1m ( r2)y = (a1x ( b1y)m ( r1x ( r2y

可知，若r1x ( r2y被m除的余数是r，即

r1x ( r2y = qm ( r，0 ( r < m，

则

ax ( by = (a1x ( b1y ( q)m ( r，0 ( r < m，

即ax ( by被m除的余数也是r。

同样方法可以证明其余结论。