(1.1)-第0章预备知识近世代数

近世代数(ContemporaryAbstractAlgebra)2主要参考书JosephA.Gallian,ContemporaryAbstractAlgebra,8thEdition,CengageLearning,2010.3整数性质模运算归纳法复数第0章预备知识等价关系映射第0章预备知识(Preliminaries)4整数性质模运算归纳法复数第0章预备知识等价关系映射第0章预备知识(Preliminaries)5良序原理(WellOrderingPrinciple)一、整数性质每一个非空正整数集合都包含一个最小整数整数性质注意：在具体问题中,良序原理有许多变形.比如，设a为整数,S为任一非空整数集合.若S中元素都大于等于a,

则S包含最小元素,若S中元素都小于等于a,

则S包含最大元素.6本课程记号约定

Z：整数集合；C：复数集合；R:实数集合；Q:有理数集合令F为上面四个数集之一，F*=F-{0},

F+={x∈F|x>0}7设

s,t,u∈Z，满足

s=tu倍数(multiple):称

s

为t

的倍数.因子(divisor):若

t≠0,称

t

为

s的一个因子,记为t|s.

反之,记为

素数(prime):一个大于1的整数,如果它大于0的因子只有1和它自

己,则称它为素数.1、因子,素数,倍数整数性质证：定理0.1

带余除法(DivisionAlgorithm)设a∈Z,b∈Z+,则存在唯一的q,r∈Z,使得a=bq+r,0≤r<b.8唯一性：假设存在两对整数q,r;x,y满足a=bq+r=bx+y,0

≤r,y<b.

不妨设r≥y.则上式可变形为：r-y=b(x-q).则b整除r-y但0

≤r-y<b.从而必有r-y=0,即r=y.因b>0,故x-q=0,即x=q.

整数性质作为良序原理的第一个重要应用，先来证明带余除法.存在性：令S={a-bk|k∈Z,a-bk≥0}.显然S非空.根据良序原理，可取r=a-bq为S中最小元素.假设r≥b.则r-b<r,且0≤r-b=a-b(q+1)∈S.与r的极小性矛盾.因此，0≤r<b.

定义：带余除法中,q

为

b

除

a的商,

r

为余数.本次课到此结束谢谢！10整数性质模运算归纳法复数第0章预备知识等价关系映射第0章预备知识(Preliminaries)112、最大公因子，互素最大公因子(GreatestCommonDivisor):非零整数a,b的最大的公因子称为是a,b的最大公因子,记为gcd(a,b).互素(RelativePrime):如果

gcd(a,b)=1,那么称整数a,b互素.整数性质两个整数的GCD如下性质在近似代数扮演着特别重要的角色,其证明应用到了带余除法和良序原理.

定理0.2(GCD是一个线性组合)

任给两个非零整数a,

b,则

存在整数s,t

使得

gcd(a,b)=as+bt.gcd(a,b)是具有as+bt形式的最小正整数.

12证：令S={am+bn|m,n∈Z,am+bn>0}.则S非空.根据良序原理,S中有最小元素,设为d=as+bt>0.下证d=gcd(a,b).易见gcd(a,b)|d.

故只需证明d为a,b的公因子.由带余除法，可得a=dq+r(0≤r<d).从而,r=a-dq=a(1-sq)+btq.由d的极小性，可得r=0,即d|a.类似地，可证d|b.整数性质13推论:如果整数a,b互素,那么存在整数

s,t,

使得

as+bt=1.值得指出的是：推论中条件既充分也必要.充分性的证明留作练习Ex.11,请读者自行完成.整数性质上述定理的特殊情形,即当a,b互素时,在近世代数中是相当重要的,将其单独写为一个推论.14欧几里德引理(Euclid’sLemma)设

p是素数,且p|ab,

则

p|a或者

p|b.证：若p不整除a，那么gcd(p,a)=1.由上面推论,存在整数s,t使得1=as+pt.等号两边同乘以b，有b=abs+pbt.

