第1章 引言和预备知识
这一章的内容虽是准备部分，但非常重要，如果不熟悉，以后会处处受阻.考虑到各人原有的基础不同，这一章的内容和习题适宜自学.但不管是谁都应把内容和习题通读一遍，有重点地在某些内容上多加注意，例如关于整数的同余运算一定要熟悉起来.
1.1 几类实际问题一、 内容提要  本节的目的是提出一些可用近世代数解决的实际问题，以期引起读者的兴趣.由于读者现在还未学习到有关内容，所以我们只能用初等的方法来做这些题，从中体会到问题的困难.
二、 习题1.1详细解答
1.1-1 用两种颜色的珠子做成有5颗珠子的项链，问可做出多少种不同的项链？
分析 在学群论前我们没有一般的方法，只能用枚举法.
解 用笔在纸上画一下，用黑白两种珠子，分类进行计算: 全白只1种，四白一黑1种，三白二黑2种，二白三黑2种，一白四黑1种，全黑只1种.因此可得总共8种.
点评 读者不妨增加颜色数或珠子数再做做看，可以发现越来越难做，从而体会到必须寻找更高明的方法.
1.1-2 对正四面体的顶点用2种颜色着色，有多少种本质上不同的着色方法？
分析 我们可以用硬一点的纸做一个正四面体，也可在纸上画一个正四面体.看看有多少种着色方法.这里所说的本质上不同的着色方法，是指对两种着色不论怎样转动此正四面体它们都不能重合.
解 类似第1题，用枚举法可得5种.
点评 读者不妨增加颜色数再做做看，比项链问题更复杂，如没有更好的方法是很难走远的.
1.1-3 有4个顶点的图共有多少个？其中互不同构的有多少个？
分析 复习一下图的概念，图一般指有标号的图，n个点的图有2n
2=2n(n-1)2个.但其中有很多是互相同构的，即不考虑点号，两个图可以重合就称为它们同构.互不同构的图又叫无标号图.求互不同构的图的个数是很难的问题，需要用群论方法.
解 由本节内容，有4个顶点的图共有64个图.用分类计数的方法可得共有11个互不同构的图: 无边的空图1个，一条边的图1个，有2条边的图有2个，有3条边的图有3个，有4条边的图有2个，有5条边的图有1个，有6条边的图有1个.
点评 读者不妨算一下有5个顶点的图共有多少个有标号图，有多少个互不同构的图.虽只增加一个点，但难度有很大的提高.
1.1-4 如何用圆规5等分一个圆周？
分析 可先作一个单位圆，设其半径长度为1，问题变成如何求出五边形的边长.
解 用初等数学的方法求五边形的边长: 作一个顶角为36. 、腰长为1的等腰三角形，设底边长为a，则a就是十边形的边长，以a为半径以单位圆周上任意一点为圆心在圆周上交出两点，则这两点之间的距离就是五边形的边长.那么a怎么求呢？只要在那个等腰三角形上作一条辅助线:底角的角平分线，再利用相似三角形边长成比例的关系，可得a=5-12，分别以1和2作直角边，斜边就是5，所以a就可作出了.图 1.1
点评 由于一个数的开平方可以在圆上作出(见图1.1，即主教材图4.2),所以，如果正n边形的边长，可由某个有理数经过有限次开平方与四则运算求得，则就可n等分一个圆.但这是否是可n等分一个圆周的必要条件呢？我们将在第4章中详细讨论此问题.
1.1-5 如何用根式表示3次和4次代数方程的根？
查看数学手册.因公式较复杂，不在这里列出了.
点评 从手册可见，对3次和4次代数方程可通过几步表示它的根，每一步都是根式表示式.而对于5次以上的某些代数方程，伽罗瓦证明了对某些5次方程不能用根式表示它的根.我们将在第5章中讨论此问题.
第1章 引言和预备知识1.2 集合与映射1.2 集合与映射一、 内容提要  由于集合的概念太基本了，没有必要从头复习，我们只是强调和补充一些东西.
1. 集合
 集合的记号: 本书用大写字母表示集合.|A|表示集合A的元素的个数，称为基数.用|A|<∞表示有限集.
整数集合记作: Z.正整数(即自然数)集合记作: Z+(自然数是否包含0，有不同的说法，高等教育出版社出版的《数学手册》把自然数定义为正整数).非负整数的集合无专门的记号.非零整数的集合记作: Z.类似的，对有理数有记号: Q,Q+,Q；对实数有记号: R,R+,R；对复数有记号: C,C.
 集合A的幂集记作: P(A)=2A={A的所有子集的集合}.当|A|<∞时有|2A|=2|A|.
 包含与排斥原理: 设A1,A2,…,An是集合S的有限子集，则∩ni=1Ai=∑ni=1|Ai|-∑1≤i<j≤n|Ai∪Aj|+…+(-1)n-1∪ni=1Ai, 
