02013初等数论练习题及答案.doc

初等数论练****题一一、填空题 1、?(2420)= 27;?(2420)=_ 880 _ 2、设 a,n是大于 1的整数,若 a n -1是质数,则 a=_ 2. 3、模 9的绝对最小完全剩余系是_ {-4 , -3, -2, -1,0,1,2,3,4}. 4、同余方程 9x+12 ≡ 0(mod 37) 的解是 x≡ 11(mod 37) 。 5、不定方程 18x-23y=100 的通解是 x=900+23 t,y=700+18 tt?Z。. 6、分母是正整数 m的既约真分数的个数为_?(m)_。 7、18 100被17 2除的余数是_256 。 8、??????103 65 = -1。 9、若 p是素数,则同余方程 x p? 1?1(mod p)的解数为 p-1 。二、计算题 1、解同余方程:3x 2?11x ?20?0(mod 105) 。解:因105 =3?5?7, 同余方程 3x 2?11x ?20?0(mod 3)的解为 x?1(mod 3), 同余方程 3x 2?11x ?38?0(mod 5)的解为 x?0,3(mod 5), 同余方程 3x 2?11x ?20?0(mod 7)的解为 x?2,6(mod 7), 故原同余方程有 4解。作同余方程组:x?b 1(mod 3),x?b 2(mod 5),x?b 3(mod 7), 其中 b 1=1,b 2=0,3,b 3=2,6, 由孙子定理得原同余方程的解为 x?13,55,58,100 (mod 105) 。 2、判断同余方程 x 2≡ 42(mod 107) 是否有解? 1 107 42 17 27 107 1 107 713 23 107 1 107 31 107 2 107 7 107 3 107 2 107 732 107 42 2 1 107 2 17 2 1 107 2 13)( ?????????????????????????) ( ) ( ) ( ) ( ) ,( ) ( ) ( ) ( ) ,( ) ( ) )( )( ( ) ( 解: ?故同余方程 x 2≡ 42(mod 107) 有解。 3、求( 1271 56 +34 ) 28除以 111 的最小非负余数。 2 解:易知 127 1≡50(mod 111 )。由50 2≡58(mod 111 ),50 3≡58×50≡14(mod 111 ),50 9≡14 3≡80(mod 111 ) 知50 28≡(50 9) 3×50≡80 3×50≡80 3×50≡68×50≡70(mod 111 ) 从而 50 56≡16(mod 111 )。故(1271 56 +34 ) 28≡( 16+34 ) 28≡50 28≡70(mod 111 ) 三、证明题 1、已知 p是质数,(a,p) =1 ,证明: (1)当 a为奇数时, a p-1 +(p-1) a≡0 (mod p); (2)当 a为偶数时, a p-1 -(p-1) a≡0 (mod p)。证明:由欧拉定理知 a p-1≡1(mod p)及(p-1) a≡-1(mod p)立得( 1)和( 2)成立。 2、设 a为正奇数, n为正整数,试证 n2a ≡ 1(mod 2 n+2)。……………(1) 证明设a=2m?1,当 n=1时,有 a 2= (2m?1) 2=4m(m?1)?1?1 (mod 2 3),即原式成立。设原式对于 n=k成立,则有 ka 2?1 (mod 2 k+2)?a 2=1?q2 k+2, 其中 q?Z,所以 12 ?ka = (1?q2 k+2) 2=1?q?2 k+3?1 (mod 2 k+3), 其中 q?是某个整数。这说明式(1)当n=k?1也成立。由归纳法知原式对所有正整数 n成立。 3、设 p是一个素数,且 1≤k≤p-1 。证明: kp1C ??(-1) k(mod p)。证明:设 A=! )()2(1C 1k kppp kp??????) ( 得: k!·A=(p-1 )(p-2) …(p-k )≡(-1)(-2) …(-k)(mod p) 又( k!,p)=1,故 A= kp1C ??(-1) k(mod p) 4、设 p是不等于 3和7的奇质数,证明: p 6≡ 1(mod 84) 。说明:因为 84= 4×3×7,所以,只需证明: p 6≡ 1(mod 4)p 6≡ 1(mod3) p 6≡ 1(mod 7)同时成立即可。证明:因为 84= 4×3×7及p是不等于 3和7的奇质数,所以 3 (p,4) =1 ,(p,3) =1 ,(p,7) =1 。由欧拉定理知: p ?(4)≡p 2≡ 1(mod 4),从而 p 6≡ 1(mod 4)。同理可证: p 6≡ 1(mod3) p 6≡ 1(