初等数论 期末复习

题目：

一、求同余式的解： 

二、求高次同余式的解：。

三、求高次同余式的解: (mod 13).

四、计算下列勒让德符号的值:, 

五、计算下列勒让德符号的值：，

六、韩信点兵：有兵一队，若列成五行纵队，则末行一人；成六行纵队，则末行五人；成七行纵队，则末行四人；成十一行纵队，则末行十人。求兵数。

七、设 是两个正整数，证明: 的最大公因子,其中 是形如(是任意整数)的整数里的最小正数.

八、证明：存在无穷多个自然数n，使得n不能表示为

（a > 0是整数，p为素数）

的形式。

九、证明:  若方程  ( 是整数,)有有理数解,则此解必为整数.

十、证明:若， 则

十一、证明：设，c无平方因子，，证明：。

十二、设是奇素数,, 证明:  (mod ).

十三、设m > 1，模m有原根，d是的任一个正因数，证明：在模m的缩系中，恰有 个指数为d的整数，并由此推出模m的缩系中恰有个原根。

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

第一题：求同余式的解：

解答： 

 同余式有三个解

  即 

 又

 因此同余式的解为。

第二题：求高次同余式的解：

解答：

解：因

同余方程的解为

同余方程的解为

同余方程的解为

故原同余方程有4解。作同余方程组：，，,其中

由孙子定理得原同余方程的解为。

第三题：求高次同余式的解：

解答：010；

   118；

      228；

      340；

    454；

    570；

      688；

    7108；

    8130；

    9154；

10180；

11208=13x6；

12238；

因此，。

第四题：计算下列勒让德符号的值:, 

解答：

第五题：计算下列勒让德符号的值：，

解答：

==*=

=

=

第六题：韩信点兵：有兵一队，若列成五行纵队，则末行一人；成六行纵队，则末行五人；成七行纵队，则末行四人；成十一行纵队，则末行十人。求兵数。

解答：，，，

，，

， ，，

 兵数=2111+2310m，m是任何一个非负整数。

第七题：如a，b是两个正整数，则，其中是形如（x，y是任意整数）的整数里的最小正数。

证：，其中 

 若，等于是

 与题意是最小正数矛盾，所以

 即

 同理可证，于是 ，因此。

 又 ，。

 所以

第八题：证明：存在无穷多个自然数n，使得n不能表示为

（a > 0是整数，p为素数）

的形式。

证：存在无穷多个正整数k，使得是合数，对于这样的k， 不能表示为的形式，

事实上，若(k  1)2 = a2  p，则(k  1  a)( k  1  a) = p，得k  1  a = 1，k  1  a = p，即此与p为素数矛盾。

第九题：证明:  若方程  ( 是整数,)有有理数解,则此解必为整数解答：

证：设有理根，（p，q）=1，代入，得到

所以，但（p，q）=1，从而q

因此该有理根必为整数。

第十题：证明:若， 则。

证：

（a，b）=1

于是，

因此

第十一题：证明：设，c无平方因子，，证明：。

证：设，则，，(a1, b1) = 1，

由得a12b12c，a12c，

因为c无平方因子，所以a1 = 1，a = d，b = ab1，即。

第十二题：设是奇素数,, 证明:  (mod ).

证：如果n是模数p的二次剩余，则

有解，，于是

又，推出

因为p是奇素数，所以和只有一个成立。我们已经证明了，如果n是模数p的二次剩余，则成立，故1，，，

是的个解，而且是它的全部解。

于是模数p的缩系中个二次非剩余给出了的全部解。这样就证明了n是模数p的二次非剩余

则成立

因此

第十三题：设m > 1，模m有原根g，d是的任一个正因数，证明：在模m的缩系中，恰有 个指数为d的整数，并由此推出模m的缩系中恰有个原根。 

 证：设模m有原根g。因构成模m的缩系，

由得令

则

故恰有个t，使得(t, d) = 1，从而知故恰有 (d)个 ，使得 m(g ) = d。特别地，取d =  (m)知模m的缩系中恰有个原根。

第十四题：

设g是模m的一个原根，证明：若

通过模m的一个缩系。

证：是完全剩余系0，1，2，，

  又g是模m的一个原根

：对模数m两两不同余

又因为（g，m）=1

所以  

因此，通过模m的一个缩系。