数论与有限域-第一章.pptVIP

第一章 整数与同余 第一节 整数 一、相关记号 二、最小整数公理 三、整除的定义及性质 一、相关记号 以后，如果没有特别声明，将用 大写英文字母Z表示由所有整数构成的集合； Z＋表示由所有正整数构成的集合； 小写英文字母a, b, c, d, ．．．表示整数，特别地 当几个小写英文字母在一起时，表示将这几个整数相乘，例如ab=a×b, abc=a×b×c； 当n是一个大于l的正整数时，an表示由n个相同的整数a相乘所得的积； 用记号|a|来表示整数a的绝对值，即 例如|2|＝|-2|＝2。 二、最小整数公理 最小整数公理（良序性）：每个正整数集的非空子集中都存在着一个最小的正整数。 注：虽然正整数集合具有良序性，但是由于许多整数的子集中都不具有最小值，因而由所有整数构成的集合Z并不具有良序性。 例如所有负整数构成的集合以及所有小于200的偶数构成的集合。 三、整除的定义及性质 在整数范围内，我们知道 整数+整数=整数； 整数-整数=整数； 整数×整数=整数。 但是整数除整数却不一定得整数，究竟什么样的整数除什么样的整数才能得到整数呢？ 三、整除的定义及性质 定义1.1.1： 设a，b是两个给定的整数且a≠0。如果存在整数c使得b=ac，则称a整除b，记为a|b，有时也称a是b的因子（或因数），b是a的倍数；反之，若找不到这样的整数c，则称a不整除b，记为a?b。 例如：易知3|6，而3?5，同时6的因子分别为 ±1, ±2, ±3, ±6。 三、整除的定义及性质 定理1.1.1 若整数a，b，c满足条件a|b且b|c，则a|c。 证明：若a|b且b|c，则由定义1.1.1知道存在整数e和f使得b=ae且c=bf，于是 c=bf=(ae)f=a(ef) 由于整数e与f的乘积仍然是整数，因而a|c。 例如：由于11|66且66|198，由定理1.1.1就有 11|198。 三、整除的定义及性质 定理1.1.2 设整数a，b，c满足条件c|a且c|b，则?m, n?Z，都有c|(ma+nb)。 证明：由于c|a且c|b，知存在整数e，f使得 a=ce，b=cf， 进而 ma+nb=mce+ncf=c(me+nf) 由于me+nf仍然是整数，因而 c|(ma+nb)。 例如：由于3|21且3|33，由定理1.1.2就有 3|(5×21-3×33)，即3|6。 三、整除的定义及性质 定义1.1.2 一个大于1的正整数，若只能被1和其本身整除，而不能被其他正整数整除，则称其为素数(或质数)，通常记为p或p1, p2, p3, …。 例如：2，3，5，7，11，13，… 都是素数。 定义1.1.3 大于1的不是素数的自然数称为合数。 例如：4，6，8，9，10，12，… 都是合数。 注：约定1不是素数。全体正整数可分为三类： l，全体素数以及全体合数。 第二节 整数的进位计数制表示法 一、带余数除法 二、整数的进位计数制表示法 三、数制转换 一、带余数除法 定理1.2.1(带余数除法) ：设a是正整数，b是整数，则一定存在唯一的整数q和r，使得b=qa+r，其中0≤ra，并分别称q与r为a 除b的商和余数。 证明：“唯一性” 假设存在整数q与r，以及整数q1与r1，使得 b=qa+r，0≤ra，且b=q1a+r1，0≤r1a。 则将两式相减，得到： r1-r=(q-q1)a。 由于q-q1仍然是整数，因而 a|(r1-r)。 一、带余数除法 证明：“唯一性” 假设存在整数q与r，以及整数q1与r1，使得 b=qa+r，0≤ra，且b=q1a+r1，0≤r1a。 a|(r1-r) 由假设0≤ra且0≤r1a，得到 -ar1-ra。 于是 r1-r=0，即r1=r。 进一步地，由b=qa+r=q1a+r1，得到 q1=q，即商q和余数r都是唯一的。 一、带余数除法 证明：“存在性”考虑由所有形如b-ka的整数构成的集合 T={b-ka , k=0, ±1, ±2, …}， 设： S={u|u?T且u?0} 则 集合S?? (只要取满足条件kb/a的整数k) 设其最小值为：r=b-qa ?0 接下来来证明ra。 若r?a，则 rr-a （a0） =b-qa-a