? b (mod m)有解，其解数为dm1?d1mk ?1 = d?mk，mod m。由归纳原理知命题对于一切n ? 1成立。 3． 解同余方程f(x) = 3x2 ? 4x ? 15 ? 0 (mod 75)
因75 = 3?52，先解f(x) ? 0 (mod 3)，用逐一代入法得解x ? 0 (mod 3)；再解f(x) ? 0 (mod 52)，用逐一代入法得f(x) ? 0 (mod 5)的解为x ? 0，2 (mod 5)，对于x ? 0 (mod 5)，令x = 5t代入f(x) ? 0 (mod 25)得t ? 2 (mod 5)，于是x = 5(2 ? 5t2) = 10 ? 25t2，即x ? 10 (mod 25)是f(x) ? 0 (mod 25)的一个解，对于x ? 2 (mod 5)，令x = 2 ? 5t代入f(x) ? 0 (mod 25)得t ? 4 (mod 5)，于是x = 2 ? 5(4 ? 5t2) = 22 ? 25t2，即x ? 22 (mod 25)是f(x) ? 0 (mod 25)的一个解；最后构造同余方程组x ? b1 (mod 3)，x ? b2 (mod 25)，b1 = 0，b2 = 10，22，由孙子定理得f(x) ? 0 (mod 75)的两个解x ? 10，72 (mod 75)。 4． 4x20 ? 3x12 ? 2x7 ? 3x ? 2 ? 0 (mod 5)
原同余方程等价于2x4 ? 2x3 ? 3x ? 2 ? 0 (mod 5)，将x = 0，?1，?2 代入，知后者有解x ? ?1 (mod 5)。 5． 判定 2x3 ? x2 ? 3x ? 1 ? 0 (mod 5)是否有三个解
2x3 ? x2 ? 3x ? 1 ? 0 (mod 5)等价于x3 ? 3x2 ? 4x ? 3 ? 0 (mod 5)，又x5 ? x = (x3 ? 3x2 ? 4x ? 3)(x2 ? 3x ? 5) + (6x2 ? 12x ? 15)，其中r(x) = 6x2 ? 12x ? 15的系数不都是5的倍数，故原方程没有三个解； 6． 求出模23的所有的二次剩余和二次非剩余
模23的所有的二次剩余为x ? 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18 (mod 23)，二次非剩余为x ? 5, 7, 10, 11, 14, 15, 17, 19, 20, 21, 22 (mod 23)。 7． 设p是奇素数，证明：模p
p?1的所有二次剩余的乘积与(?1)2对模p同余
设x1, x2, ?, xk为模p的所有二次剩余，则
x1x2?xk ? 1222?
(mod p)。
8． 设p是奇素数，证明：模p的两个二次剩余的乘积是二次剩余；两个二次非剩余的乘积是二次剩余；一
个二次剩余和一个二次非剩余的乘积是二次非剩余。 设a，b为模p的二次剩余，有
? (?1)(?1) ? 1 (mod p)，以及 ? 1?(?1) ? 1 (mod p)知结论成立。
9． 设p，q是两个不同的奇素数，且p = q ? 4a，证明：(a)?(a) pq? 1?1 ? 1 (mod p)，再设c，d为模p的二次非剩余，有
由p = q ? 4a知p，q同为4k ? 1或同为4k ? 3，当p，q同为4k ? 1时，有
，当p，q同为4k ? 3时，有
。
10．
|b，b < 4ac，求(a，b，c是正整数，(a, b) = 1，2?a)与(a)的关系 4ac?bb，若a为偶数，于是4ac ? b与b同为8k ? 1
若a为奇数，有
6
或同为8k ? 3，即
，设a = 2?a1，a1为奇数，有
。
=
三、原根与指标
1． 求模14的全部原根
x ? 3，5 (mod 14)是模14的全部原根。
2． 设m > 1，模m有原根，d是?(m)的任一个正因数，证明：在模m的简化剩余系中，恰有?(d)个指数为d
的整数，并由此推出模m的简化剩余系中恰有?(?(m))个原根
因g1, g2, ?, g?(m)构成模m的简化剩余系，由d = ?m(g?) =
(?,?(m)) =
得
，则
，1 ? ? ? ?(m) ? (t, d) = 1，1 ? t ? d，
故恰有?(d)个t，使得(t, d) = 1，从而知故恰有?(d)个?，使得?m(g?) = d。特别地，取d = ?(m)知模m的简化剩余系中恰有?(?(m))个原根。
3． 设p = 2n ? 1是一个奇素数，证明：模p的全部二次非剩余就是模p的全部原根 在模p的简化剩余系中有又设g是模p原根，则
= 2n ?1个二次非剩余，在模p的简化剩余系中有?(?(p)) = ?(2n) = 2n ?1个原根，? ?1 (mod m)，即g是模p的二次非剩余。
4． 设m ? 3, g1、g2都是模m的原根, 则g = g1g2不是模m的原根
存在一个?，(?,?(m)) = 1，使得g2 ? g1? (mod m)，于是g1g2 ? g1? +1 (mod m)，
又由m ? 3知?(m)是偶数，?是奇数，? ? 1是偶数，(? ? 1,?(m)) ? 1，故g = g1g2不是模m的原根 |n时，有1n ? 2n ? … ? (p ? 1)n ? 0 (mod p) 5． 设p是奇素数，证明：当且仅当p ? 1?当p ? 1?n时，则1n ? 2n ? ? ? (p ? 1)n ? p ? 1 0 (mod p)，当p ? 1 n时，设g是p的一个原根，则1n ? 2n
? ? ? (p ? 1)n ? (1?g)n ? (2?g)n ? ? ? [(p ? 1)g]n ? [1n ? 2n ? ? ? (p ? 1)n]gn (mod p)，得[1n ? 2n ? ? ? (p ? 1)n](1 ? gn) ? 0 (mod p)，由(1 ? gn) 因为
d=(n, ?(m))=(8, ?(41))=(8, 40)=8, ind23=36
又36不能被8整除，所以同余方程无解。
四、扩域
定理1令E是F的一个扩域，而S1，S2是E的两个子集，那么
F(S1)(S2)=F(S1∪S2)= F(S2)(S1)
证明 F(S1)(S2)是一个包含F，S1，S2的E的子域，而F(S1∪S2)是包含F和S1∪S2的E的最小子域。因此
F(S1)(S2)?F(S1∪S2) (1)
另一方面，F(S1∪S2)是包含F，S1，S2的E的子域，因而是包含F(S1)和S2的E的子域。但F(S1)(S2) 是包含F(S1)和S2的E的最小子域。因此
0 (mod p)知1n ? 2n ? ? ? (p ? 1)n ? 0 (mod p)。
6． 求8次同余方程x8 ? 23 (mod 41)
F(S1)(S2)?F(S1∪S2) (2)
7
由(1)(2)得F(S1)(S2)=F(S1∪S2)。同样可以得到F(S1∪S2)= F(S2)(S1)。定理得证。
定理5 给定域F的一元多项式环F[x]的一个n次多项式f(x)，一定存在f(x)在F上的分裂域E。 证明 用归纳法：
当n=1时，E=F即可。假设n?m时结论也成立。
当n=m+1时，若f(x)在F[x]上可约，则存在次数小于m的多项式f1(x)和g1(x)使得f(x)= f1(x)g1(x)，由归纳假设知存在f1(x)在F上的分裂域E1，包含f1 (x)的所有根α1, α2, …, αn1。g1(x)视为F(α1, α2, …, αn1)上的次数小于n的多项式，故存在g1(x)在F(α1, α2, …, αn1)上的分裂域E，包含g1 (x)的所有根。从而E含有f(x)的所有根，是f(x)在F上的分裂域。若f(x)在F[x]上不可约，由定理3，存在F的单代数扩域K(K=F(θ))含有f(x)的一个根θ。于是在K[x]中f(x)=(x-θ)g(x)，再利用归纳假设，由于g(x)的次数为n-1，故存在g(x)在K上的分裂域E，包含g (x)的所有根，从而E也含有f(x)在F上的所有根，是f(x)在F上的分裂域。证毕。
定理6 设θ是F[x]中一个n次不可约多项式f(x)的一个根，则F(θ)是F上的有限扩域。
证明 因为F(θ)中每一元都可以表示成F上次数小于n的θ的多项式，故1，θ，θ2，…，θn，是F(θ)的一组生成元，又a0+a1θ+…+an-1θn-1 = 0可推出ai =0，所以F(θ)是F上的n维向量空间，有一组基为1，θ，θ2，…，θn-1，即F(θ) 是F上的一个有限扩域，并且(F(θ):F)=n。
关于有限扩域，有下列重要结论。
定理7 域F的有限扩域一定是F的代数扩域。
证明 设(E:F)=n，则存在一组基1，θ，θ2，…，θn-1，而n+1个向量1，θ，θ2，…，θn，从而线性相关。即存在n+1个不全为0的ai?F，使得a0+a1θ+…+anθn = 0。亦即θ满足F[x]中多项式。故E是F的一个代数扩域。
定理8 令K是域F的有限扩域，而E是域K的有限扩域，那么E也是域F的有限扩域，且(E:F)=(E:K)(K:F)。 证明 设(K:F)=r，(E:K)=s，而α1, α2, …, αr是向量空间K在域F上的一个基，β1, β2, …, βs是向量空间E在域K上的一个基。下面证rs个元构成向量空间E在域F上的一个基。
αiβj (i=1,2,…,r; j=1,2,…,s) (1)
显然，向量空间E中任意元素都可以表示rs个元系数为F上元的线性组合。下证(1)中元素在F上线性无关。若?aijαiβj?0 (aij?F)，那么?(?aijαi)βj?0 ?aijαi?K。
i,jjii由βj，0?j?s在K上的线性无关性可知 ?aijαi?0，(j=1,2,…,s)。
i由αi，0?i?r在F上的线性无关性可知aij=0，(i=1,2,…,r; j=1,2,…,s)。 也就是说，(1)的rs个元为E在F上的一组基。 六、有限域
定理1 一个有限域E有pn个元素，这里p是E的特征，而n是E在它的素域Δ上的次数。
证明 E为有限域，其特征一定为素数p。把E所含的素域记作Δ。因为E只含有限个元，所以它一定是Δ的一个有限扩域，(E：Δ)=n。这样，E的每个元可以唯一的写成a1α1+…+anαn的形式，这里ai?Δ，而α1，…，αn是向量空间E在Δ上的一个基。由于Δ只有p个元，所以对于每一个ai有p中选择法，因而E一共有pn个元。
定理2 令有限域E的特征为素数p，E所含的素域为Δ，而E有q=pn个元。那么E是多项式xq-x在Δ上的分裂域。任何两个这样的域都是同构的。
证明 E的不等于零的元对于乘法来说，做成一个群。这个群的的阶为q-1，单位元是1。所以
αq-1=1，α?E，α?0。
由于0q=0，所以有αq=α，α?E。因此用α1，…，αq来表示E的元，在E里多项式
qx?x??(x?αi)
i?1q 8
而且显然 E=Δ(α1，…，αq)。这样，E是多项式xq-x在Δ上的分裂域。
特征为p的素域都同构，而多项式xq-x在同构的域上的分裂域都同构。
定理3 令Δ是特征为p的素域，而q=pn (n?1)。那么多项式xq-x在Δ上的分裂域E是一个有q个元的有限域。
证明 E=Δ(α1，…，αq)，这里αi是f(x)= xq-x在域E里的根。由于E的特征是p，f(x)的导数f’(x)= pn xq-1-1= -1。所以f(x)与f’(x)互素。这样f(x)的q个根都不相同。f(x) 的q个根可以看成E的一个子域E1，这是因为
αnαpα(αi?αj)p?αip?αjp?αi?αj, (i)p?in?i(αi?0)
αjαjαjpnnnn这就是说，αi?αj和αi(αi?0)仍是αjf(x)的根而属于E1，因而E1是E的一个子域。但E1含Δ，也含一切αi，所
以E1就是多项式xq-x在Δ上的分裂域。这样E=E1，而E恰有q个元，得证。
以上证明了给定素数p和正整数n，有且只有(在同构意义下)一个恰好含pn个元的有限域存在。 有限域通常称作Galois域，有pn个元素的有限域通常记作GF(pn)。 定理4 (i) 有限域GF(pn)的子域是GF(pm)的形式，其中m|n。
(ii) 对n的任一因子m，有限域GF(pn)有且仅有一个子域GF(pm)。 定理4同上节定理6。这里我们来证明该定理。
证明 设T是有限域E= GF(pn)的子域，Δ是E的素域，由[E:T][T: Δ]= [E: Δ]=n可知[T: Δ]=m必整除n；T是元素个数为pm的有限域。这样T是xq-x (q=pm)在Δ上的分裂域。注意T是E的子域，故T={a?E|aq-a=0}。这样E中元素个数为pm的子域T有且仅有一个，由xq-x在E中的一切根组成。得证。
定理5 一个有限域E是它的素域Δ的一个单扩域。
证明 设E含有q个元。E的非零元对E的乘法来说作成一个交换群G，它的阶是q-1。令m是G的元的阶中最大的一个，那么由引理，aim=1，对于任意ai?G。这就是说，多项式xm-1至少有q-1个不同的根。因此m?q-1，但是由于m整除G的阶，故m ?q-1，所以m=q-1。也就是说G有一个元a，它的阶为q-1，因而G是一个循环群(a)。这样E是添加a于Δ所得的单扩域E=Δ(a)。定理得证。
定理5.3.6 域的乘群的任何有限子群是循环群。
证明：设G是域F的有限子乘群，令m是G中所有元素的阶的最小公倍数，由拉格朗日定理 G中任意元素的阶均为群G的阶的因子， 因而若设c为G中阶为m的元素，则 m?|G|。
另一方面，G中的元素均满足方程xm-l=0，而多项式f(x)=xm-l?F[x]在F上最多有m个不同的根， 故|G|?m，由此得|G|=m，所以G=(c)。
例6.2.7利用多项式f(x)=x2-2构造一个有限域，并找出这个域中的本原元。
解：这里只给出了构造域的多项式，并未给出构造域所需的欧氏环，因而需要选择一个欧氏环，并保证f(x)为此域中的不可约多项式。
注意到在F3中f(0)=1，f(1)=f(2)=2，因而 该多项式是F3[x]中的一个不可约多项式，
以此可以构造一个具有9个元素的有限域F。
域F中的元素都可以看做是二维向量(a,b)，其中a,b?F3={0,1,2}。
在域F中注意到x2≡2(mod x2-2)，因而可定义域F中的加法与乘法运算如下：
9
(a1,b1)+(a2,b2)=(a1+a2,b1+b2)。 (a1,b1)(a2,b2)=(a1b2+a2b1, b1b2+2a1a2) 接下来利用高斯算法寻找这个域中的本原元。
首先取α1=(1,0)=x，为了计算α1的阶，先来计算α1=(1,0)=x的各个幂次对f(x)取模的结果 x0≡1 (mod x2-2), x1≡x (mod x2-2), x2≡2 (mod x2-2) x3≡2x (mod x2-2)， x4≡2x2≡1(mod x2-2)，
以二维向量表示为 表6-3 α1=(1,0)=x各个幂次的向量表示
因而
α1=(1,0)=x的阶为4， 即在高斯算法中有t1=4。 由于t1≠q-1=8， 因而α1不是本原元， 接着转至第3步，需要选择 一个不是α1的幂次的元素β， 例如可以选 β=(1,2)=x+2，则
β2=(x+2)2≡x(modx2-2)=(1,0)， 类似地可以得到
β=(1,2)=x+2的各个幂次对f(x)取模的结果的向量表示 表6-4 β=(1,2)=x+2的各个幂次的向量表示
因而β的阶 s=8=q-1， 则令α2=β， 算法停止；
α2就是F中的本原元。
10