∪ni=1Ai=∑ni=1|Ai|-∑1≤i<j≤n|Ai∩Aj|+…+(-1)n-1∩ni=1Ai.当并集的基数比交集的基数容易求时，用第一个公式.反之，用第二个公式.
2. 映射
集合A到集合B的映射记作: f:xf(x)(A→B).
 f是单射f(x1)=f(x2)x1=x2.
 f是满射f(A)=B.
 f是双射f既是单射又是满射.
 f可逆f是双射.
二、 习题1.2详细解答
1.2-1 设|A|<∞，用二项式定理证明: |2A|=2|A|.
分析 二项式定理为: (a+b)n=an+n
1an-1b+n
2an-2b2+…+bn.求幂集的元素个数如何与二项式定理联系起来呢？我们从二项式系数n
k入手，它是从n个元素中取k个元素的取法，正好是k元子集的个数，而全部子集的个数正好就是这些二项式系数之和.
证 设A={a1,a2,…,an}，由于A中k元子集的个数等于二项式系数n
k，于是把它们从k=1到k=n加起来，再加一个空集，所以|2A|=1+n
1+n
2+…+n
n=(1+1)n=2n=2|A|.  点评 证明该公式方法至少有以下几种: 
证法1 如主教材1.2.2(指主教材的节号，下同.例子号，定理号等均指主教材中的.)中所说: 每一个元素有在子集中与不在子集中2种可能，因而共有2n种可能，每一种可能对应一个子集，所以共有2n个子集.
证法2 用二项式定理.
证法3 利用主教材1.2.6节中公式: |BA|=|B||A|.令A={a1,a2,…,an}, B={0,1}，则每一个A到B的映射对应一个子集，所以全部子集的个数为|BA|=|B||A|=2n.
1.2-2 一个班有93%的人是团员，80%的人担任过社会工作，70%的人受过奖励，问：
(1) 受过奖励的团员至少占百分之几？
(2) 三者兼而有之的人至少占百分之几？
分析 该题是求几个集合的交集的基数，可用包含与排斥原理得到比较精确的结果.
解 设A为团员的集合，B为担任过社会工作的人的集合，C为受过奖励的人的集合，则由包含与排斥原理，可得
(1) |A∩C|=|A|+|C|-|A∪C|≥93+70-100=63, 
所以受过奖励的团员至少占63%.
(2) |A∩B∩C|=|A|+|B|+|C|-|A∪B|-|B∪C|-|A∪C|+|A∪B∪C|，由于|A∪B∪C|-|A∪B|≥0，所以|A∩B∩C|≥|A|+|B|+|C|-|B∪C|-|A∪C|
≥93+80+70-100-100=43.故三者兼而有之的人至少占43%.
点评 该题主要是复习集合运算的包含与排斥原理.对于集合个数较少时，可用画图的方法来确定.
1.2-3 在不大于1000的正整数中，求：
(1) 不能被5, 6, 8中任何一个整数整除的个数.
(2) 既非平方数也非立方数的个数.
分析 利用包含与排斥原理，参考主教材例1.2.1.
解 (1) 设X=［1,1000］表示1到1000的所有整数，A={x|x∈X&5|x}，即为X中能被5整除的所有整数的集合，B={x|x∈X&6|x}, C={x|x∈X&8|x}.则|A|=10005,  |B|=10006,  |C|=10008, 并可求出|A∩B|=10005×6=33,  |B∩C|=1000［6,8］=41, 
|A∩C|=10005×8=25,  |A∩B∩C|=1000［5,6,8］=8, 其中［6,8］和［5,6,8］是最小公倍数的记号.记号x表示x的下整数，x表示x的上整数.所以所求的个数为|X|-|A∪B∪C|=1000-|A|-|B|-|C|+|A∩B|
+|B∩C|+|A∩C|-|A∩B∩C|
=1000-200-166-125+33+41+25-8
=600.  (2) 设A为X中平方数的个数，B为X中立方数的个数，则|A|=1000=31,  |B|=31000=10, 
|A∩B|=61000=3.所以所求的个数为|X|-|A∪B|=1000-|A|-|B|+|A∩B|
=1000-31-10+3
=962.  点评 根据题意，首先确定是求集合的交还是并，然后利用包含与排斥原理.
1.2-4 设|A|=m, |B|=n，求：
(1) A到B的单射有多少个？
(2) 当m=3, n=2时，求A到B的满射有多少个？
分析 f: A→B是单射|f(A)|=|A|，因而|A|≤|B|.
f: A→B是满射|f(A)|=|B|，因而|A|≥|B|.
解 (1) 当m>n时，显然不存在A到B的单射.
当m≤n时，由于单射的像必是B中的某个m-子集，且和子集元素的次序有关，由此可得A到B的单射个数为以下从m个元素中选取n个元素的选排列数: P(m,n)=m(m-1)…(m-n+1).  (2) 当m<n时，显然不存在A到B满射.
当m≥n时，存在A到B满射.对于m=3, n=2，设A={a1,a2,a3}, B={0,1}，我们知道A到B全部映射数为8，非满射只有2个，所以A到B的满射有6个.
点评 对一般情形，求满射数的问题可参看［4］p.52-53.(参考文献的页码是本书后所附的参考文献，下同.)
1.2-5 证明实数区间(0, 1)与(-∞,+∞)等势.
分析 关键是在这两个集合之间找一个双射.
证 作映射 f:xlnx1-x.可证f是单射: 任取x1,x2∈(0,1)，有lnx11-x1=lnx21-x2x11-x1=x21-x2x1-x1x2
=x2-x1x2x1=x2.所以f是单射.
再证f是满射: 任取y∈(-∞,+∞)，令y=lnx1-x，可解出x=ey1+ey∈(0,1)使f(x)=y，所以f是满射.
综上，f是双射，因此(0, 1)与(-∞,+∞)等势.
点评 可以找到很多满足要求的映射，读者试另找一个双射.
1.2-6 设f是A到B的一个映射，SA，举例说明f-1［f(S)］=S是否成立？ 
注意 这里的记号f-1并非指f的逆，f不一定可逆.f-1［T］表示T的全原像.
解 不一定成立.
成立的情况: 显然当f可逆时，f-1［f(S)］=S成立.实际上，只要f是单射，式子就成立: x∈S，设f(x)=y，由于f是单射，y的原像只有x，即f-1［f(x)］=x，所以f-1［f(S)］=S.
不成立的情况: 只要举一个f不是单射的例子.例如: f:xx2, R→R.取S={1}，则f(S)={1}，但f-1［f(S)］=f-1(1)={-1,1}≠S.
点评 可以一般的证明: f-1［f(S)］=S成立的充分必要条件是f是单射.
1.2-7 设|A|<∞, f:A→A，证明以下三个命题等价: 
(1) f是单射；     (2) f是满射；     (3) f可逆.
分析 这个题的结论很重要，即有限集上的单射、满射与双射都是互为充要条件.证明方法并不复杂.
证 用循环证法: 
(1)(2): 因为f是单射，且A是有限集，故有|f(A)|=|A|.所以f是满射.
(2)(3): 因为f是满射，故有f(A)=A.下面用反证法证明f是单射: 假设f不是单射，由于A是有限集，必故有|f(A)|<|A|.与f是满射矛盾，所以f是单射.因而f是双射，即可逆.
(3)(1): 显然.
点评 我们再强调一下，对有限集这个结论很重要！即有限集上的单变换必是满变换，也必是双变换和可逆变换.通常遇到有限集的问题我们要充分利用有限性使问题简化，甚至可列出所有的元素来进行分析.
1.2-8 设A≠，证明不存在A到它的幂集P(A)的双射.
分析 如果A是有限集，这个结论是显然的.因为P(A)的元素个数多于A的元素个数，因此不存在A到P(A)的双射.但对于无限集，就不能用用这种方法证明了.下面的证法有特殊的技巧.
证 用反证法.
假设存在A到P(A)的双射f:xf(x)=Sx∈P(A).在A 中取一个满足以下条件的子集: T={x|x∈A&xSx}.  T∈P(A)，由于f是满射，存在a∈A使f(a)=Sa=T，现我们分析a是否在T中？
若a∈T，根据T的定义有aSa，即aT，矛盾.
若aT，即aSa，根据T的定义有a∈T，也矛盾.
所以不可能有这样的双射存在.
点评 是否有其他的证明方法呢？如有更简单的证明方法请发Email至hugz@tsinghua.edu.cn.
1.3 二 元 关 系一、 内容提要1. 二元运算和代数系  我们从小学开始所做的运算大多是两个数的运算，但不太关心数的范围的变化.例如，两个正整数相减，其结果可能跑出正整数的范围；一个整数开平方，其结果不仅可能跑出整数的范围，而且可能跑出有理数的范围.在近世代数中，不管做什么样的运算，我们始终念念不忘是在什么集合里进行，其结果是否还在这个集合里？而且只有其结果仍在原集合的运算称为二元运算，具体定义如下: 
1.3 二元关系 二元运算: 设S为非空集合，则映射f:S×S→S就称为S中的一个二元运算.其最主要之点是满足封闭性和惟一性.
 代数系: 定义了一个或几个二元运算的集合就称为一个代数系.对不同的集合定义不同的运算就得到不同的代数系，例如群，环，域等.代数系是近世代数的基本舞台.
