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

第四章原根和指数;第一节原根;一、整数的阶;一、整数的阶;一、整数的阶;一、整数的阶;一、整数的阶;定理设整数a与正整数n相对互素，那么正整数x是同余式ax≡1(modn)的解当且仅当ordna|x。

证明：给定正整数x，假设ordna|x，那么由于此时存在正整数k，使得x=k?ordna，因而

即此时正整数x是同余式ax≡1(modn)的解。

反之，假设正整数x是同余式ax≡1(modn)的解，那么由算术根本定理会存在整数q，r，使得

x=q?ordna+r，0≤rordna。

因而

ax=≡ar(modn)。;证明：ax=≡ar(modn)。

由于ax≡1(modn)，因而

ar≡1(modn)。

但是ordna是使得ax≡1(modn)成立的最小正整数，现在竟然有整数r，0≤rordna，也使得同余式ax≡1(modn)成立，因而

r=0，即x=q?ordna，故此时ordna|x。

例确定x=137与x=120是否为同余式2x≡1(mod11)的解。

解：由例，有ord112=10，由于10?137且3|120，因而

x=137不是同余式2x≡1(mod11)的解，

而x=120是同余式2x≡1(mod11)的解。;一、整数的阶;一、整数的阶;一、整数的阶;二、原根的定义和性质;二、原根的定义和性质;二、原根的定义和性质;二、原根的定义和性质;二、原根的定义和性质;二、原根的定义和性质;三、原根的存在性;三、原根的存在性;3.1、素数的原根的存在性;3.1、素数的原根的存在性;3.1、素数的原根的存在性;3.1、素数的原根的存在性;3.1、素数的原根的存在性;3.1、素数的原根的存在性;3.1、素数的原根的存在性;引理设p是素数，d|(p-1)，那么模p的d阶整数中小于p的整数的个数不超过φ(d)。

证明：对p-1的每一个因子d，令F(d)为模p的d阶整数中小于p的正整数的个数。

假设F(d)=0，那么

F(d)?φ(d)，

否那么必存在

一个模p的d阶整数a。

由于ordna=d，整数a,a2,…,ad是模p不同余的。而对每个正整数k有

(ak)d=(ad)k≡1(modp)，因而

a,a2,…,ad都是xd-1对p取模的根。;引理设p是素数，d|(p-1)，那么模p的d阶整数中小于p的整数的个数不超过φ(d)。

证明：a,a2,…,ad都是xd-1对p取模的根。

又xd-1恰有d个模p不同余的根，因而

模p的每一个根都与a,a2,…,ad中的一个同余。

然而，假设a的一个幂次ak具有阶数d，那么一定有

(k,d)=1。

一共有φ(d)个满???此条件的整数k，1≤k≤d，因而假设存在一个模p的d阶元素，那么必定恰有

φ(d)个这样的小于d的整数，因而

F(d)?φ(d)。;定理设p是素数，d|(p-1)，那么模p的d阶不同余的整数的个数为φ(d)。

证明：对p-1的每一个因子d，令F(d)为模p的d阶整数中小于p的正整数的个数。由于一个与p互素的整数模p的阶整除p-1，因而

因而当d|(p-1)时，有F(d)≤φ(d)，结合

得到对p-1的每一个因子d，有

F(d)=φ(d)。

因而，F(d)=φ(d)，即恰有φ(d)个d阶模p不同余的。;推论每个素数都有原根。

证明：设p是素数，那么由定理知

有φ(p-1)个p-1阶模p不同余的整数，

而由原根的定义，

它们当中的每一个都是原根，因而

p有φ(p-1)个原根。;定理设奇素数p有原根r，那么r或r+p是模p2的原根。

证明：由于r是模p的原根，因而

ordpr=φ(p)=p-1。

设，那么

rn≡1(modp2)，

即存在整数k，使得rn-kp2=1，也即对模p2成立的同余式对模p也是成立的，因而

rn≡1(modp)，又p-1=ordpr，因而p-1|n。

另一方面，由于|φ(p2)，即n|φ(p2)，且φ(p2)=p(p-1)，因而

n|p(p-1)。;由n|p(p-1)以及(p-1)|n，得到n=p-1或者n=p(p-1)。

假设n=p(p-1)，那么=φ(p2)，即

r是模p2的原根，

假设n=p-1，那么rp-1≡1(modp2)。设s=r+p，那么

s≡r(modp)，

由于ordpr=p-1，因而ordps=p-1，即

s也是模p的原根。因而

等于p-1或者p(p