从而，p|b.整数性质下面引理给出素数的一个重要性质.在今后的学习中,将会经常用到.注：当p不是素数时,欧几里德引理不一定成立.比如6|(4•3)但6既不整除4,也不整除3.15定理0.3算术基本定理(FundamentalTheoremofArithmetic)任意大于1的整数可分解为素数乘积,若不考虑因子顺序分解惟一.定理0.3的存在性部分的证明将在讲归纳法时给出证明(例子11),而唯一性部分的证明则由欧几里德引理可证

(留作练习Ex.31，读者自行完成).整数性质下面定理表明素数是构成整数的基本元素.163、最小公倍数(LeastCommonMultiple)非零整数a,b的所有公倍数中的最小正整数称为a,b的最小公倍数,

记为

lcm(a,b).简单观察：

a,b的任一公倍数均是lcm(a,b)的倍数.这一结论留作练习Ex.10,读者自行完成证明.整数性质在整数性质这一部分的最后,我们介绍如下概念.本次课到此结束谢谢！18整数性质模运算归纳法复数第0章预备知识(Preliminaries)第0章预备知识等价关系映射19二、模运算现在是三月份，25个月后是几月份

25=2×12+1,答案:四月模运算

模运算是带余除法的一个重要应用，也是我们常用的计数方法一个抽象，比如：20模运算这些运算法则的证明留作练习Ex7和Ex9,读者自行完成.模运算例5：试证任意三个连续整数的立方和被9整除.证明：设n为一整数.要证n3+(n+1)3+(n+2)

3mod9=0mod9.由第二条模运算法则：只需验证r3+(r+1)3+(r+2)3mod9=0mod9,其中r为9除n的余数.给定正整数n和整数a,则由带余除法,知存在唯一的整数q,r

使得,a=qn+r且0≤r<n.定义：amodn=r.模运算具有如下运算法则amodn=bmodn

当且仅当

n|(a-b).令a

modn=c,bmodn=d,则

(a+b)modn=(c+d)modn

且abmodn=cdmodn.21三、复数1.复数的标准形式：z=a+bi,

其中i

2=-1,a和b

为两个实数，分别称为复数z的实部(realaxis)和虚部(imaginaryaxis).2.复数的两极形式：其中

为z到原点的距离,也记为|a+bi|.

ReIm0rba复数22定理0.4复数运算性质

(1)

加法：(2)

乘法：(3)

除法：(4)逆元：对任意非零复数

a+bi,总存在复数

c+di使得:

(a+bi)(c+di)=1复数23(5)复共轭：(6)方幂：(7)根：证明:(1)-(5)可根据定义直接验证.

(6)将在例8中给出证明

,(7)留作练习Ex.25,读者自行完成.复数本次课到此结束谢谢！25整数性质模运算归纳法复数第0章预备知识(Preliminaries)第0章预备知识等价关系映射26四、归纳法设P

为一个与正整数有关的命题,要证P对任意整数都成立,只需做以下两步：验证P

对1

成立；

假设

P对n

成立，证明P对n+1也成立.定理0.5(第一数学归纳法)设S为一个包含

a的整数集合，且具有如下性质：只要n≥a且n∈S,则必有n+1∈S.

那么对任意整数x≥a,都有

x∈S.

归纳法由数学归纳有两种形式的证明，均和良序原理等价.先来看第一种.27例7:给定一把直尺，一个圆规及一个单位长度.证明对任意正整数n,

可以做出长度为的线段.关键点：如何尺规做直角?画一线段，分别以两端点为圆心,以大于线段一半为半径画圆，连接两圆之交点.归纳法注意：若两直角边分别为1和，则斜边为28例8:(DeMOIVRE’s定理)其中,n为任意正整数,为任意实数.证:(1)显然n=1

时命题成立.(2)假设对某一个正整数n≥1

成立，即命题对整数n+1成立.得证.归纳法29设P是与整数有关的命题，若能：验证P对整数a成立；在P对任意a≤x<n的x成立的假设下，证明P对n

也成立.

那么P

对任何满足

m≥a

的整数m成立.定理0.6(第二数学归纳法)设S为一个包含a的整数集合,具有如下性质：如果对任意的x满足a≤x<n,都有x∈S,那么n∈S.

那么对任意整数x≥a,都有

x∈S.归纳法30例9:(算术基本定理的存在性部分)

任意大于1的整数n都可分解成素数乘积.证:

显然,n=2可分解为素数乘积.设对任意整数2≤k<n,k