2. 二元关系和等价关系
我们从小学开始就知道相等、大于和小于等关系，后来学几何又知道三角形的全等、相似等关系，在线性代数里又有矩阵的相似、相合等关系.这些都是二元关系.其中最重要的是等价关系.
 二元关系: 在两个集合A和B的元素之间如果有一个规则R, a∈A, b∈B可判断aRb(a与b符合规则R),或aR′b(a与b不符合规则R).则规则R就称为集合A和B的元素之间的一个二元关系.
 等价关系: 在同一个集合里，一个二元关系如果满足3个条件: 反身性，对称性和传递性.则此二元关系称为此集合中的一个等价关系，等价关系记作～、= 、≡ 等.
 等价类及其代表元: 设集合A中的一个等价关系为～，则子集a-={x|x～a}称为以a为代表的等价类，它的记号有: a～, \等，以a-最简单，本书主要采用此记号.
 商集: A中等价类的集合，记作A/～={a-|a∈A}，称为A模～的商集.它是A的幂集的一个子集.
 一个重要的等价关系--同余关系(非常重要！): 先在整数集合Z中定义一个二元关系称为整除关系:  a|bc∈Z使b=ac.然后可定义两整数的同余关系.
整数集合Z中模n的同余关系记作: ≡(mod n)，定义为a≡b(mod n)n|(a-b).这个等价关系的记号有点复杂和特殊， "a与b模n同余”习惯记作a≡b(mod n).整数模n的同余类: a-={a+qn|q∈Z}.a是a-的代表元，代表元不是惟一的.若取代表元满足: 0≤a<n，则称它是正则代表元，是惟一确定的.
有的书把同余类记作: \={a+qn|q∈Z}.
整数模n的商集: Zn=Z/≡(mod n)={0-,1-,…,n-1}.称为整数模n的同(剩)余类集合.
二、 习题1.3详细解答
1.3-1 A={1,2,3,4,5}，在2A中定义二元关系～: S～T|S|=|T|.证明～是等价关系，并写出等价类和商集2A/～.
分析 此题虽然简单，但对还不太熟悉等价类和商集的读者来说，还是应认真做一下.
证 易证～满足等价关系的三个条件，反身性，|S|=|S|S～S；对称性: S～T|S|=|T|T～S；传递性: S～T,T～U|S|=|T|=|U|S～U.
等价类为: ={}, {1}={{1},{2},{3},{4},{5}}, {1,2}={{1,2},{1,3},{1,4},{1,5},{2,3},{2,4},
    {2,5},{3,4},{3,5},{4,5}}, 
{1,2,3}={{1,2,3},{1,2,4},{1,2,5},…,{3,4,5}}, 
{1,2,3,4}={{1,2,3,4},…,{2,3,4,5}}, 
A-={A}.  商集为2A/～={,{1},{1,2},{1,2,3},{1,2,3,4},A-}.
点评 这是概念题，虽然简单，但必须仔细写一写，以加深印象，并熟悉表示方法.
1.3-2 S={0,1,…,n}, f:Ar(A)(Mn(R)→S).求由f所决定的等价关系，并决定等价类和商集.
分析 本题是把所有实n阶矩阵按秩分类，注意把等价类的代表元写得简单一些.
解 f所决定的等价关系～为: A～Br(A)=r(B).易证～满足等价关系的三个条件(略).在秩为k的等价类中最简单的矩阵为Ik0
00，所以得到等价类: Ik0
00={A|A∈Mn(R),r(A)=k},k=0,1,…,n.
商 集: Mn(R)/～=Ik0
00k=0,1,…,n.  点评 矩阵集合是近世代数的重要研究对象，我们必须对它很熟悉.
1.3-3 在Mn(C)中定义二元关系～: A～B存在可逆阵P使PAP-1=B.证明～是等价关系，并决定等价类和商集.
证 由于所定义的二元关系～是矩阵的相似关系，在线性代数中已经证明过它是等价关系.等价类中最简单的代表元是约当标准形，但是由于约当标准形很难全部表达出来，所以无法再继续下去.
点评 有些问题中等价类的代表元很难表达，因而商集也写不出来，我们只要从概念上理解清楚就行了.
1.3-4 设S为n阶实对称矩阵的集合，定义二元关系～: A～B存在可逆阵C使CTAC=B，证明～是等价关系，并求|S/～|.
分析 这是线性代数中的矩阵相合关系，已证明过是等价关系，这里不妨再证一下.由于实对称矩阵可通过相合变换化为对角元素为1，或-1，或0的规范形，所以等价类的最简单的代表元就是规范形.
证与解 反身性: ITAI=AA～A.对称性: A～BCTAC=B(C-1)TBC-1=AB～A.传递性: A～B,B～CP,Q:PTAP=B,QTBQ=C(PQ)TA(PQ)=CA～C.
在线性代数中我们知道实对称矩阵可用可逆矩阵化为规范形，所以得商集为S/～=-Ik00
0Il0
0000≤k+l≤n.其元素个数可以这样来计算: 先看规范形中-1的个数，如有k个-1，则对应n-k+1个不同的矩阵，因而总数为∑nk=0(n-k+1), 再变换一下和式中的变量，得|S/～|=∑nm=0(m+1)=(n+1)(n+2)2.  点评 因为实对称矩阵的相合标准形可取对角元素为-1, 1或0的规范形，因此商集元素的个数就是不同规范形的个数.
1.3-5 举一个偏序集但不是全序集的例子，并画出它的Hasse图.
解 考虑到画图的方便，可举有限集的例子，例如: 有限集的幂集对包含关系所构成的偏序集，有限整数集对整除关系所构成的偏序集.
详解略.
点评 此题虽简单，但对初学者还是要认真写一写.
1.3-6 已知两个偏序集的Hasse图形如下，分别写出它们的偏序集及偏序关系.
解 按偏序的定义，可直接列出所有有序的关系的元素对就可以了.
(a) 的偏序集可表为: (S,≤)，其中S={a,b,c,d,e,f,g}, ≤={a<b,a<c,b<d,b<e,c<f,c<g}.  (b) 的偏序集可表为: (T,≤)，其中T={a,b,c,d,e,f}, ≤={a<b,a<c,a<d,a<e,d<f,e<f}.图 1.2
  1.3-7 用两种方法定义Z的序，使它成为一个良序集.
