下载文档原格式
第三章同余例题分析例1：求3406的末二位数。
解：∵（3，100）=1，∴3)100(φ≡1（mod 100）φ(100)=φ(22·52)=40,∴340≡1(mol 100)∴3406=(340)10·36≡(32)2·32≡-19×9≡-171≡29(mod 100)∴末二位数为29。
例2：证明（a+b ）p ≡a p +b p (mod p )证：由费尔马小定理知对一切整数有：a p ≡a （p ），b p ≡b (P )，由同余性质知有：a p +b p ≡a+b (p )又由费尔马小定理有（a+b ）p ≡a+b (p )（a+b ）p ≡a p +b p (p )例3：设素数p >2，则2P -1的质因数一定是2pk +1形。
证：设q 是2p -1的质因数，由于2p -1为奇数，∴q ≠2，∴（2·q ）=1,由条件q|2p -1,即2p ≡1（mod q ），又∵（q ,2）=1，2p ≡1（mod q ）设i 是使得2x ≡1（mod p ）成立最小正整数若1<i <p ，则有i |p 则与p 为素数矛盾∴i=p ,∴p |q -1又∵q -1为偶数，2|q -1,∴2p |q -1,q -1=2pk ,即q =2pk +1例4：证明13|42n +1+3n +2证：∵42n +1+3n +2≡4·16n +9·3n≡3n (4+9)≡13×3n ·≡0(13)∴13|42n +1+3n +2例5：证明5y +3=x 2无解证明：若5y +3=x 2有解，则两边关于模5同余有5y +3≡x 2(mod 5)即3≡x 2(mod 5)而任一个平方数x 2≡0,1,4(mod 5)∴30,1,4(mod 5)∴即得矛盾，即5y +3=x 2无解例6：求50111......被7除的余数。
初等数论练习题答案信阳职业技术学院2010年12月初等数论练习题一一、填空题1、d(2420)=12; ϕ(2420)880_2、设是大于1的整数，若1是质数，则2.3、模9的绝对最小完全剩余系是_{-4，-3，-2，-1,0,1,2,3,4}.4、同余方程912≡0( 37)的解是x ≡11( 37)。
5、不定方程的通解是900+23t ，700+18t t Z 。
.6、分母是正整数m 的既约真分数的个数为_(m )_。
7、18100被172除的余数是_256。
8、⎪⎭⎫⎝⎛10365 1。
9、若p 是素数，则同余方程x p 11( p )的解数为 1 。
二、计算题1、解同余方程：3x 211x 20 0 ( 105)。
解：因105 = 357，同余方程3x 211x 20 0 ( 3)的解为x 1 ( 3)， 同余方程3x 211x38 0 ( 5)的解为x0，3 ( 5)， 同余方程3x 211x 20 0 ( 7)的解为x 2，6 ( 7)，故原同余方程有4解。
作同余方程组：xb 1 ( 3)，xb 2 ( 5)，xb 3 ( 7)，其中b 1 = 1，b 2 = 0，3，b 3 = 2，6，由孙子定理得原同余方程的解为x13，55，58，100 ( 105)。
2、判断同余方程x 2≡42( 107)是否有解？11074217271071107713231071107311072107710731072107732107422110721721107213)(=∴-=-=-==-=-=-==⨯⨯≡-•--•-）（）（）（）（），（）（）（）（），（）（））（）（（）（解：故同余方程x 2≡42( 107)有解。
3、求（127156+34）28除以111的最小非负余数。
解：易知1271≡50（ 111）。
由502 ≡58（ 111）, 503 ≡58×50≡14（ 111），509≡143≡80（ 111）知5028 ≡（509）3×50≡803×50≡803×50≡68×50≡70（ 111） 从而5056 ≡16（ 111）。
初等数论初等数论自学安排第一章：整数的可除性（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学时同余方程概念 孙子定理高次同余方程的解数和解法 素数模的同余方程 威尔逊定理。
习题要求60p ：1；64p ：1，2；69p ：1，2。
第五章：二次同余式和平方剩余（4学时）自学12学时二次同余式单素数的平方剩余与平方非剩余 勒让德符号 二次互反律 雅可比符号、素数模同余方程的解法习题要求78p ：2； 81p ：1，2，3；85p ：1，2；89p ：2；93p ：1。
第六章：原根与指标（2学时）自学8学时指数的定义及基本性质 原根存在的条件 指标及n 次乘余 模2 及合数模指标组、 特征函数习题要求123p ：3。
➢ 第一章 整除 一、主要内容筛法、[x]和{x}的性质、n ！的标准分解式。
二、基本要求通过本章的学习，能了解引进整除概念的意义，熟练掌握整除 整除的定义以及它的基本性质，并能应用这些性质，了解解决整除问题的若干方法，熟练掌握本章中二个著名的定理：带余除法定理和算术基本定理。
认真体会求二个数的最大公因数的求法的理论依据，掌握素数的定义以及证明素数有无穷多个的方法。
初等数论期末复习数论教案§1整数的整除带余除法1 整数的整除设a,b 是整数,且b ≠0,如果有整数q,使得a=bq,则称b 整除a,记为b|a,也称b 是a 的因数,a 是b 的倍数. 如果没有整数q,使得a=bq,则称b 不能整除a,记为b ?a.例如 2|4, 4|-12, -5|15; 2?3， -3?22. 在中⼩学数学⾥,整除概念中的整数是正整数,今天讲的整除中的整数可正可负. 判断是否b|a ？当a,b 的数值较⼤时,可借助计算器判别.如果b 除a 的商数是整数,说明b|a;如果b 除a 的商不是整数,说明b ?a.例1判断下列各题是否b|a ？(1) 7|127? (2) 11|129? (3) 46|9529? (4) 29|5939? 整除的简单性质(1)如果c|b,b|a,那么c|a;(2)如果d|a,d|b,那么对任意整数m,n,都有d|ma+nb. (3)如果12,,,n a a a L 都是m 的倍数,12,,,n q q q L 是任意整数,那么1122n n q a q a q a +++L 是m 的倍数.(4)如果c|a,d|b,那么cd|ab 。
例如： 2|4,2|(-6),那么2|4+(-6),2|4-(-6). 2|4,3|(-6),那么2×3|4×(-6). 例2证明任意2个连续整数的乘积,⼀定可被2整除. 练习证明任意3个连续整数的乘积,⼀定可被3整除. 2.带余除法设a,b 是整数,且b>0,那么有唯⼀⼀对整数q,r 使得 a=bq+r,0≤r ＜ b . (1) 这⾥q 称为b 除a 的商,r 称为b 除a 的余数.例如-5=3×(-2)+1 5=3×1+2 -5=(-3)×2+1 5=(-3)×(-1)+2 15=(-5)×(-3), -24=(-2)×12. 事实上,以b 除a 的余数也可以是负的.例如 -5=3×(-1)-2=3×(-2)+1.求b 除a 的余数,也称为模运算(取余):mod.可⽤计算器进⾏.具体操作:输⼊a-按mod(取余)键-输⼊b-按=键得出余数.如果b 除a 的余数=0,则b|a;如果b 除a 的余数≠0,则b ?a.例3 利⽤计算器求余数:(1) 7除127;(2)11除-129 ;(3)46除-9529;(4)-29除5939 奇数、偶数及性质能被2整除的整数称为偶数.如,0,4,10,-6,-8都是偶数. 不能被2整除的整数称为奇数.如,-5,-3,1,7,11都是奇数. 偶数的形式为2n(n 是整数);奇数的形式为2n-1(n 是整数).奇数、偶数的性质: 偶数±偶数=偶数,奇数±奇数=偶数,奇数±偶数=奇数,偶数×偶数=偶数,偶数×奇数=偶数,奇数×奇数=奇数.例如 2+4,2-4,3+1,3-1,3+4,6+5设a,b 是任意两个整数,则a+b 与a-b 同奇同偶. 例如3+5,3-5,6+3,6-3,例4设a,b,n 是任意3个整数,⽽且222a b n -=,证明n 是偶数. 例5设a 是任⼀奇数,试证明8|21a -. 例6设n 是正整数,证明形如3n-1整数不是完全平⽅数.证明对任意整a,设a=3q 或a=3q ±1,于是2a=92即2a ≠3n-1,故3n-1不是完全平⽅数.练习设n 是正整数,证明形如4n-1、4n+2的整数都不是完全平⽅数. 习题:P3-4:1t,2t.§2公因数、最⼤公因数 1.最⼤公因数、辗转相除法中⼩学⾥的公因数、最⼤公因数的概念：⼏个数的公有因数叫做这⼏个数的公因数.公因数中最⼤的整数称为这⼏个数的最⼤公因数. (1)⼏个数:不能确定;(2)因数、公因数:都是正整数; 最⼤公因数:没有专门的符号. 定义设12,,,n a a a L ,d 都是整数,d ≠0,如果i d a ,i=1,2,…,n,称d 是12,,,n a a a L 的公因数,12,,,n a a a L 的公因数中最⼤的整数称为最⼤公因数.记为12(,,,)n a a a L .如果12(,,,)n a a a L =1,则称12,,,n a a a L 互质。
初等数论第一次作业（第1章）一、单项选择题1、=),0(b （ ）.A bB b -C bD 02、如果a b ，b a ，则( ).A b a =B b a -=C b a ≤D b a ±=3、如果1),(=b a ，则),(b a ab +=（ ）.A aB bC 1D b a +4、小于30的素数的个数（ ）.A 10B 9C 8D 75、大于10且小于30的素数有（ ）.A 4个B 5个C 6个D 7个6、如果n 3，n 5，则15（ ）n .A 整除B 不整除C 等于D 不一定7、在整数中正素数的个数（ ）.A 有1个B 有限多C 无限多D 不一定二、计算题1、求24871与3468的最大公因数?2、求[24871,3468]=?3、求[136,221,391]=?三、证明题1、如果b a ,是两个整数,0 b ,则存在唯一的整数对r q ,,使得r bq a +=,其中b r ≤0.2、证明对于任意整数n ,数62332n n n ++是整数. 3、任意一个n 位数121a a a a n n -与其按逆字码排列得到的数n n a a a a 121- 的差必是9的倍数.4、证明相邻两个偶数的乘积是8的倍数.第一次作业参考答案1、=),0(b （C ）.Ab B b - D 02、如果a b ，b a ，则(D ).A b a =B b a -=C b a ≤D b a ±=3、如果1),(=b a ，则),(b a ab +=（C ）.A aB bC 1D b a +4、小于30的素数的个数（A ）.A 10B 9C 8D 75、大于10且小于30的素数有（ C ）.A 4个B 5个C 6个D 7个6、如果n 3，n 5，则15（A ）n .A 整除B 不整除C 等于D 不一定7、在整数中正素数的个数（C ）.A 有1个B 有限多C 无限多D 不一定二、计算题1、 求24871与3468的最大公因数?解： 24871=3468⨯7+5953468=595⨯5+493595=493⨯1+102493=102⨯4+85102=85⨯1+1785=17⨯5,所以,(24871,3468)=17.2、 求[24871,3468]=?解：因为（24871,3468）=17所以[24871,3468]= 17346824871⨯ =5073684所以24871与3468的最小公倍数是5073684。
第二章不定方程例题分析例1：利用整数分离系数法求得不定方程15x +10y +6z =61。
解：注意到z 的系数最小，把原方程化为z =)()(12361102261101561++-++--=+--y x y x y x 令t 1=z y x ∈++-)(12361，即-3x +2y -6t 1+1=0此时y 系数最小，)()(12131632111-++=-++=∴x t x t x y 令t 2=z x ∈-)(121,即122+=t x ,反推依次可解得y =x +3t 1+t 2=2t 2+1+3t 1+t 2=1+3t 1+3t 2z =-2x -2y +10+t 1=6-5t 1+10t 2∴原不定方程解为⎪⎩⎪⎨⎧--=++=+=21212105633121t t z t t y t x t 1t 2∈z.例2:证明2是无理数证：假设2是有理数，则存在自数数a,b 使得满足222y x =即222b a =，容易知道a 是偶数，设a =2a 1，代入得2122a b =,又得到b 为偶数，a b a <<1，设12b b =，则21212b a =,这里12a b <这样可以进一步求得a 2，b 2…且有a>b>a 1>b 1>a 2>b 2>…但是自然数无穷递降是不可能的，于是产生了矛盾，∴2为无理数。
例3：证明：整数勾股形的勾股中至少一个是3的倍数。
证：设N =3m ±1(m 为整数)，∴N 2=9m 2±6m +1=3(3m 2±2m )+1即一个整数若不是3的倍数，则其平方为3k +1,或者说3k +2不可能是平方数，设x,y 为勾股整数，且x,y 都不是3的倍数，则x 2,y 2都是3k +1，但z 2=x 2+y 2=3k +2形，这是不可能，∴勾股数中至少有一个是3的倍数。
例4：求x 2+y 2=328的正整数解解：∵328为偶数，∴x,y 奇偶性相同，即x ±y 为偶数，设x+y =2u ,x -y =2v ，代入原方程即为u 2+v 2=164,同理令u +v =2u 1,u -v =2v 1有21121121212282v v u u v u v u =-=+=+,,,412222=+v u 22v u ,为一偶一奇，且0<u 2<6u 2=1，2，3，4，5代方程，有解（4，5）（5，4）∴原方程解x =18,y =2,或x =2,y =18。
《初等数论》例题选讲1一、计算题1、求24871与3468的最大公因数?分析：利用辗转相除法，r n 即最大公因数解：24871=3468⨯7+5953468=595⨯5+493595=493⨯1+102493=102⨯4+85102=85⨯1+1785=17⨯5,所以,(24871,3468)=17.2、求[24871,3468]=?解：因为（24871,3468）=17所以[24871,3468]=17346824871⨯=5073684所以24871与3468的最小公倍数是5073684。
3、求[525,231]=?解：解：因为（525,231）=21所以[525,231]=17231525⨯=57754、求[136,221,391]=?分析：如果i a (k i ≤≤1)是k 个整数，则],,[1k a a =k m .先求[136,221]=1768，再求[1768,391]=40664，即是136,221,391三数的最大公倍数解：[136,221,391]=[[136,221],391]=[391,17221136⨯]=[1768,391]=173911768⨯=104⨯391=40664.二、证明题1、如果b a ,是两个整数,0 b ,则存在唯一的整数对r q ,,使得r bq a +=,其中b r ≤0.分析：注意“存在唯一”的含义，即证明存在性、唯一性。
证明：首先证明唯一性.设q ',r '是满足条件的另外整数对,即r q b a '+'=,b r '≤0.所以r bq r q b +='+',即()r r q q b '-=-',r r q q b '-=-'.又由于b r ≤0,b r '≤0,所以b r r '-.如果q q '≠,则等式r r q q b '-=-'不可能成立.因此q q '=,r r '=.其次证明存在性.我们考虑整数的有序列……,,3,2,,0,,2,3b b b b b b ---……则整数a 应介于上面有序列的某两数之间,即存在一整数q 使()b q a qb 1+≤ .我们设qb a r -=,则有r bq a +=,b r ≤0.2、证明对于任意整数n ,数62332n n n ++是整数.分析：要证明数62332n n n ++是整数，需证明数62332n n n ++的结果的分数形式商是整数，化简62332n n n ++，得62332n n n ++=)32(62n n n ++=)2)(1(61++n n n ，于是，要证明数62332n n n ++是整数，相当于证明6整除)2)(1(++n n n 。
