初等数论总复习题及知识点总结(7)

化简得12?52z??25(mod53). 即12z??1(mod5).

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

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

?11(mod)125的一个解，

?11(mod)125的两个解是x?56(mod)125，x??56(mod)125.

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

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

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

? 第六章 原根与指标

一、主要内容

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

二、基本要求

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

三、重点和难点：

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

四、自学指导：

31

上章介绍了x2≡a(modm)的解数。本章主要以解决x2≡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的一个简化系为a1 ,a2 ,??aφ(m) 。不是任何整正数都有原根存在的，只有当m=2，4，pα,2pα时，原根存在。反之当m≠2,4, pα， 2pα时无原根存在。

要弄清p和pα的原根之间的关系，及pα与2pα的原根之间的关系。弄清当m在原根存在时，m的所有原根表达方式s={gn 1?n?φ(m)，(n, φ(m))=1}

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

五、例子选讲

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

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

∴ 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)

32

例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，有

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

所以由定理，2是模q的非平方剩余，即???2?q????1。

??从而有22p??1(modq)。

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

故由费马定理有

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

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

q?133p?32??1(modq)即可

由定理有

q?133p?32????3??q???(modq) 由于p是奇素数，故p?1,3,5,7,11(mod12)之一， 不管那一种情况，均有6p?6(mod12)，所以

q?6p?1?7(mod12)。

33

所以3是模q的非平方剩余，即???3?q????1，

??所以33p??1(modq)

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

《初等数论》模拟试卷（A）

说明：考生应有将全部答案写在答题纸上，否则作无效处理

一、 填空（36分）

1、d（1000）= 。σ（1000）= 。φ（1000）= 。2、n?1， 若(n?1)!?1?0(modn)则n为 。

3、不能表示成5X+3Y（X、Y非负）的最大整数为 。 4、7在2003！中的最高幂指数是 。 5、（1515 ，600）= 。

6、ax?b(modm)有解的充要条件是 。 7、威尔逊定理是 。

8、写出6的一个简化系，要求每项都是5的倍数 。

9、0.32?化为分数是 。 10、22003的末位数是 。 11、[-2.3]= 。

12、φ（1）＋φ（P）＋?φ（Pn）= 。

13、x?1且能被4、5、7整除，则最小的x是 。 14、888??????88?666?????66?被7除后的余数为 。 505015、两个素数的和为31，则这两个素数是 。 16、带余除法定理是 。

34

二、 解同余方程组（12分）

??x?2(mod5)?x?3(mod8) ??x?1(mod7)

三、 叙述并且证明费尔马小定理。（12分）

四、 如果整系数的二次三项式p(x)?x2?bx?c当x?0,1p(x)?0没有整数根（6分）

五、 设Ｐ为奇素数，则有（8分） （1）1p?1?2p?1???(p?1)p?1??1(modp) （2）1p?2p???(p?1)p?0(modp) 六、 证明：对任何正整数ｋ，ｍ，ｎ

有１１|55k?2?45m?4?35n?3 （6分）

七、证明：3是无理数。（8分）

八、试证：对任何的正整数n,n2?2不能被4整除。（6分） 九、解不定方程4x?5y?10 （6分）

《初等数论》模拟试卷（A）答案 一、

1、16，2340，9360 2、素数 3、7 4、331 5、15 6、(a,m)|b

7、(p?1)!?1?0(modp) 8、5，25

的值都是奇数，证明35

时

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库初等数论总复习题及知识点总结(7)在线全文阅读。