《初等数论 期末复习》由会员分享，可在线阅读，更多相关《初等数论 期末复习（7页珍藏版）》请在金锄头文库上搜索。
1、 题目：一、求同余式的解： 111x75(mod321)二、求高次同余式的解：。)105(mod0201132xx三、求高次同余式的解: (mod 13).27100xx四、计算下列勒让德符号的值:, 105 22391 563五、计算下列勒让德符号的值：，)593438()1847365(六、韩信点兵：有兵一队，若列成五行纵队，则末行一人；成六行纵队，则末行五人； 成七行纵队，则末行四人；成十一行纵队，则末行十人。求兵数。七、设 是两个正整数，证明: 的最大公因子,其中 ba,ba,00( , )a baxby00axby是形如(是任意整数)的整数里的最小正数.axby, x y八、证明：存
2、在无穷多个自然数 n，使得 n 不能表示为（a 0 是整数，p 为素数）pa 2的形式。九、证明: 若方程 ( 是整数,)有有理数解,则此1 1.0nn nxa xa0,ina1,.,in解必为整数.十、证明: 若， 则( , )1a b (,)12ab ab 或十一、证明：设，c 无平方因子，证明：。cba,cba22ba十二、设是奇素数, 证明: (mod ).p1),(pn pnnp 21 p十三、设 m 1，模 m 有原根，d 是的任一个正因数，证明：在模 m 的缩系中，恰)(m有 个指数为 d 的整数，并由此推出模 m 的缩系中恰有个原根。)(d)(m十四、设是模的一个原根，证明：若
3、通过模的最小非负完全剩余系, 则通gm( )mg过模的一个缩系。m第一题：求同余式的解：111x75(mod321)解答： (111,321)3,3 75Q同余式有三个解即 11175321x(mod)33337x25(mod107)4x75(mod107)又x27 75(mod107)99(mod107)Q因此同余式的解为。x99,206,313(mod321)第二题：求高次同余式的解：)105(mod0201132xx解答：解：因, 753105同余方程的解为)3(mod0201132xx),3(mod1x同余方程的解为)5(mod0201132xx),5(mod3 , 0x同余方程的解为
4、)7(mod0201132xx),7(mod6 , 2x故原同余方程有 4 解。作同余方程组：，)3(mod1bx )5(mod2bx ,其中)7(mod3bx , 6 , 2, 3 , 0, 1321bbb由孙子定理得原同余方程的解为。)105(mod100,58,55,13x第三题：求高次同余式的解：2x7x100(mod13)解答：010；x 2,x +7x+10=时118；x 2,x +7x+10=时228；x 2,x +7x+10=时340；x 2,x +7x+10=时454；x 2,x +7x+10=时570；x 2,x +7x+10=时688；x 2,x +7x+10=时7108
5、；x 2,x +7x+10=时8130；x 2,x +7x+10=时9154；x 2,x +7x+10=时10180；x 2,x +7x+10=时11208=13x6；x 2,x +7x+10=时12238；x 2,x +7x+10=时因此，。x8,11(mod13)第四题：计算下列勒让德符号的值:, 105 22391 563解答：-105-1357()=()()()()223223223223223223 1(3-1)(223-1)(5-1)(223-1)(7-1)(223-1) 2444223223223=(-1)()(-1)()(-1)()(-1)3571361( )( 1)( )(
6、)( 1)357 2 4 4523( )( 1)( )( )377 2 6 4227( )( )( )( 1)373 9 149 1 881( 1)( 1)( )3 1 562 9090 16 44915631791()()( 1)()( 1)()( 1)( 1)563919117 289 12 16 8462317()()()( 1)()( 1)1717 173 9 1 82( )( 1)13 第五题：计算下列勒让德符号的值：，)593438()1847365(解答：=*=)593438()5932()593219(21593 21219 81593 ) 1(*) 1(2 )219593()
7、219155(=1)1552()15564()155219() 1(621219 21155 )1847365()3652)(36511()36522()3651847() 1(211847 21365 = 1) 1()112()11365(1) 1(811121365 2111 8136522 第六题：韩信点兵：有兵一队，若列成五行纵队，则末行一人；成六行纵队，则末行 五人；成七行纵队，则末行四人；成十一行纵队，则末行十人。求兵数。解答：，x1(mod5)x5(mod6)x4(mod7)x10(mod11)m5 6 7 11 ，1M6 7 11462 2M5 7 11385 3M5 6 11
8、330 4M5 6 7210 ， ，1M3 2M7 3M8 4M12 111222333444xM M bM M bM M bM M b (modm)462 3 1 385 7 5330 8 4210 12 10(mod2310) 1386 13475 1056025200(mod2310)2111(mod2310)兵数=2111+2310m，m 是任何一个非负整数。第七题：如 a，b 是两个正整数，则，其中是形如00(a,b)axby00axby（x，y 是任意整数）的整数里的最小正数。axby证：，其中 00aq(ax +by )+000ax +by若，等于是00000(1 qx )a(
9、qy )bax +by 与题意是最小正数矛盾，所以00ax +by0即00ax +by a同理可证，于是 ，因此。00ax +by b00ax +by (a,b)00ax +bya,b又 ，。Q00(a,b) ax +by00a,bax +by所以00(a,b)axby第八题：证明：存在无穷多个自然数 n，使得 n 不能表示为（a 0 是整数，p 为素数）pa 2的形式。证：存在无穷多个正整数 k，使得是合数，对于这样的 k， 不能表示为12 k2) 1( k的形式，pa 2事实上，若(k 1)2 = a2 p，则(k 1 a)( k 1 a) = p，得 k 1 a = 1，k 1 a =
10、p，即此与 p 为素数矛盾。, 12 kp第九题：证明: 若方程 ( 是整数,)有有理1 1.0nn nxa xa0,ina1,.,in数解,则此解必为整数解答：证：设有理根， （p，q）=1，代入，得到p qf(x)0nn-1n 1npa p q+a q =0Lnn-1n-1 1np(a p+a q)q L所以，但（p，q）=1，从而 qnq p1 因此该有理根必为整数。第十题：证明: 若， 则。( , )1a b (,)12ab ab 或证：(ab,ab)(ab,a+b+a-b)(ab,2a)（a，b）=1Q(ab,a)1于是，(ab,2a)(ab,2)12 或因此(ab,ab)1 或2第
11、十一题：证明：设，c 无平方因子，证明：。cba,cba22ba证：设，则，(a1, b1) = 1，dba),(1daa 1dbb 由得 a12b12c，a12c，cba22因为 c 无平方因子，所以 a1 = 1，a = d，b = ab1，即。ba第十二题：设是奇素数, 证明: (mod ).p1),(pn pnnp 21 p证：如果 n 是模数 p 的二次剩余，则2xn(modp),(p,n)1(1)有解，于是1x1(x ,p)1p 1 p-12 11xn(modp) 又，推出Qp-1n1(modp)p 1p 1 22(n1)(n1)0(modp) 因为 p 是奇素数，所以和只有一个成
12、立。我们p-1 2n1(modp)p-1 2n1(modp) 已经证明了，如果 n 是模数 p 的二次剩余，则成立，故 1，p-1 2n1(modp)2 p2，L是的个解，而且是它的全部解。2 pp 1()2p-1 2x1(modp)p 1 2于是模数 p 的缩系中个二次非剩余给出了的全部解。这样p 1 2p-1 2x1(modp) 就证明了 n 是模数 p 的二次非剩余则成立p-1 2n1(modp) 因此p 1 2nn( )(modp)p 第十三题：设 m 1，模 m 有原根 g，d 是的任一个正因数，证明：在模 m 的缩)(m系中，恰有 个指数为 d 的整数，并由此推出模 m 的缩系中恰
13、有个原)(d)(m根。 证：设模 m 有原根 g。因构成模 m 的缩系，)(21,mgggL由得令)(,()()(mmgdm,)()(,(dmmtdm)(则,1 , 1),()(1 ,)()(,(dtdtmdmm故恰有个 t，使得(t, d) = 1，从而知故恰有(d)个，使得m(g) = d。特别地，)(d取 d = (m)知模 m 的缩系中恰有个原根。)(m第十四题：设 g 是模 m 的一个原根，证明：若m通过模()的最小非负完全剩余系, 则通过模 m 的一个缩系。g证：是完全剩余系 0，1，2，L(m) 1又g 是模 m 的一个原根Q：对模数 m 两两不同余g012(m) 1g ,g ,g ,gL又因为（g，m）=1所以 i(g ,m)1i0,1,2, (m) 1L因此，通过模 m 的一个缩系。g
