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

初等数论总复习题及知识点总结最后，给大家提一点数论的学习方法，即一定不能忽略习题的作用，通过做习题来理解数论的方法和技巧，华罗庚教授曾经说过如果学习数论时只注意到它的内容而忽略习题的作用，则相当于只身来到宝库而空手返回而异。

数论有丰富的知识和悠久的历史，作为数论的学习者，应该懂得一点数论的常识，为此在辅导材料的最后给大家介绍数论中著名的“哥德巴赫猜想”和费马大定理的阅读材料。

初等数论自学安排第一章：整数的可除性（6学时）自学18学时整除的定义、带余数除法最大公因数和辗转相除法整除的进一步性质和最小公倍数素数、算术基本定理[x]和{x}的性质及其在数论中的应用习题要求：2，3 ；：4 ；：1；：1，2，5；：1。

第二章：不定方程（4学时）自学12学时二元一次不定方程多元一次不定方程勾股数费尔马大定理。

习题要求：1，2，4；：2，3。

第三章：同余（4学时）自学12学时同余的定义、性质剩余类和完全剩余系欧拉函数、简化剩余系欧拉定理、费尔马小定理及在循环小数中的应用习题要求：2，6；：1；：2，3；1，2。

第四章：同余式（方程）（4学时）自学12学时同余方程概念孙子定理高次同余方程的解数和解法素数模的同余方程威尔逊定理。

习题要求：1；：1，2；：1，2。

第五章：二次同余式和平方剩余（4学时）自学12学时二次同余式单素数的平方剩余与平方非剩余勒让德符号二次互反律雅可比符号、素数模同余方程的解法习题要求：2；：1，2，3；：1，2；：2；：1。

第一章：原根与指标（2学时）自学8学时指数的定义及基本性质原根存在的条件指标及n次乘余模2及合数模指标组、特征函数习题要求：3。

第一章整除一、主要内容整除的定义、带余除法定理、余数、最大公因数、最小公倍数、辗转相除法、互素、两两互素、素数、合数、算术基本定理、Eratosthesen筛法、[x]和{x}的性质、n！的标准分解式。

二、基本要求通过本章的学习，能了解引进整除概念的意义，熟练掌握整除整除的定义以及它的基本性质，并能应用这些性质，了解解决整除问题的若干方法，熟练掌握本章中二个著名的定理：带余除法定理和算术基本定理。

《初等数论》总结姓名 xxx学号 xxxxxxxx院系 xxxxxxxxxxxxxxx专业 xxxxxxxxxxxxxxx个人感想初等数论是一门古老的学科，它对于数的性质以及方程整数的解做了深入的研究，是对中等数学数的理论的继续和提高。

有时候上课听老师讲解一些例题，觉得比较简单，结果便是懂非懂地草草了之，但是过段时间做老师留下的一些相似的课后练习时，又毫无头绪，无从下手。

这就是上课的时候没做到全神贯注地去听，所以课下的时间尤为重要，一定做好复习巩固的工作。

老师讲课的方法也十分好，每次上课都会花二十分钟到半个小时来对上节课的知识帮助我们进行回顾，我想很多同学都喜欢并适合这种教学方式。