分析 良序集要求任何两个元素都有序，且任何子集都有最小元.首先要使整个集合有最小元，我们可以把整数轴选择不同的点把左边折过来到右边，从而得到不同的良序集.
解 (1) 取0作为最小元，在Z中定义偏序关系≤为a<b|a|<|b| 或 |a|=|b| 且 a<b, 
a=ba=b.其中右边的<和=为普通的小于和等于.按此序排列的整数集合为0,-1,1,-2,2,-3,3,….  下面证明(Z,≤)是良序集: 设S是(Z,≤)的任一非空子集，令A={|x||x∈S}, 则A是非负整数集的子集，由非负整数集的良序性，A有最小元a，显然，a（或-a）也是S的最小元，所以(Z,≤)是良序集.
(2) 取1作为最小元，在Z中定义偏序关系≤为 a<b|a-1|<|b-1|或|a-1|=|b-1|且a<b, 
a=ba=b.其中右边的<和=为普通的小于和等于.按此序排列的整数集合为1,0,2,-1,3,-2,4,-3,5,….良序性证明类似(1).
点评 以上两种方法比较类似，是否有其他的差别较大的方法？
1.4 整数与同余方程1.4 整数与同余方程一、 内容提要  虽然我们对整数已经很熟悉了，但这一节内容的重要性无论怎样强调都不过分.可以说，全书的内容都以本节内容为基础，是它的推广与发展.
1. 整数运算的几个重要公式(非常重要！) 
 带余除法定理: a,b∈Z, b≠0，则存在惟一的q,r∈Z满足a=qb+r 且 0≤r<|b|.并记作a mod b=r, 或 a(mod b)=r, 称a模b的余为r.用前面给出的同余的概念有a≡r(mod b).这里用了两个略有不同的记号，它们的区别是: amod b是一种运算，给出惟一的结果，用等号表示.而≡(mod b)给出的是两个整数之间的关系，用恒等号表示.例如，7mod 5=2,   或7(mod 5)=2.
