例1：设p=4n+3是素数，试证当q=2p+1也是素数时，梅素数Mp不是素数。 证：∵ q=8n+7,24n?3?2q?12?2????q???1(modq) ??∴ q|24n+3-1，即q |Mp，∴ Mp不是素数。

例2：若3是素数p平方剩余，问p是什么形式的素数？

?3?解：∵ 由反转定律??p???(?1)??p?12?p????， ?3?p?1(mod4) p??1(mod4)??1p??1注意到p>3，p只能为p??1(mod 3)且??????3??3???∴ ??p???1只能下列情况

?p?1(mod3) ?p?1(mod4)?d)?p??1(mo3 ?d)?p??1(mo4∴ p?1(mod12)或p??1(mod12)

例3：证明形如4m+1的素数有无穷多个。

证：假设形如4m+1的素数只有有限个，设为p1?pk，

显然(2p1?pk)2+1的最小素因数p是奇数，且p与p1?pk不同，

设p为4m+3形的素数，但p整除(2p1?pk)2+1，表明(2p1?pk)2+1≡0（mod p） 即x2

??1???1?≡(-1)(mod p)有解，即?，但????1?p??????p??(?1)p?12?(?1)2m?1??1矛盾，

∴p为4m+1形，这与4m+1的素数只有k个矛盾。

例4：证明不定方程x2+23y=17无解。 证：只要证x2≡17(mod 23)无解即可，

∵ 17≡1(mod 4)

17??23??6??2??3??3??17??2?∴ ?????????????????????????1

?23??17??17??17??17??17??3??3?∴ x2≡17(mod 23)无解，即原方程无解。

例5设x为整数，证明形如x2?1的整数的所有奇因数都有4h+1的形式，（其中h为整数） 证：设2n+1是整数x2?1的任一奇素因数，于是有 x2?1?0(mod2n?1),即x2??1(mod2n?1).

可以证明，这时x2?0(mod2n?1)，否则有1?0(mod2n?1)，这是不可能的。

因此，由2n?1是奇素数，便有(x,2n?1)?1。

2从而(x,2n?1)?1，这样由费马定理，有x2n?1(mod2n?1)。 但是x2n?(x2)n?(?1)n(mod2n?1),因此有(?1)n?1(mod2n?1).

由此可知，n必为偶数，记n=2h,便有2n+1=4h+1.这样便证明了整数x2?1的的所有奇素因数形式必为4h+1形式。又由于两个4h+1形式的数的乘积仍为4h+1形式的数，故x2?1形式的数的奇因数必为4h+1形式的数。

证2：由上面可知，-1是模2n+1的平方剩余，即???1???1. 2n?1??其中2n+1是奇素数。由定理3知2n?1?1(mod4)

从而 2n?0(mod4)，故n?0(mod2)，所以n是偶数，其余同上。

例6：证明：形如p?1(mod8)的素数有无穷多个。

证：设N是任意正整数，p1,p2,...,ps是不超过N的一切形如p?1(mod8)的素数。记

q?(2p1p2...ps)4?1。

显然q的任意素因数a异于2，且x?2p1p2...ps是同余式x4?1?0(moda)的解。 由a?1(mod8).又由于是pi(i?1,2,...,s)不是q的因数，

故a?pi(i?1,2,...,s)，从而a?N。因此形如p?1(mod8)的素数有无穷多个。

例7: 解如下二次同余式x2?11(mod125)

解： (1)125=53。先解x2?11?1(mod5)。它的一个解是x=1。

再解x2?11(mod52)。令x?1?5y，

则有(1?5y)2?11(mod52).化简得(1?10y)?11(mod52)，

得到y?1(mod5),从而有5y?5(mod52)，1?5y?6(mod52)， 所以x2?11(mod52)的一个解为x?6,最后解x2?11(mod53)。 设x?6?52z。代入有(6?52z)2?11(mod53)， 化简得12?52z??25(mod53). 即12z??1(mod5).

它的一个解是z?2.因此x?6?25?2?56是同余式x2?11(mod)125的一个解， 所以由定理，x2?11(mod)125的两个解是x?56(mod)125，x??56(mod)125.

例8：判断同余方程x2?286(mod443)是否有解。

解：286=2×143，433是素数，(143，443)=1

奇数143不是素数，但可用判定可比符号计算的生勒让德符号

?286??2??143?????????(?1)?443??243??443??(?1)143?184432?12?(?1)143?1443?1?22?443??14??2??7??????????? ?143??143??143??143??(?1)7?1143?1?22?143??? 7???3??1?????????1 ?7??3?∴原方程有解。

第六章 原根与指标

一、 主要内容

原根、指数的定义及基本性质、原根存在的条件、指标及n次乘余、模2及合数模指标组、特征函数

二、基本要求

理解原根，指数的定义，掌握指数的性质，原根存在的条件以及在一定条件下求已知模的原根。能判断怎样的数为模m的原根，用指数以及指标组能构造模m的简化乘余系。

三、重点和难点：

本章内容都比较抽象，具有一定的理论性。原根与指标是重点。

四、自学指导：

2

上章介绍了x2≡a(modm)的解数。本章主要以解决x≡a(modm)的解而引进原根，指数等概念。 指数是指使?at≡(modm)的最小的正整数d。一般记为?m(a)，上述条件是以(a,m)=1为先决条件。设

m>1， a≡b(mod m)，则δm(a)=δm(b)，对于指数可讨论若干问题，特别当δm(a)=φ(m)时称a为m的一个原根。若a 为m的一个原根，则m的一个简化系为a ,a ,??aααα12φ(m) 。不是任何整正数都有原根存在的，只有当m=2，4，p,2p时，原根存在。反之当m≠2,4, p， 2p时无原根存在。

ααα要弄清p和p的原根之间的关系，及p与2p的原根之间的关系。弄清当m在原根存在时，m的所有原

n

根表达方式s={g 1?n?φ(m)，(n, φ(m))=1}

指标是原根这一种另一个重要的概念，它有类似于对数函数的性质，另用指标可构造适当模m的简化剩余系。

α

五、例子选讲

例1：试10是模17的原根。

证：因?(17)=16，其正因子为d=2,4,8,且10d

∴ 10为模17的原根。

例2：解同余方程x12≡2(mod 31) 解：d=(12,30)=6, 查表ind2=24,

6|24，解且本题有6个解，

x12≡2(mod 31)?12indx=ind2(30) 即indx≡4(mod 5)

∴ indx≡2,7,12,17,22,27(mod 30) 查模31指标表，

∴ x≡9,17,8,22,14,23(mod 31)

1(mod 17),

例3: (1)若p和q=4p+1均为素数，则2是模q的一个原根。

(2)若p和q=6p+1均为奇素数，则3是模q的一个原根。 证 ：(1)由于p和q=4p+1均为素数，故p≠2，从而(2,q)=1。

根据费马定理有 2q?1?24p?1(modq)

因此要证明2是模q的一原根，只需证明

q?122?22p??1(modq)

即可。根据本章定理2，有

22p?q?122?2????q??(modq) ??而q是奇素数，必有p?1,3,5,7(mod8)之一，但不管那一种，

均有4p?4(mod8)，因此q?4p?1?5(mod8) 所以由定理，2是模q的非平方剩余，即??????1。 从而有22p??1(modq)。

故2关于模q的阶为4p=q-1，所以2是模q的一个原根。 (2)由于p和q=6p+1均为奇素数，故3q，从而(3,q)=1， 故由费马定理有

?2??q?3q?1?36p?1(modq)

为了证明3是模q的一个原根，只需证明

q?1233p?3??1(modq)即可

由定理有

33p?3q?12?3????q??(modq) ??由于p是奇素数，故p?1,3,5,7,11(mod12)之一， 不管那一种情况，均有6p?6(mod12)，所以 q?6p?1?7(mod12)。 所以3是模q的非平方剩余，即??????1， 所以33p?3??q???1(modq)

故3关于模q的阶为6p=q-1，所以3是模q的一个原根。