知识点总结第一章 整数的可除性1. 定义：设b a ,是给定的数，0≠b ，若存在整数c ，使得bc a =则称b 整除a ，记作a b |，并称b 是a 的一个约数，称a 是b 的一个倍数，如果不存在上述c ，则称b 不能整除a 2性质：(1)若c b |且a c |，则a b |(传递性质)；(2)若a b |且c b |，则)(|c a b ±即为某一整数倍数的整数之集关于加、减运算封闭。

若反复运用这一性质，易知a b |及c b |，则对于任意的整数v u ,有)(|cv au b ±。

更一般，若n a a a ,,,21L 都是b 的倍数，则)(|21n a a a b +++L 。

或着i b a |，则∑=ni i i b c a 1|其中n i Z c i ,,2,1,L =∈；(3)若a b |，则或者0=a ，或者||||b a ≥，因此若a b |且b a |，则b a ±=；(4)b a ,互质，若c b c a |,|，则c ab |；(5)p 是质数，若n a a a p L 21|，则p 能整除n a a a ,,,21L 中的某一个；特别地，若p 是质数，若n a p |，则a p |；(6)(带余数除法)设b a ,为整数，0>b ，则存在整数q 和r ，使得r bq a +=，其中b r <≤0，并且q 和r 由上述条件唯一确定；整数q 被称为a 被b 除得的(不完全)商，数r 称为a 被b 除得的余数。

初等数论知识点整理 1. 整数的基本性质：
- 整数的定义与整数集的基本运算
- 整数的大小与比较
- 整数的不同表示形式（十进制、二进制、八进制等） 2. 整除与约数：
- 整除的定义与性质
- 素数的定义与判定方法
- 约数的定义与性质
- 最大公约数与最小公倍数的概念与计算方法
3. 同余与模运算：
- 同余的定义与性质
- 同余的基本运算性质
- 模运算的基本性质
- 剩余类和完全剩余系的概念与性质
4. 质数与素数：
- 质数与素数的定义
- 质数与素数的性质和特性
- 素数的测试方法与算法
- 质因数分解的方法与应用
5. 数论基本定理：
- 唯一分解定理（素因数分解定理）
- 辗转相除法与欧几里得算法
- 欧拉函数与欧拉定理
- 费马小定理与扩展欧几里得算法
6. 数论问题的应用：
- 同余方程与线性同余方程
- 不定方程的整数解与应用
- 素数分布与素数定理
- 模重复性与周期性问题
注意：本整理的所有内容仅供参考，请勿将其作为官方教材或其他正式场合使用。

《初等数论》（2019级小教）总复习题1、进位制的互化：（1）(20 011)3=( )10；（2）(31 404)5=( )10；（3）(7 137)10=( )2；（4）(21 58)10=( )8；（5）(1376)8=( )5；（6）2000=（ ）3=（ ）7=（ ）9=（ ）12；（7）（12301）5=（ ）7 .2、已知(ab)9=(ba)7，求a,b.3、（1）以2为基，求13，15，19的小数展开式； （2）以12为基，求113，114的小数展开式. 4、如果(52)k 是(25)k 的两倍，那么(123)k 在十进位制中表示多少？5、某正整数除以3余2，除以4余1，则此数除以12余数为?6、计算：（1）（110）2+（1011）2；（10101）2-（111）2； （10101）2×（101）2；（1101001）2÷（1010）2.（2）（2517）8+（3124）8；（15721）8-（452）8； （301）8×（125）8；（212）÷（27）8.7、若962427ab 且1162427ab ，求a,b.8、四位数7a2b̅̅̅̅̅̅̅能同时被2，3，5整除，求a,b.̅̅̅̅̅̅̅̅̅̅,求a,b.9、已知99|81ab93̅̅̅̅̅̅̅̅̅̅̅̅,求a,b.10、已知24|62742ab11、三个相邻偶数之积是四位数，且其末位数为8，求这个三位数。

12、若1176a=b4（a,b为正整数），求a的最小值。

13、975*935*972*( ) ,要使这个乘积的最后四个数都是零，则（）内最小应填几？14、写出下列各数的标准分解式.193975，26840，111111，999 999 999 99915、某数除300，262，205余数相同，则此数最大值为 .16、某数除701，1059，1417，2312余数相同，则此数最大值为多少.17、720的所有正约数的倒数之和为。

福师期末考试《初等数论》复习题及参考答案复习题及参考答案一一、填空(40%)１ 、求所有正约数的和等于15的最小正数为 考核知识点:约数，参见P1４—1９ 2、若1211,,,b b b 是模１1的一个完全剩余系，则121181,81,,81b b b +++也是模１１的剩余系．考核知识点：完全剩余系，参见P54—573.模13的互素剩余系为考核知识点：互素剩余系,参见P5８4.自１７６到545的整数中是1３倍数的整数个数为 考核知识点:倍数，参见Ｐ11-13 5、如果p 是素数,a 是任意一个整数，则a 被p 整除或者考核知识点：整除，参见Ｐ1-４６、b a ,的公倍数是它们最小公倍数的 . 考核知识点：最小公倍数,参见P1１—13７、如果b a ,是两个正整数，则存在 整数rq ,,使r bq a +=,b r ≤0．考核知识点:整除，参见P1-４ 8、如果n 3，n 5,则１5( ）n ． 考核知识点：整除,参见P1-4二、（１０％)试证：6|n(ｎ+1）(2n+1），这里n 是任意整数。

考核知识点：整除的性质，参见P ９-１２ 提示：ｉ)若 则ｉi ）若 则ii ｉ）若 则又三、(１0％）假定a 是任意整数，求证a a (mod )++≡2103或a a (mod )+≡203考核知识点:二次同余式,参见P88提示：要证明原式成立,只须证明231a a ++,或者23a a +成立即可。

四、(1０％）设p 是不小于5的素数，试证明21(mod 24)p ≡ 考核知识点:同余的性质,参见P4８－52 提示:且是不小于５的素数．ﻫ又 且是不小于5的素数．只能是奇数且ﻫﻫ 即即五、(1５％）解同余式组51(mod7)142(mod8)x x ≡⎧⎨≡⎩考核知识点:同余式，参见P74-７5 提示∵ （14，8)=2 且 ２ ｜ 2 ∴ 1４ｘ≡2（ｍod8） 有且仅有二个解解7x ≡1（mod ４) ⇒ ｘ≡３ （m ｏｄ4） ∴ ６x ≡１0(mod ８）的解为 x ≡3，3+4(mo ｄ8） 原同余式组等价于()()3mod 73mod8x x ≡⎧⎪⎨≡⎪⎩ 或()()3mod 77mod8x x ≡⎧⎪⎨≡⎪⎩分别解出两个解即可。

初等数论学习总结本课程只介绍初等数论得得基本内容。

由于初等数论得基本知识与技巧与中学数学有着密切得关系， 因此初等数论对于中学得数学教师与数学系(特别就是师范院校)得本科生来说，就是一门有着重要意义得课程，在可能情况下学习数论得一些基础内容就是有益得．一方面通过这些内容可加深对数得性质得了解，更深入地理解某些她邻近学科，另一方面，也许更重要得就是可以加强她们得数学训练，这些训练在很多方面都就是有益得．正因为如此，许多高等院校，特别就是高等师范院校，都开设了数论课程。

最后，给大家提一点数论得学习方法，即一定不能忽略习题得作用，通过做习题来理解数论得方法与技巧，华罗庚教授曾经说过如果学习数论时只注意到它得内容而忽略习题得作用，则相当于只身来到宝库而空手返回而异。

数论有丰富得知识与悠久得历史，作为数论得学习者，应该懂得一点数论得常识，为此在辅导材料得最后给大家介绍数论中著名得“哥德巴赫猜想”与费马大定理得阅读材料。

初等数论自学安排第一章：整数得可除性（6学时）自学18学时整除得定义、带余数除法最大公因数与辗转相除法整除得进一步性质与最小公倍数素数、算术基本定理[x]与{x}得性质及其在数论中得应用习题要求3p ：2，3 ； 8p ：4 ；12p ：1；17p ：1，2，5；20p ：1。

第二章：不定方程（4学时）自学12学时二元一次不定方程c by ax =+多元一次不定方程c x a x a x a n n =++Λ2211勾股数费尔马大定理。

习题要求29p ：1，2，4；31p ：2，3。

第三章：同余（4学时）自学12学时同余得定义、性质剩余类与完全剩余系欧拉函数、简化剩余系欧拉定理、费尔马小定理及在循环小数中得应用习题要求43p ：2，6；46p ：1；49p ：2，3；53p 1，2。

第四章：同余式（方程）（4学时）自学12学时同余方程概念孙子定理高次同余方程得解数与解法素数模得同余方程威尔逊定理。

第一章考点1、会求最大公因数与最小公倍数解法：最大公因数用辗转相除法最小公倍数为两个数的乘积除以两者的最大公约数，所以也是要先求出两者的最大公约数2、判别一个数是为质数还是合数判别法：用小于√x的所有质数除此数，看能否被整除3、证明整除（最好用同余证）例1证：73|8n+2+92n+1（n∈N）解：法一 8n+2+92n+1=64×8n+9×81n=64×8n+9×（73+8）n=64×8n+9×（C0n73n+C1n73n-1×8+…+C n n8n）=64×8n+9(73q+8n)( q∈Z)=73×8n+9q×73所以73|8n+2+92n+1法二 8n+2+92n+1≡64×8n+9×81n≡64×8n+9×8n≡73×8n≡0（mod73）所以73|8n+2+92n+1例2已知17|2x+3y,证明17|9x+5y解：因为9x+5y=17（x+y）- 4(2x+3y) 且17|2x+3y所以17|9x+5y例3设k为正奇数，证：1+2+3+....+9|1k+2k+3k+ (9)证：记S=1k+2k+3k+ (9)则2S=（1k+9k）+（2k+8k）+…+（9k+1k）=（1+9）q1 （q1∈Z)所以10|2S又因为2S=（0k+9k）+（1k+8k）+…+(9k+0k)=（0+9）q2（q2∈Z）所以9|2S又因为（9,10）=1所以90|2S 即45|S从而1+2+3+....+9|1k+2k+3k+ (9)4、证明某种类型的质数有无穷多个例：证明4n+1形的质数的个数为无穷。

（最后一节课讲的）第三章同余考点：1、同余的性质；（应用在同余解题中）P482、简化剩余系和欧拉函数；（求简化剩余系的个数）P583、欧拉定理和费马定理对循环小数的应用；（利用欧拉定理解题；判断是纯循环还是混循环，若是混循环，从第几位开始）P61具体分析：一、同余的性质1、a≡a (mod m)2、若a≡b (mod m),则b≡a (mod m)3、若a≡b (mod m) b≡c (mod m) 则 a≡c (mod m)4、i.若a1≡b1 (mod m) a2≡b2 (mod m) 则 a1+a2≡b1+b2 (mod m)ii. a+b≡c (mod m) 则 a≡c-b (mod m)5、a1≡b1 (mod m) a2≡b2 (mod m) 则 a1a2≡b1b2 (mod m)特别的，若a≡b (mod m) 则 ak≡bk (mod m)6、若a≡b (mod m) 且a=a1d b=b1d (d,m)=1 则 a1≡b1 (modm)7、i.若a≡b (mod m) k>0 则 ak≡bk （mod mk）ii.若a≡b (mod m) d为a,b及m的任一正公因数，则a/d≡b/d (mod m/d)8、若a≡b (mod m) i=1、2…k 则a≡b(mod m1m2…m k)例：一个小于4000的四位数，被3、4、5、7、9除皆余2，求这个数。

初等数论陈培东 2014.7一、基础知识 1．整除问题（1）整除的部分性质：①若c | b ，b | a ，则c | a ②若c | a ，d | b ，则cd | ab ③若c | a ，c | b ，则c |（ka ＋nb ）；若c | a ，c |﹨b ，则c |﹨（a ＋b ） ④若ma | mb ，则a | b ⑤若a ＞0，b ＞0，b | a ，则b ≢a ⑥任意n 个连续正整数的乘积必能被n ！整除。

当（a ，b ）＝1时，称a 、b 互素（互质）。

有：①已知（a ，c ）＝1，若a | bc ，则a | b ；若a | b ，c | b ，则ac | b ②p 为素数，若p | ab ，则p | a 或p | b ③[a ，b]·（a ，b ）＝ab ④（a ，b ）＝（a ，b －ac ）＝（a －bc ，b ）对任何整数c 成立 ⑤存在整数x 、y ，使ax ＋by ＝（a ，b ）（裴蜀定理）⑥m （a ，b ）＝（ma ，mb ） ⑦若（a ，b ）＝d ，则（a d ，bd ）＝1⑧若a | m ，b | m ，则[a ，b] | m ⑨m[a ，b]＝[ma ，mb] （2）奇偶性分析 （3）个位数定理：在n 4k ＋r （k ，r 为非负整数）中，0≢r ＜4，则当r ＝0（k ≠0）时，n 4k ＋r 的个位数字与n 4的个位数字相同；当r ≠0时，n 4k ＋r 的个位数字与n r 的个位数字相同。

（4）平方数性质：①个位数字只能是：0，1，4，5，6，9 ②末两位数字不可能同时为奇数。

③偶数的平方是偶数，且被4整除；奇数的平方是奇数，且被4除余1。

④在n 2与（n ＋1）2之间不存在平方数。

（5）算术基本定理：任何一个大于1的整数都可以分解成素数的乘积。

如果不考虑这些素因子的次序，则这种分解法是唯一的。

即对任一整数a ＞1，有a ＝p 1α1p 2α2…p nαn ，其中p 1＜p 2＜…＜p n 均为素数，α1、α2、…、αn 都是正整数。

初等数论学习总结本课程只介绍初等数论的的基本容。

由于初等数论的基本知识和技巧与中学数学有着密切的关系， 因此初等数论对于中学的数学教师和数学系(特别是师院校)的本科生来说，是一门有着重要意义的课程，在可能情况下学习数论的一些基础容是有益的．一方面通过这些容可加深对数的性质的了解，更深入地理解某些他邻近学科，另一方面，也许更重要的是可以加强他们的数学训练，这些训练在很多方面都是有益的．正因为如此，许多高等院校，特别是高等师院校，都开设了数论课程。

最后，给大家提一点数论的学习方法，即一定不能忽略习题的作用，通过做习题来理解数论的方法和技巧，华罗庚教授曾经说过如果学习数论时只注意到它的容而忽略习题的作用，则相当于只身来到宝库而空手返回而异。

数论有丰富的知识和悠久的历史，作为数论的学习者，应该懂得一点数论的常识，为此在辅导材料的最后给大家介绍数论中著名的“哥德巴赫猜想”和费马大定理的阅读材料。

初等数论自学安排第一章：整数的可除性（6学时）自学18学时整除的定义、带余数除法 最大公因数和辗转相除法 整除的进一步性质和最小公倍数 素数、算术基本定理[x]和{x}的性质与其在数论中的应用习题要求3p ：2，3 ； 8p ：4 ；12p ：1；17p ：1，2，5；20p ：1。

第二章：不定方程（4学时）自学12学时二元一次不定方程c by ax =+多元一次不定方程c x a x a x a n n =++ 2211 勾股数 费尔马大定理。

习题要求29p ：1，2，4；31p ：2，3。

第三章：同余（4学时）自学12学时同余的定义、性质 剩余类和完全剩余系 欧拉函数、简化剩余系欧拉定理、费尔马小定理与在循环小数中的应用 习题要求43p ：2，6；46p ：1；49p ：2，3；53p 1，2。

第四章：同余式（方程）（4学时）自学12学时同余方程概念 子定理高次同余方程的解数和解法 素数模的同余方程 威尔逊定理。

福师期末考试《初等数论》复习题及参考答案本复习题页码标注所用教材为：教材名称 单价 作者版本 出版社 初等数论14.20闵嗣鹤，严士健第三版高等教育出版社复习题及参考答案一一、填空(40%)1 、求所有正约数的和等于15的最小正数为 考核知识点：约数，参见P14-19 2、若1211,,,b b b 是模11的一个完全剩余系，则121181,81,,81b b b +++也是模11的 剩余系.考核知识点：完全剩余系，参见P54-573．模13的互素剩余系为考核知识点：互素剩余系，参见P584.自176到545的整数中是13倍数的整数个数为 考核知识点：倍数，参见P11-13 5、如果p 是素数,a 是任意一个整数,则a 被p 整除或者考核知识点：整除，参见P1-46、b a ,的公倍数是它们最小公倍数的 . 考核知识点：最小公倍数，参见P11-137、如果b a ,是两个正整数,则存在 整数r q ,,使r bq a +=,b r ≤0.考核知识点：整除，参见P1-4 8、如果n 3，n 5，则15（ ）n . 考核知识点：整除，参见P1-4二、(10%)试证：6|n(n+1)(2n+1)，这里n 是任意整数。

考核知识点：整除的性质，参见P9-12提示：i)若 则ii)若 则iii)若 则又三、(10%)假定a 是任意整数，求证a a (mod )++≡2103或a a (mod )+≡203考核知识点：二次同余式，参见P88提示:要证明原式成立，只须证明231a a ++，或者23a a +成立即可。

四、（10％）设p 是不小于5的素数，试证明21(mod 24)p ≡ 考核知识点：同余的性质，参见P48-52提示： 且是不小于5的素数．又 且是不小于5的素数．只能是奇数且即即五、(15%)解同余式组 51(mod7)142(mod8)x x ≡⎧⎨≡⎩考核知识点：同余式，参见P74-75 提示∵ (14，8)=2 且 2 | 2 ∴ 14x ≡2(mod8) 有且仅有二个解解7x ≡1(mod4) ⇒ x ≡3 (mod4) ∴ 6x ≡10(mod8)的解为 x ≡3，3+4(mod8) 原同余式组等价于()()3mod 73mod8x x ≡⎧⎪⎨≡⎪⎩ 或()()3mod 77mod8x x ≡⎧⎪⎨≡⎪⎩分别解出两个解即可。

初等数论复习题答案1. 试述质数与合数的定义。

答案：质数是指大于1的自然数，除了1和它本身以外不再有其他因数的数。

合数则是指除了1和它本身之外，还有其他因数的自然数。

2. 请解释最大公约数和最小公倍数的概念。

答案：最大公约数（GCD）是指两个或多个整数共有约数中最大的一个。

最小公倍数（LCM）是指两个或多个整数的最小公共倍数。

3. 举例说明辗转相除法（欧几里得算法）的计算过程。

答案：设两个正整数为a和b（a > b），辗转相除法的过程是：用较大的数除以较小的数，得到余数r，然后用较小的数去除这个余数，再得到新的余数，如此反复，直到余数为0，最后的除数即为最大公约数。

4. 试证明费马小定理。

答案：费马小定理指出，如果p是一个质数，a是一个不被p整除的整数，则a^(p-1) ≡ 1 (mod p)。

证明过程通常涉及模运算和群论的基本概念。

5. 说明中国剩余定理的基本原理。

答案：中国剩余定理是数论中一个关于线性同余方程组的定理。

给定一组两两互质的模数和一组对应的余数，定理保证了存在一个唯一的解，这个解在模数乘积的模下是唯一的。

6. 什么是素数定理？请简要说明。

答案：素数定理描述了素数在自然数中的分布情况。

它指出，小于或等于给定数x的素数数量大约是x除以x的自然对数，即π(x) ≈ x / ln(x)。

7. 描述同余的概念及其性质。

答案：同余是指两个整数a和b，若它们除以正整数n后余数相同，则称a和b同余模n，记作a ≡ b (mod n)。

同余具有自反性、对称性和传递性等性质。

8. 简述模运算的性质。

答案：模运算的性质包括加法和乘法的封闭性、结合律、交换律、分配律以及模逆元的存在性等。

9. 试解释什么是完全数。

答案：完全数是指一个正整数，它等于其所有真因数（即除了自身以外的因数）之和。

10. 请解释什么是亲和数。

答案：亲和数是一对或一组数，其中每个数的所有真因数之和等于另一个数。

例如，220和284就是一对亲和数，因为220的真因数之和为1+2+4+5+10+11+20+22+44+55+110=284，而284的真因数之和也为220。

大一初等数论知识点总结数论，作为数学的一个分支，是研究整数的性质和结构的学科。

在高等数学中，数论是一个重要的基础学科，也是培养数学思维和证明能力的重要内容之一。

下面将总结一些大一初等数论中的重要知识点。

一、素数与因数分解1. 素数定义：一个大于1的自然数，除了1和它本身以外没有其他因数的数被称为素数。

2. 质因数分解定理：任何一个大于1的自然数都可以表示为一系列素数的乘积，且这个分解方式是唯一的。

3. 最大公因数与最小公倍数：最大公因数是两个数同时能整除的最大的自然数，最小公倍数是能同时被两个数整除的最小的自然数。

二、模运算1. 同余：对于给定的正整数m，如果两个整数a和b满足a-b 能被m整除，则称a和b在模m下同余，记作a≡b (mod m)。

2. 同余性质：同余具有如下性质：- a ≡ b (mod m) 且c ≡ d (mod m)，则a±c ≡ b±d (mod m)。

- a ≡ b (mod m) 且c ≡ d (mod m)，则ac ≡ bd (mod m)。

3. 模运算法则：模运算具有如下法则：- (a+b) mod m = (a mod m + b mod m) mod m- (a-b) mod m = (a mod m - b mod m) mod m- (ab) mod m = (a mod m)(b mod m) mod m三、整除性与剩余类1. 整除性定义：如果a能被b整除，则称a是b的倍数，b是a 的因数。

2. 剩余类定义：对于给定的正整数m，将整数a分成m个不同的等价类，每个等价类都与m同余的整数被称为模m的一个剩余类。

3. 剩余类的运算：模m的剩余类满足如下运算规则：- 模m的剩余类可以进行加法和乘法运算。

- 模m的剩余类乘法满足交换律和结合律。

四、欧几里得算法与最大公因数1. 欧几里得算法：欧几里得算法用于求两个正整数的最大公因数，具体步骤如下：- 设a和b是两个正整数，其中a>b。

第一节 整数的p 进位制及其应用正整数有无穷多个，为了用有限个数字符号表示出无限多个正整数，人们发明了进位制，这是一种位值记数法。

进位制的创立体现了有限与无限的对立统一关系，近几年来，国内与国际竞赛中关于“整数的进位制”有较多的体现，比如处理数字问题、处理整除问题及处理数列问题等等。

在本节，我们着重介绍进位制及其广泛的应用。

基础知识给定一个m 位的正整数A ，其各位上的数字分别记为021,,,a a a m m --，则此数可以简记为：021a a a A m m --=（其中01≠-m a ）。

由于我们所研究的整数通常是十进制的，因此A 可以表示成10的1-m 次多项式，即012211101010a a a a A m m m m +⨯++⨯+⨯=---- ，其中1,,2,1},9,,2,1,0{-=∈m i a i 且01≠-m a ，像这种10的多项式表示的数常常简记为10021)(a a a A m m --=。

在我们的日常生活中，通常将下标10省略不写，并且连括号也不用，记作021a a a A m m --=，以后我们所讲述的数字，若没有指明记数式的基，我们都认为它是十进制的数字。

但是随着计算机的普及，整数的表示除了用十进制外，还常常用二进制、八进制甚至十六进制来表示。

特别是现代社会人们越来越显示出对二进制的兴趣，究其原因，主要是二进制只使用0与1这两种数学符号，可以分别表示两种对立状态、或对立的性质、或对立的判断，所以二进制除了是一种记数方法以外，它还是一种十分有效的数学工具，可以用来解决许多数学问题。

为了具备一般性，我们给出正整数A 的p 进制表示：012211a p a p a p a A m m m m +⨯++⨯+⨯=---- ，其中1,,2,1},1,,2,1,0{-=-∈m i p a i 且01≠-m a 。

而m 仍然为十进制数字，简记为p m m a a a A )(021 --=。

题目：一、求同余式的解：111x 75(mod321)≡二、求高次同余式的解：)105(m od 0201132≡-+x x 。

三、求高次同余式的解: 27100x x ++≡(mod 13). 四、计算下列勒让德符号的值:105223-⎛⎫⎪⎝⎭, 91563⎛⎫⎪⎝⎭五、计算下列勒让德符号的值：)593438(，)1847365(六、韩信点兵：有兵一队，若列成五行纵队，则末行一人；成六行纵队，则末行五人；成七行纵队，则末行四人；成十一行纵队，则末行十人。

求兵数。

七、设 b a ,是两个正整数，证明: b a ,的最大公因子00(,)a b ax by =+,其中00ax by +是形如ax by +(,x y 是任意整数)的整数里的最小正数. 八、证明：存在无穷多个自然数n ，使得n 不能表示为p a +2（a > 0是整数，p 为素数）的形式。

九、证明: 若方程 11...0n n n x a x a -+++= (0,i n a > 是整数,1,...,i n =)有有理数解,则此解必为整数.十、证明: 若(,)1a b =， 则(,)12a b a b +-=或十一、证明：设N ∈c b a ,,，c 无平方因子，c b a 22，证明：b a 。

十二、设p 是奇素数,1),(=p n , 证明: ⎪⎪⎭⎫ ⎝⎛≡-p n np 21 (mod p ). 十三、设m > 1，模m 有原根，d 是)(m ϕ的任一个正因数，证明：在模m 的缩系中，恰有)(d ϕ 个指数为d 的整数，并由此推出模m 的缩系中恰有))((m ϕϕ个原根。

十四、设g 是模m 的一个原根，证明：若γ通过模()m ϕ的最小非负完全剩余系, 则g γ通过模m 的一个缩系。

第一题：求同余式的解：111x 75(mod321)≡ 解答：(111,321)3,375=∴同余式有三个解11175321x (m o d )333≡ 即 37x 25(mod107)≡ 4x 75(m o d 10≡ 又x 2775(mod107)99(mod107)≡⨯≡因此同余式的解为x 99,206,313(mod321)≡。