7≡2≡-3≡…(mod 5).显然有a1≡a2(mod b)a1mod b=a2mod b, 所以两个整数模b同余就是它们模b的余相同，这就是同余这个名词的意义.
注 记号amod b是本书根据近代文献引入的一个新的记号，在实际应用中很有用.在本书中，当强调求余数时用等号“=" ，当强调表示两个数的同余关系时用恒等号“≡" .
 算术基本定理: 每一个大于1的正整数n可分解为素数的幂之积: n=pε11pε22…pεss, 其中p1,p2,…,ps是不同的素数，此式称为整数的标准分解式.
利用算术基本定理可计算出正整数n的因子数为(ε1+1)(ε2+1)…(εs+1).
2. 最大公因子
 最大公因子定义: 设a,b∈Z，不全为0，若有d∈Z满足: (1)d|a且d|b;(2)如果有d′满足d′|a且d′|b，则d′|d.则称d是a与b的最大公因子.当d是a与b的最大公因子时，-d也是a与b的最大公因子，我们把正的最大公因子记作(a,b).
类似可定义最小公倍数，a与b的正的最小公倍数记作\.
 最大公因子定理(或Bezout公式): 设a,b∈Z，不全为0, a与b的最大公因子为d=(a,b)，则存在p,q∈Z使pa+qb=d.   有关最大公因子的计算方法: 
