第1章 整数与多项式
整数(integer)历史悠久，一直以来都是数学研究的主要对象之一.公元前6世纪，毕达哥拉斯就已研究过整数的可除性问题.公元前3~4世纪，欧几里得证明了有无穷多个素数，给出了求两个正整数的*大公因数的算法，建立了整数可除性的初步理论.我国古代许多著名的数学著作都有关于整数内容的论述.例如，《九章算术》的“方程”一章中正式引入负数及其加减运算法则，这在世界数学史上是*早的.
多项式(polynomial)源于代数方程的研究，在古巴比伦时代(约公元前1894—公元前1595)，人们已经知道如何求解一元二次方程.公元12世纪，出生于巴格达一个犹太家庭的萨玛瓦尔.在他的著作《耀眼的代数》(Al-Bahir Fi’l-jabr)中已经给出了多项式的带余除法.1545年，卡尔达诺.在《重要的艺术》(Ars Magna)一书中给出了一元三次方程和一元四次方程的求根公式.19世纪上半叶阿贝尔.和伽罗瓦.分别证明了五次及五次以上一般形式的多项式方程没有求根公式.高斯.于1799年证明了一般复系数多项式方程在复数域中有根.多项式是高等代数的基本研究对象之一，它对于进一步学习代数以及其他数学分支有重要的作用.
本章首先介绍整数的算术性质和同余，然后研究一般数域上的多项式理论.
1.1 整数的算术性质
整数包括正整数、零和负整数.自然数(natural number)包括正整数和零.通常用N表示自然数集，正整数集记为而整数集用Z表示.为什么用Z表示整数集呢?这归功于杰出数学家埃米 诺特.她是德国人，德语中的数叫做Zahlen，她于1921年首次使用Z表示整数环(整数集本身是一个数环)，从此整数集就用Z表示了为后文需要，我们先介绍数学归纳法.数学归纳法是数学证明的一种重要方法，它主要用来证明与自然数有关的命题的正确性.与自然数有关的命题有很多，例如
(1);
(2);
(3);
(4)边凸多边形内角之和是，其中;
(5);
(6).
要证明它们的正确性，我们不能对每个n一一去验证，也不能只验证前100，1000，甚至前10000个n的值.我们需要用一种严格的数学推理来证明.这种严格的数学推理就是数学归纳法(mathematical induction).
已知*早使用数学归纳法的证明出现于16世纪，据说意大利一位数学家(伽利略的老师)于1575年用归纳法证明了前n个奇数之和是n2，由此揭开了数学归纳法之谜，直到19世纪，德 摩根才首次提出了“数学归纳法”的概念.这里我们主要介绍数学归纳法的两种等价形式以及与它们等价的良序原理.
定理1.1.1 (第一归纳法(first form of induction))设Pn是一个与自然数有关的命题，其中是某一固定的整数.若
(1)当n=n0时，Pn0成立，
(2)对任意整数，由Pk成立可以推出Pk+1成立，则对任意整数成立.
定理1.1.2 (第二归纳法(second form of induction))设Pn是一个与自然数有关的命题，其中是某一固定的整数.若
(1)当时，成立，
(2)对任意整数，由都成立可以推出Pm+1成立，
则对任意整数成立.
定理1.1.3 (良序原理(well-ordering principle))设 n0是某一固定的整数，且，则 S 中任一非空子集都有*小数.特别地，自然数集的任一非空子集都有*小数.
定理1.1.4 (整数的带余除法(division algorithm for integers))设且n6=0，则存在**一对使得，其中.通常称q为m除以n的商(quotient)，而称r为m除以n的余数(remainder).
证明 因为n6=0，不妨假设n>0(否则考虑).先证存在性.
首先，我们给一个直观的证明.用n的倍数将数轴划分为长度为n的区间，则m必在某个分点上或在某两个分点之间，如下图.
因此，存在使得.令，则，其中.
下面我们用良序原理证明.考虑集合.
(1)此时存在整数k使得，则.
(2)此时m6=0(若，则，矛盾).
若m>0，则.若m<0，则.
由此可见，S是自然数集合的非空子集.由良序原理知，S中有一个*小数r，即存在整数q使得，从而.
若，则，并且.因此，是S中小于r的数，与r是S中的*小数矛盾!故，其中.
下证**性.
若，其中，且，则.若，则.不妨设，则.但是，矛盾!所以.**性得证.
定义1.1.5 设.
(1)若存在k2Z使得m=kn，则称n整除(divide) m，此时， n称为m的因数(divisor 或 factor)， m称为n的倍数(multiple).当n整除m时，记作，否则，记作.
(2)若既是m的因数，又是n的因数，则称d是m与n的公因数(common divisor).若d是m与n的公因数，并且m与n的任一公因数都是d的因数，则称d是m与n的*大公因数(greatest common divisor).
(3)若既是m的倍数，又是n的倍数，则称l是m与n的公倍数(commonmultiple).若l是m与n的公倍数，并且m与n的任一公倍数都是l的倍数，则称l是m与n的*小公倍数(least common multiple).
注记1.1.6 由上述定义可知
(1)在的定义中，n可以为零，此时m=0;若n6=0，则当且仅当m除以n的余数为0.
(2)任意整数整除0;任意整数整除它自身; 1整除任意整数.
(3)若，则;若，则;若，则对任意整数s，t都有.
(4)若d1，d2都是m与n的*大公因数，则d1= d2.若mjn，则m是m与n的*大公因数.特别地，m是m与0的*大公因数.当然，0是0与0的*大公因数.当m，n不全为零时，m与n的*大公因数不为零，此时常用(m，n)表示m与n的正的*大公因数.
(5)两个整数的*小公倍数在相差一个正负号的意义下是**的.若m，n中有一个为0，则0是m与n的**公倍数，因此，由定义可知，0就是它们的*小公倍数.对于全不为零的两个整数m与n，常用[m，n]表示它们的正的*小公倍数.
(6)对于任意k个整数，可以类似于两个整数的情形定义它们的*大公因数和*小公倍数.以后常用和，分别表示的正的*大公因数和正的*小公倍数.
例1.1.7 设整数m，n不全为零.如果存在整数q，r使得，证明:(m，n)=(n，r).
证明因为并且，所以.于是，由*大公因数的定义知.同理.故(m，n)=(n，r).
定理1.1.8 设，则m，n的*大公因数d存在且**(不计符号的意义下)，并且d可表示为m与n的组合，即存在使得
证明由定义可知，两个整数的*大公因数在相差一个正负号的情况下是**的.下面证明存在性.
若，则n是m与n的*大公因数，并且.若，此时，不妨设n>0.由带余除法得
(1.1.1)
注意，由于逐渐递减，所以存在正整数 s 使得但.于是，根据例1.1.7.由(1.1.1)式知.如此继续下去，逐个消去，得到整数使得.
上述定理中用来求*大公因数的方法通常称为辗转相除法或欧几里得算法(Euclidean algorithm).
定义1.1.9 设.若(m，n)=1，则称m与n互素(relatively prime 或coprime).设，其中.若，则称互素.如果当时，mi与mj互素，那么称m1，m2， ，mt两两互素(pairwise coprime).
下面的命题给出了整数互素的一些性质.
命题1.1.10 设m，n，k都是整数.
(1)m与n互素当且仅当m与n仅以1为公因数.
(2)m与n互素当且仅当存在整数u，v使得um+vn=1.
(3)若m，n不全为零，则.
(4)若，且(m，n)=1，则.
(5)若m，n为正整数，则.
(6)若，则，特别地，若(m，n)=1，则.
(7)若(m，k)=1，(n，k)=1，则.
证明 (1)由定义即知.
(2)必要性由定理1.1.8即知.
充分性设d是m与n的公因数，则dj1.由此可见，m与n仅以 1为公因数，故m与n互素.
(3)由定理1.1.8知，存在使得.注意(m，n)6=0，所以，从而由(2)知.
(4)因为(m，n)=1，所以存在整数u，v使得，从而.由于，故.
(5)设，则由(3)知.令，则，因此，l是m与n的公倍数.若k是m与n的任一公倍数，则存在使得，从而，即.由于(m1，n1)=1，所以由(4)知.于是存在使得，从而，即k是l的倍数.故.
(6)由*小公倍数的定义以及(5)即得.
(7)因为，所以存在使得.于是，即.故由(2)知.
推论1.1.11 设k，n，mi都是整数.
(1)若，则.
(2)若，则，特别地，若m1，m2， ，mt两两互素，则.
定义1.1.12 设p为整数，并且.若p的全部因数为，则称p为素数(primenumber).通常约定素数是正的.
设p>1.易见，p是素数当且仅当p不能分解为两个小于p的正整数之积.
定理1.1.13 设整数p>1，则下列陈述等价:
(1)p是素数;
(2)对任意整数m，总有或(p，m)=1;
(3)对任意两个整数m，n，如果，那么或.
证明 (1)=)(2)任取一个整数m，令(m，p)=d，则djp.因为p是素数，所以d=1或d=p.由此可见，或(p，m)=1.
(2)设m，n是任意两个整数，并且.若，则由条件(2)知，(p，m)=1.由命题1.1.10(4)知.
(3)(1)若p不是素数，则存在整数p1，p2使得，并且1<p1，p2<p.显然，但是，与条件(3)矛盾.故p是素数.
推论1.1.14 设.若p是素数，并且，则存在，使得.
定理1.1.15 (算术基本定理(fundamental theorem of arithmetic))任意
