《初等数论》本科一、填空题（每空2分）1.写出30以内的所有素数2.,a b 设3.若,a b 是非零整数，则a 与b 互素的充要条件是存在整数,x y ，使1ax by +=4.写出180的标准分解式是(2+1)(2+1)(1+1)=18个.5.,1,2,,a b a b 设与是正整数则在中能被.6.设,a b 是非零整数，c 是整数，方程ax by c +=有整数解(,x y )的充要条件是(,)|a b c7.A m 的完全剩余系，则A 中含有m 个整数.8.ϕ9.当p 素数时，(1)()p ϕ=1p -;(2)()k p ϕ=1k k p p --.10.(),(,)1,1m m a m a ϕ=-设是正整数则).m11.,,p p a a a -设是素数则对于任意的整数有).p12.已知235(mod 7)x +≡，则x 7).13.同余方程22(mod7)x ≡14.同余方程2310120(mod9)x x ++≡的解是X=6+9t(t ∈Z ). 15.(,)1n p =若，n p 是模的二次剩余的充要条件是-121(mod ).p np ≡.16.(,)1n p =若，n p 是模的二次非剩余的充要条件是-121(mod ).p np ≡-.17.3(54(518.,p 设是奇素数则2()p=218(1).p --.19.,p 设是奇素数则1()p -1()p=20.5()=92()=45二、判断题。

(判断下列结论是否成立，每题2分). 1.||,|a b a c x y Z a bx cy ⇒∈+且对任意的有.成立 2.(,)(,),[,][,]a b a c a b a c ==若则.不成立3.23|,|a b a b 若则.不成立a=8b=124.(mod ),0,(mod ).a b m k k N ak bk mk ≡>∈⇒≡成立5.(mod )(mod ).ac bc m a b m ≡⇒≡不成立6.22(mod ),(mod )(mod )a b m a b m a b m ≡≡≡-若则或至少有一个成立.不成立7.222(mod ),(mod )a b m a b m ≡≡若则.不成立8.若x 通过模m 的完全剩余系，则x b +(b 是整数)通过模m 的完全剩余系.成立9.若｛1a ，2a ，……，m a ｝与｛1b ，2b ……m b ｝都是模m 的完全剩余系，则｛1a +1b ，2a +2b ，……，m a +m b ｝也是模m 的完全剩余系。

不成立10.若(,)1a m =，x 通过模m 的简化剩余系（完全剩余系），则ax b +也通过模m 的简化剩余系.不成立 11.12121212,,(,)1,()()().m m N m m m m m m ϕϕϕ∈==若则成立12.同余方程24330(mod15)x x -+≡和同余方程2412120(mod15)x x +-≡是同解的.成立13.(mod ).ax b m ax my b ≡+=同余方程等价于不定方程成立14.2,(mod ),() 1.am x a m m≡=当是奇素数时若有解则成立15.2,()1,(mod ).a m x a m m=≡当不是奇素数时若则方程一定有解不成立三计算题1.(1859,1573)-求解：1.(1859,1573)(1859,1573)(286,1573)(286,15732865)(286,143)(0,143)143-===-⨯===2.求[－36，108，204]解：22232232.[36,108,204][36,108,204],3623,10823,2042317,[36,108,204]23171836.-==⨯=⨯=⨯⨯∴=⨯⨯=3.求(125，17)，以及x ，y ，使得125x +17y =(125，17)解：3.651,16-56-(17-26)36-173(125-177)-173125-2217.1253-17221,3,-22.x y =+==⨯=⨯=⨯⨯=⨯⨯∴⨯⨯===由等式起逐步回代得4.求整数x ，y ，使得1387x －162y =(1387，162)解：4.9421,19-429-4(11-9)59-4115(20-11)-411520-911520-9(71320)322097132(91-71)97132914171329141(16291)73914116273(13878162)41162731387625162.1=⨯+=⨯=⨯=⨯⨯=⨯⨯=⨯⨯=⨯⨯-⨯=⨯-⨯=⨯-⨯=⨯-⨯=⨯-⨯-=⨯-⨯=⨯-⨯-⨯=⨯-⨯∴由等式起逐步回代得38773162625 1.⨯-⨯=5.12!.分解为质因数乘积（8分）6.,10|199!k k 求最大的正整数使.（8分）7.[1].100++求(10分) 8.81743.x y +=求方程的整数解(6分)9.19201909.x y +=求方程的正整数解(10分)10.求方程111x －321y =75的整数解.(10分) 11.12310661.x x x ++=求方程15的整数解(8分) 12.361215.x y z ++=求不定方程的整数解(8分)13.237.x y z ++=求不定方程的所有正整数解(8分)14.19,2,3 5.30将写成三个分数之和它们的分母分别是和(10分) 15.222370.x y x y +--=求方程的整数解(6分) 16.331072.x y +=求方程的整数解(8分)17.5()4.xy yz zx xyz ++=求方程的正整数解(10分)18.4063().求的个位数字与最后两位数字十进制(10分) 19.67(mod 23).x ≡解同余方程(8分) 20.12150(mod 45).x +≡解同余方程(8分)21.2(mod 3)3(mod 5).2(mod 7)x x x ≡⎧⎪≡⎨⎪≡⎩解同余式组(6分)22.43()0(mod35),()289.f x f x x x x ≡=+++解同余式(10分)23.765:2720(mod5).x x x x --++≡解同余方程(6分)24..求出模23的所有二次剩余和二次非剩余(8分)25.25(mod11).x ≡判断方程有没有解(6分)26.2563,429(mod563).x ≡已知是素数判定方程是否有解(8分) 27.3求以为其二次剩余的全体素数.(8分)28.10173:(1)();(2)().1521计算(8分) 29.(300).ϕ计算(6分)30.3(mod8)11(mod 20).1(mod15)x x x ≡⎧⎪≡⎨⎪≡⎩解同余式组(10分)四证明题1、,,,, 1.:|,|,|.a b x y ax by a n b n ab n +=设是两个给定的非零整数且有整数使得求证若则(6分)证明：1.()|,|.n n ax by nax nbyab na ab nb ab n =+=+∴又2.121212,,,,0,.4|.n n n a a a a a a a a a n n +++==设是整数且则(8分)证明：1212121231122.,,,,,,0,2.,,,.,,2(2).-,(-1),,.,,,,4.n n n i n n n n a a a a a a n a a a a a i n a a a a n a a a n +++=∴≤≤+++=∴若是奇数则都是奇数则不可能即在中至少有一个偶数如果只有一个偶数不妨设为则不整除由知左边是个奇数的和右边是偶数这是不可能的在中至少有两个偶数即3.任给的五个整数中，必有三个数之和被3整除.(8分)证明：1231231231231231233.3,03,1,2,3,4,5.(1)0,1,2,0,1,2,3()3.(2)0,1,2,,(0,12),3()3.i i i i i i i a q r r i r r r r a a a q q q r r r r r r r a a a q q q r =+≤<====++=+++====++=+++设若在中数都出现不妨设则成立若在中数至少有一个不出现则至少有三个取相同的值令或则成立4.22,,9|,3|(,).a b a ab b a b ++设是整数且则(8分)证明：2222224.9,9()3,3()3,3(),3,9(),93,3,33.3,3,3.3.3,3.3(,).a ab b a b ab a b ab a b a b a b ab ab a b a a b b b a b a a b ++∴-+∴-+∴-∴-∴-∴∴∴-∴-∴或若若故5.设,a b 是正整数，证明()[,][,]a b a b a b a b +=+.(8分)证明：()5.()[,](),(,)(,)()[,](,),(,)(,),()[,](,),()[,],(,)ab b a b a b a b a b a a b a b b a b b a b b a b b a b a b b a b b a b a b b a b b a b a b ++=+⋅=⋅+=+++=∴+=++=+∴而即结论成立6.(mod ),0,,(mod ).nna b m n n N a b m ≡>∈≡当时又则(6分)证明：123216.(mod ),,()(),,(mod ).n n n n n n n n n n a b m m a b a b a b a a b a b b m a b a b m ----≡∴--=-++++∴-≡又即7.12{,,,},{}.m A x x x m x x =设是模的一个完全剩余系以表示的小数部分11:(,)1,{}(-1).2mi i ax b a m m m =+==∑证明若则(10分) 证明：1211111117.2,{,,,},(1),1(1)1{}{}{}{}.22m i mm mm m i i j j j j ax b ax b ax b m ax b km j j m ax b j j j j m m m k m m m m m m --=====++++=+≤≤+--=+====⋅=∑∑∑∑∑由定理知也是模的一个完全剩余系可设从而8.,:n N ∈设证明1()2,2k n n n k N ϕ==∈的充要条件是.(10分) 证明：-1-118.2,(2)2(1-)2.22(),2,2|,21()()()(2)(2)()2()2,222(),1,.(()112)k k k k k k k k k nn nn n t t n t n t n t t t t t t t t t n n ϕϕϕϕϕϕϕϕϕϕϕ⇐====⇒==/=====⨯⋅=⋅=∴==⇔=若则若设则即从而得证注或 9.,5|12344.n n n n n N n ∈+++⇔/设则(10分)证明：444449.(5)4,,1(mod 5)(14).4,03,1234(1)1(2)2(3)3(4)41234(mod 5).5|1234,5|1234,0,1,2,30,4;4,0,5|1234,n n n n q r q r q r q rr r r r n n n n r r r r r r r r k k n q r r r r n n r ϕ=≡≤≤=+≤≤+++≡⋅+⋅+⋅+⋅≡+++⇒++++++==∴//⇐=+++/由定理知令则若即得把代入检验可知若则易知5|1234.n n n n ∴+++/10.()1,(,)1,:(mod )(mod ).m m a m x ba m ax b m ϕ-=≡≡设是正整数证明是同余方程的解证明：()()()-110.(,)1,,1(mod ).(mod ),(,)1,(mod ).m m m a m Euler a m ax b a b m a m x a b m ϕϕϕ=≡∴≡≡=∴≡由定理则11.-121(mod ).p n p n p ≡-是模的二次非剩余的充要条件是(10分)证明：-111221122-121211.(,)1,,1(mod ),(1)(1)0(mod ),,10(mod )10(mod ),1(mod ),1(mod ).p p p p p p p n p Euler n p nnp p n p np n p n p np -----=≡∴+-≡+≡-≡≡∴≡-若则由定理是素数则或中必有一个成立是模的二次剩余的充要条件是 12.12(mod ),(mod ),y a p y a p p ≡≡设都是模的平方剩余12(mod ),(mod ).y b p y b p p ≡≡都是模的平方非剩余121211:(mod ),(mod ),(mod ).y a a p y b b p p y a b p p ≡≡≡求证都是模的平方剩余是模的平方非剩余(10分)证明：11112222121211122212121112.1,1(mod ),1(mod ),()()1(mod ),()1(mod ),.p p p p p p p a a p b b p a a b b p a b p -------≡≡≡≡-∴≡≡≡-∴由定理知得证13.22,43,:(mod ),(mod ).p q n x p q x q p +≡≡设为两个形如的奇质数求证若无解则有两个解(10分)1-122222221-113.:,43,,,22(mod ),()1,()(-1)()() 1.(mod ),,-(mod ),(-)(mod ),-,,(mod ).p q p q p q n p q p p x p q q p q qx q p c c c p c c q p c x q p c -⋅-+∴≡∴=-==-=∴≡≡=≡/∴≡±证明均为形如的数均为奇数又无解则有解设是其一解则因为且也是其一解又因为二次同余方程至多有两个解故恰有两个解为14.1(mod 4),(mod ).p p y a p p ≡≡设是适合的素数是模的平方剩余:(mod ).y a p p ≡-证明也是模的平方剩余(8分)121214.:41,1,1(mod ),(-)1(mod ).p p p k a p a p --=+≡≡证明令由定理知则15.2,:141.n n m ++设是整数证明的任何奇因数都是的形式(10分)22215.:,4141.:1,41.|1,1(mod ),-1(),,4 1.m m p n p m p n n p QR p p m +++++≡-∈=+证明由于奇数都可表示成奇素数之积而且任意多个形如的整数之积也具有的形式我们只需证明若素数是的因数则具有的形式若则即由以上推论知 16.-1,1(mod )-1.p p x p p ≡若是素数则同余方程有个解(8分)16.:(),.,-1,1,2,3,,-1(mod ).Fermat p p x p p ≡证明由费马定理定理可知任意与互质的数都是它的解因此这个同余方程恰好有个不同的解即17.-1-1100101010,:9|9|.nnn n n i i N a a a a N a ==+++⋅+⇔∑设求证(8分)23111011017.101,101,101,,101(mod9),101010(mod9);n n n n n n n N a a a a a a a a ---≡≡≡≡∴=++++≡++++18.52:641|2 1.+求证(8分)5248163232218.24,216,2256,2154,21(mod 641),210(mod 641),6412 1.≡≡≡≡≡-∴+≡∴+19.:,,()(,)([,]).m n N mn m n m n ϕϕ∈=证明若则(10分)12121219.:[,],(1).111()(1-)(1-)(1-),111([,])[,](1-)(1-)(1-),(,)[,],111()(,)[,](1-)(1-)(1-)(,)([,]).i kk kmn m n p i k mn mn p p p m n m n p p p mn m n m n mn m n m n m n m n p p p ϕϕϕϕ≤≤===∴==证明易知与有相同的素因数设它们是则20.,,(mod ).p p a a a p ≡设是素数则对于任意的整数有(8分)120.:(,)1,,1(mod ),(()1),(mod ).(,)1,,0(mod ),p p pa p Euler a p p p a a p a p p a a a p ϕ-=≡=-∴≡>∴≡≡∴证明若由定理若则结论成立。