(1) 利用算术基本定理法: 取a与b的标准分解式中相同的素数的最低次幂作出的乘积就是d=(a,b).
(2) 辗转相除法: 先用辗转相除法求出d=(a,b)，再用回代法得到p,q；或可用大衍求一术公式编程等.
 最大公因子与最小公倍数的关系: (a,b)\=ab.
 素数与互素的性质: 
(1) (a,b)=1p,q∈Z:pa+qb=1.
(2) a|bc且(a,b)=1a|c.
(3) 设p为素数，则有p|abp|a或p|b.
(4) (a,b)=1且(a,c)=1(a,bc)=1.
(5) a|c, b|c且(a,b)=1ab|c.
 欧拉φ-函数: 设大于1的正整数n=pε11pε22…pεss，则小于n并与n互素的正整数的个数为: φ(n)=n1-1p1…1-1ps.并有性质: 当(m,n)=1时有φ(mn)=φ(m)φ(n).
3. 同余方程
 一次同余方程: ax≡b(mod m)(a≠0(mod m))有解的充分必要条件是(a,m)|b.且有解时通解为x≡pb1(mod m1) 或 x=pb1+km1,  k∈Z, 其中b1,m1的意义如下: a=a1(a,m),  b=b1(a,m),  m=m1(a,m), p满足: pa1+qm1=1.
因此一次同余方程ax≡b(mod m)(a≠0(mod m))的求解步骤为
(1) 求d=(a,m)，若d|b，则方程有解.
(2) 求a1,b1,m1: a1=a/d, b1=b/d, m1=m/d.
(3) 求p: pa1+qm1=1.
(4) 得通解为x≡pb1(mod m1)或x=pb1+lm1, l∈Z.
 一次同余方程组的求解方法--孙子定理.
由于一次同余方程组中每个同余方程必须有解，故每个同余方程可表示为解出形式，所以一次同余方程组可表示为以下形式: x≡b1(mod m1),
x≡b2(mod m2),
  
x≡bk(mod mk).(1.1)  定理(孙子定理) 设m1,m2,…,mk为k个两两互素的正整数，令M=m1m2…mk=m1M1=m2M2=…=mkMk,则同余方程组的一般解为x≡b1c1M1+b2c2M2+…+bkckMk(mod M),   (1.2)其中ci是满足同余方程Mix≡1(mod mi)的一个特解，i=1,2,…,k.
由此得求同余方程组的一般解的步骤为
(1) 求M=m1m2…mk, Mi=M/mi, i=1,2,…,k.
(2) 求同余方程Mix≡1(mod mi)的一个特解ci, i=1,2,…,k.
(3) 得同余方程组(1.1)的一般解为x≡b1c1M1+b2c2M2+…+bkckMk(mod M).   当k=2时，同余方程组为x≡b1(mod m1),
x≡b2(mod m2),                (1.3)(m1,m2)=1.若pm1+qm2=1，则方程组(1.3)的解为x≡b1qm2+b2pm1(mod m1m2).  (1.4)注意脚标对应关系的特点.公式(1.4)是公式(1.2)的特殊情况.
类似可研究二次同余方程x2≡a(mod n)的解的问题(以后将会学到).
二、 习题1.4详细解答
1.4-1 a=493, b=391，求(a,b), \和p,q使pa+qb=(a,b).
分析 可用两种方法来求最大公因子: 辗转相除法和大衍求一术.然后用公式(a,b)·\=ab求出\.
解 方法1 辗转相除法.列以下算式:  a=1×b+102, 
b=3×102+85, 
102=1×85+17, 
85=5×17.  由此得到  (a,b)=17,  \=ab17=11339.然后回代: 17=102-85=102-(b-3×102)=-b+4×102=-b+4(a-b)=4a-5b.所以得p=4, q=-5.   方法2 大衍求一术.
公式与计算表格如下: rk-2=qkrk-1+rk,  (带余除法)r-1=a,r0=b且a>b; 
ck=qkck-1+ck-2,  c-1=1,c0=0; 
dk=qkdk-1+dk-2,  d-1=0,d0=1.一直计算到rn≠0, rn+1=0，则d=(a,b)=rn, 
p=(-1)n-1cn,  q=(-1)ndn.
kqk
rk-2=qkrk-1+rkrkck
ck=qkck-1+ck-2dk
dk=qkdk-1+dk-2-1a=493100b=3910111102112385343(n)117454(n+1)50由此求得  n=3,d=(a,b)=17,
p=(-1)n-1cn=c3=4,  q=(-1)ndn=-d3=-5.  点评 两个方法比较: 辗转相除法比较直观，容易记忆，适合手算；大衍求一术公式比较复杂，不易记忆，但适合计算机编程.
1.4-2 求n=504的标准分解式和φ(n).
分析 求标准分解式的方法可用素数来除，由小到大进行: 2, 3, 5, ….
解 作以下计算: 