可分解为素数乘积.若n

是素数,结论自然成立.若n不是素数,则有n=ab,2≤a,b<n.由归纳假设,a,b可分解为素数乘积,故n可分解为素数乘积.归纳法31例10:赌博公司只有5美元和8美元赌牌，问不能为赌资的最大数目是多少？证:5,8,10,13,15,16,18,20,21,23-26,28,29,30,…猜测为27.需证若n≥28,则n=5s+8t,其中s,t>0.n=28

时成立：假设猜测在n≥28时成立,即n=5s+8t,其中s,t>0.则必有或者s>2或者t>2.

若s>2,则n+1=5s+8t-15+16=5(s-3)+8(t+2).若t>2,则n+1=5s+8t+25-24=5(s+5)+8(t-3).故猜测对n+1也成立.归纳法最后,我们来看一道刊载于1988年美国《Discover》杂志1月期的一道题.本次课到此结束谢谢！33整数性质模运算归纳法复数第0章预备知识(Preliminaries)第0章预备知识等价关系映射34五、等价关系数学中，某个环境下两个不同的对象，在另一环境中却会被看作是等价的。比如：在通常加法意义下2+1与4+4显然不同，但在mod5加法运算下它们却是相等的。等价关系为此，我们需要将“相等”适当推广，即“等价”。35关系:设A是一个集合,

A×A={(a,b)|a,b∈A}

的一个子集R

称为

A的一个关系.

给定集合A的任意关系R,对A中任意元素a和

b

,如果(a,b)

∈

R，则称a和

b符合关系R:记为

aRb.

否则称a和

b不符合关系R.等价关系1、关系(Relation)362、等价关系(EquivalenceRelation)集合

A

上的一个关系R

称为

等价关系，若(1)自反性：(2)对称性：(3)传递性：等价关系注：(1)等价为相等的推广，常用~,≈或≡表示等价关系R.

(2)如果~是集合A上的一个等价关系,则称

[a]={x∈A|x~a}为A的含a的等价类.37例11:设S为平面上所有三角形组成的集合.定义：

R={(a,b)|a,b相似,a,b∈S}.则R为集合S上的一个等价关系.此时,通常用a

~

b表示aRb.等价关系例12:给定正整数n.定义:R={(a,b)|amodn=bmodn,a,b∈Z}.则根据模运算的法则不难验证R为集合Z上的一个等价关系.此时,通常用a≡b表示aRb.例13:在上题中,令n=7,则可知[1]={…,-20,-13,-6,1,8,15,…}和[4]={…,-17,-10,-3,4,11,18,…}为两个等价类.通常将每个这

样的等价类称为模7的剩余类.383、分划(Partition)分划:集合S的某些子集(叫做类)构成的集合称为S的一个分划,

如果S中每个元素属于且只属于一个子集(即所有子集的并为S,且任何两个不同子集的交为空).等价关系39例14:集合{0},{1,2,3,…},{…,-3,-2,-1}为整数集的一个分划.例15:非负整数集和非正整数集不是Z

的分划.等价关系由该定理可知：整数集合Z模

n剩余类{[0],[1],[2],……,[n-1]}构成Z

的一个分划.定理0.7(等价类与分划)

集合A上一个等价关系决定A的一个分划.

集合A上任意一个分划决定A的一个等价关系,且该分划与该等价关系决定的分划相同.40后半部分的证明：设是A

上的一个分划.定义A的关系

在同一Si中.容易验证是等价关系.设则有.(有关验证,留作练习Ex.61)

等价关系证明:设~是集合A

上的一个等价关系，任给A中两个元素a,b,则

或

[a]=[b].

等价类集合

是A

的一个分划.定理0.7(等价类与分划)

集合A上一个等价关系决定A的一个分划.

集合A上任意一个分划决定A的一个等价关系,且该分划与该等价关系决定的分划相同.本次课到此结束谢谢！42整数性质模运算归纳法复数第0章预备知识(Preliminaries)第0章预备知识等价关系映射43六、映射1、

映射(Function(Mapping))集合A到集合B的一个映射ϕ是一个对应法则,使得对A中任一元素a,在B中有唯一元素b与之对应.称A

为ϕ的定义域(d