1、初等数论及其应用1.1 整除定义整数集 正整数指的是数 1, 2, ，而 整数 指的是数 0,1, 2,。全体整数的集合记为 Z，而全体正整数的集合记为Z+。 整数集 Z关于加、减、乘运算是封闭的 ：任意 a， b Z，有 a+b， a-b， ab Z。 但是，整数集 Z关于除法运算不是封闭的 ：存在 a， b Z， a/b 不属于 Z。比如： 6不能被 4整除。因此，我们需要考虑整除，即研究何时 a/b Z。2整除的定义 定义 1.1.1 设 a， b Z，且 b0。如果存在 q Z，使得 a=bq，则称 b整除 a，记作 b|a。此时， b叫做 a的因数 ， a叫做 b的 倍数 。 任意整
2、数 a，有 1|a，即 1是任意整数的因数；当 a0时，有 a|0和 a|a，即 0是任意整数的倍数，任意非零整数是自身的因数也是自身的倍数。 如果一个整数是 2的倍数，我们称它为 偶数 ；否则称它为 奇数 。偶数和奇数可分别表示如下的一般形式：2k， 2k+1， k Z。3整除的基本性质 命题 1.1.1 设 a， b， c Z。 如果 c|b， b|a，那么 c|a。 如果 b|a， c0，那么 cb|ca。 如果 c|a， c|b，那么对任意 m， n Z，有 c|ma+nb。 如果 a|b， b|a，那么 a=b或 a=-b。 证明 ：上述 4点的证明类似，这里仅证明第 4点。设b=a
3、q， a=bp，其中 p， q Z。于是b=aq=(bp)q=b(pq)若 b=0，则 a=bp=0，即结论成立；若 b0，则由上式可得 pq=1。由于 p， q Z，则p=q=1，或 p=q=-1，即结论成立。4带余除法 定理 1.1.1 设 a， b Z，且 b0，则存在唯一的 q， r Z，使得a=bq+r， 0 r0时，有 a=bq+r；当 b0时，有 a=b(-q)+r。这就证明了 q， r的存在性。 5带余除法 证明 ： 唯一性证明 。假设存在另一组 q*， r* Z，满足： a=bq*+r*， 0 r*|b|，则-|b|r-r*=b(q*-q)|b|。因此 b(q*-q)=0，从
4、而 r-r*=0，即 q*=q， r*=r，所以唯一性成立。 特别要注意的是， 带余除法是初等数论的证明中最基本、最常用的工具 。例如，证明下面整数不同进制表示相关的定理，就需要用到带余除法。6整数的表示 定理 1.1.2 设 b2是给定的正整数，那么任意正整数 n可以唯一表示为n=rkbk+rk-1bk-1+r 1b+r0，其中整数 k 0，整数 ri(i=0,1,.,k)满足 0rib， rk0。 证明 ：对给定的正整数 n，必存在唯一的整数 k 0，使得 bk nbk+1。由带余除法，存在唯一的的 q0， r0 Z，使得 n=bq0 +r0 ， 0 r0b。下面利用数学归纳法进行证明。这
5、里需要注意， 数学归纳法 包含两步：证明结论在 k=0时成立；假设结论在 k=m 0时成立，证明结论在 k=m+1时也成立。7整数的表示 证明 ：（ 1）当 k=0时，由于 1 nb，则有 q0=0，0r0 =nb，结论显然成立。（ 2）假设结论在 k=m 0时成立，那么当 k=m +1时，有 bm+1 nbm+2，而 n可以唯一表示为 n=bq0 +r0 （ 0 r0b），这样 bm+1 bq0 +r0 bm+2。由于 0 r0b，则 bm+1-b bq0 bm+2，即 bm q0 bm+1。由归纳假设知， q0 可唯一表示为q0 =smbm+sm-1bm-1+s 1b+s0，其中整数 si
6、(i=0,1,.,m)满足 0 sib， sm0。因此有n=bq0 +r0 =smbm+1+sm-1bm+s 1b2+s0b+r0， 这种表示是满足定理要求的唯一表示，否则与 q0唯一表示性矛盾。因此结论在 k=m +1时成立。8证明方法的讨论 上述定理的证明采用了 数学归纳法 ，它的一般证明步骤为： (1) 证明结论在 k=0时成立； (2) 假设结论在k=m 0时成立，证明结论在 k=m+1时也成立。 此外，上述定理的证明还可以采用如下方法：存在性证明采用 构造法 ，而唯一性证明采用 反证法 。可以当作课后练习，其中存在性证明的提示： 首先对 n应用带余除法 n=bq0 +r0（ 0 r0
7、b），然后不断地对上次得到的商应用带余除法，直到商为 0。9不同进制的转换 在上述定理给出的表示式中，如果 b取不同值，则代表不同进制的表示，常用的有 2进制（ b=2）、 10进制（ b=10）、 16进制（ b=16）等。为了区分不同进制，记 (rkrk-1r 1r0)b=rkbk+rk-1bk-1+ +r1b+r0。 由上述定理可以很容易得到任意正整数 n的 b进制表示 (rkrk-1r 1r0)b，计算方法如下：n=q0b+r0 =(rkbk-1+rk-1bk-2+ r1)b+r0q0= q1b+r1 =(rkbk-2+rk-1bk-3+r 2)b+ r1qk-2= qk-1b+rk-1=rkb + rk-1 qk-1= qkb+rk =0*b+ rk10