所以 504=23×32×7.φ(504)=504×1-121-131-17=144.  点评 只是简单地套公式，读者可以自己再举些例子算一算.
1.4-3 团体操表演过程中要求队伍变换成10行、15行、18行、24行时，均成长方形，问需要多少人？
分析 这是一个求最小公倍数的问题.
解 求最小公倍数: 作以下算式

得［10, 15, 18, 24］=5×2×3×3×4=360.所以需要 360k(k>0) 人.
点评 这是求数个整数的最小公倍数的问题，其手算方法如上.由于考虑到问题的实际意义，答案应取正整数.
1.4-4 方程 ax+by=c在整数范围内有解的充分必要条件是(a,b)|c.
分析 需要用到最大公因子的性质.
证 必要性: 设方程有解，则存在m,n∈Z满足am+bn=c，由于(a,b)|a, (a,b)|b, 故(a,b)|am+bn，所以(a,b)|c.
充分性: 设 d=(a,b), d|c. 由最大公因子定理，存在整数p, q 使 pa+qb=d.又由 d|c，可设 c=dh.可得pah+qbh=dh=c.所以 x=ph, y=qh 就是方程ax+by=c的一个解.
点评 证明必要性比较容易.证明充分性主要利用最大公因子定理.问题: 有解时是否还有其他的解？如有，求出所有的解.(答案可在本章的某处找到)
1.4-5 分别解同余方程: 
(1) 258x=131(mod 348); 
(2) 56x=88(mod 96).
分析 首先要判断方程是否有解，在有解的情况下，按照书中的步骤来解.
解 (1) 求(a,m)=(258,348)=6，由于6不能整除131，所以此同余方程无解.
(2) 求(a,m)=(56,96)=8，由于8能整除88，所以此同余方程有解.
按照解同余方程的四个步骤: 
① 求d=8; 
② 求a1=a/d=7, b1=b/d=11, m1=m/d=12; 
③ 用辗转相除法求p, q 使 pa1+qm1=1，得 p=-5; 
④ 所以方程的解为x≡pb1≡5(mod 12)，或x=5+12k(k为任意整数).
点评 该题的目的是熟悉同余方程的求解问题，虽然读者从中小学就开始解代数方程的问题，但较少遇到整数解的问题，更少遇到同余方程的问题，而这些概念和算法是学代数的基础，应熟练掌握.
1.4-6 解同余方程组: x≡3(mod 5), 
x≡7(mod 9).  分析 这是两个方程的同余方程组问题.可用公式(1.4).
解 首先我们应检验一下m1,m2是否互素.然后按公式(1.4)来做.
观察得到 2×5+(-1)×9=1,p=2,q=-1.所以此同余方程组的解为x≡b1qm2+b2pm1(mod m1m2)
 =3×(-1)×9+7×2×5(mod 45)
=43(mod 45).  点评 两个方程的同余方程组比较简单，公式比一般的孙子定理好记.
1.4-7 韩信点兵： 有兵一队，若列成5行，则多1，成6行，多5，成7行，多4，成11行,多10，求兵数.
分析 这是一个应用题，可用同余方程组来解.
解 设兵数为x，则x满足以下同余方程组: x≡1(mod 5),
x≡5(mod 6),
x≡4(mod 7),
x≡10(mod 11).  按解同余方程组的步骤，计算如下: M=5×6×7×11=2310,M1=462,M2=385,M3=330,M4=210.分别解以下一次同余式: 462x=1(mod 5),得c1=3.
385x=1(mod 6),得c2=1.
330x=1(mod 7),得c3=1.
210x=1(mod 11),得c4=1.代入同余方程组的解的公式，得x≡b1c1M1+b2c2M2+…+bkckMk(mod M), 
         =1×3×462+5×1×385+4×1×330
+10×1×210(mod 2310)
         =2111(mod 2310).由实际问题的意义，x应取正数，所以兵数为x=2111+2310k (k非负整数).  点评 一般来说孙子定理比较长，不一定记得住，遇到时会查就可.
第1章补充题第1章补充题
补充题1-1 证明n维欧氏空间中有且最多有n+1个互夹钝角的向量.
分析 这是线性代数的问题，一方面，因为线性代数是学习近世代数的重要基础；另一方面，通过这个题，引起对证明方法的重视，如何用简洁的语言严格证明理论问题.
    对于这个问题，首先可以从直观入手，先看一维的情况，显然有两个方向相反的向量，它们夹180. .再看二维的情况，显然也有3个互夹钝角的向量.对于三维的情况，我们只要把xy平面上的3个互夹钝角的向量的原点往z轴正方向拉一个很小的距离，则与z轴上的向量形成4个互夹钝角的向量，如此等等，所以该题可用归纳法来做，按上述方法构造出n+1互夹钝角的向量.
证 (1) 先证存在性: 对n作归纳法.n=1显然成立.
下设n>1，由归纳假设，Rn-1中有n个互夹钝角的向量，设为αi=(ai1,ai2,…,ain-1), i=1,2,…,n,  且 (αi,αj)<0,i≠j.在Rn中取向量: βi=(ai1,ai2,…,ain-1,b),  i=1,2,…,n, 
   βn+1=(0,0,…,0,-1).其中实数b满足条件:0<b<min1≤i<j≤n|(αi,αj)|.
则有(βi,βj)=(αi,αj)+b2<0, 1≤i<j≤n+1.所以β1,β2,…,βn+1是Rn中n个互夹钝角的向量.
(2) 再证最多有n+1个互夹钝角的向量.对n作归纳法.n=1显然成立.
设n>1，由归纳假设，Rn-1中最多有n个互夹钝角的向量.下面用反证法证明Rn中最多有n+1个互夹钝角的向量: 
假设Rn中有n+2个互夹钝角的向量: α1,α2,…,αn+2.
在αn+2的基础上取一组标准正交基: ε1,ε2,…,εn=αn+2|αn+2|.
则在这组标准正交基下，α1,α2,…,αn+2的坐标可表示为αi=(ai1,ai2,…,ain-1,ci),  i=1,2,…,n+1, 
       αn+2=(0,0,…,0,1).由于(αi,αj)<0,i≠j得ci<0, i=1,2,…,n+1，和∑n-1k=1aikaik<-cicj<0,  i≠j.令γi=(ai1,ai2,…,ain-1),  i=1,2,…,n+1.则(γi,γj)<0, 1≤i<j≤n+1, 得到Rn-1中有n+1个互夹钝角的向量，与归纳假设矛盾.证毕.
点评 证明第(1)部分--存在性时，可直接在Rn中构造n+1个互夹钝角的向量，例如令 α1=-1,1n,…,1n,
          α2=1n,-1,1n…,1n,
  
          αn=1n,…,1n,-1,
         αn+1=1n,1n,…,1n,则有(αi,αj)=-2n+n-2n2<0,  1≤i<j≤n, 
     (αi,αn+1)=-1n+n-1n2=-1n2<0,  i=1,2,…,n.所以它们互夹钝角.
该题的内容完全是复习线性代数，同时为了训练证明方法，证明方法是学习这门课的基础.在证明过程中要注意逻辑的严密，语言的简洁，表达的确切.
1.4-4的点评中所提问题的答案: 若ax+by=c在整数范围内有解，求所有的解.
解 由习题1.4-4，得到(a,b)|c.令d=(a,b), a=da1, b=db1.设x0,y0是ax+by=c的一组解，则有ax0+by0=c.设x,y是ax+by=c的任一组解，则有ax+by=c,两式相减，得a(x-x0)+b(y-y0)=0a1(x-x0)+b1(y-y0)=0
 b1|(x-x0),  a1|(y-y0), 可设x=x0+rb1, y=y0+sa1，代入原方程可得s=-r.所以ax+by=c得全部解为x=x0+rb1,
y=y0-ra1, r∈Z.  
补充题1-2 证明三维空间中只有5种正多面体.
分析 该题要用到欧拉多面体定理: 点数-边数+面数=2.
证 设正多面体的面数为n，每面为正m边形(m≥3)，每个顶点与k条边(或称棱)相接(k≥3).
(1) 我们来建立它们的关系.
由于每条边是2个面的边界，所以正多面体的边数为mn2.
又由于顶点数×k=2×边数，得顶点数为mnk.
由多面体欧拉定理: 顶点数-边数+面数=2得到方程: 
mnk-mn2+n=2, 
得
n=4k2k+2m-km.