(解答题36道)第四章 同余式.doc

2011年2月初等数论题库第四章 同余式三、解答题1、设，与是正整数，又设，证明同余方程的一切解都可以表示成，其中满足同余方程。解：设是的任意一个解，则一次同余方程有解，再由得，即可以表示成，其中满足同余方程；反之，易知如此形式的是的解。2、解同余方程组解：这同余方程组的解与同余方程组的解相同， 但第二个同余方程可化为,第四个同余方程可化为,与矛盾，所以原同余方程组无解.3、设素数,求同余方程的解解：同余方程可写为由于,所以上式等价于或因此，对任意的解为解数为2.4、求同余式解：无公解有唯一解以代入得但，故，因此是的唯一解将代入得但，故，设是的唯一解。5、.解： 因为 ,所以同余式有3个解.将同余式化简为等价的同余方程. 我们再解不定方程,得到一解. 于是定理4.1中的. 因此同余式的3个解为, , .6、.解：因为,所以同余式有3个解. 将同余式化简为等价的同余方程. 我们再解不定方程, 得到一解. 于是定理4.1中的. 因此同余式的3个解为, , .7、.解: 因为(7,8,9)=1,所以可以利用定理5.1.我们先解同余式,得到.于是所求的解为8、判定是否有3个解解：等价于，又，其中的系数的都不是5的倍数，故方程没有3个解9、解同余式 解： 10、同余方程的解的个数. 解：因为 所以等价于 （1） （2） （3）解同余方程（1）（2）（3）得到 所以原方程的解得个数有2*2*1=4个。11、解同余式解：同余式只有一个解11是素数12、解同余方程组 解：利用孙子定理有，, 13、求整数，它被3，5，7除的余数分别是1，2，3。解：是同余方程组的解.在孙子定理中，取， 则因此所求的整数.14、求的解解：；而所以同理而所以，而所以所以15、解同余方程组解：取，都是素数，满足条件。我们来求.由于知，因此可取.由知，因此可取，由知，因此可取.由知，因此可取.所以同余方程的解为：，即16、解同余方程 解：因为，所以同余方程等价于同余方程组 其中或，或或.利用孙子定理，取则17、解同余式解： 同余式只有一个解 是素数 18、解同余方程：解：若，则成立，反之，若，则成立；19、解同余方程解：由Fermat定理得，因此，原同余方程等价于将分别代入方程中进行检验，可得原同余方程的解是：20、解同余方程解：方程有一解，故，, 解，得， ， ，,解，得 故，再解，得故原方程的解为21、1、求同余方程的所有解.解：因为且整除 所以同余方程恰有三个解.先求同余方程的唯一解，显然所以原同余方程的三个解为2、求一次同余方程组解：由于、两两不互质，所以不能直接用孙子定理，原一次同余方程组与一次同余方程组等价显然，去掉相同的一次同余方程后，此一次同余方程组又与一次同余方程组等价，由于能被整除，此一次同余方程组又与一次同余方程组等价此时两两互质，由孙子定理知，原一次同余方程组有唯一解求得所以为原一次同余方程组的解. 3、解同余方程组解:再代入即方程组的解是4、解同余方程.解： 5、 解同余式. 解：因为,所以同余式有解,而且解的个数为. 又同余式等价于即. 我们利用解不定方程的方法得到它的一个解是,即定理4.1中的 . 因此同余式的个解为 ,.6、韩信点兵：有兵一队，若列成五行纵队，则末行一人，成六行纵队，则末行五人，成七行纵队，则末行四人，成十一行纵队，则末行十人，求兵数.解：，此时： 得故：又 7、解同余方程.解： 原同余方程等价于同余方程组， (1). (2)先解同余方程(1).容易验证，同余方程的解是.令并代入方程(1)，得到 ， (3)容易看出，这是一个对于任何整数都成立的同余式，所以，方程(3)的解是，于是方程(1)的解是. (4)再解同余方程(2).用去验证，得到(2)的解是.因此，原同余方程的解是下面六个同余方程组的解：，.利用孙子定理解这六个方程组，记则.将和的不同取值代入，得到所求的解是，.8、解同余方程.（理由：考察孙子定理，解同余方程组.）解：因为，所以，原同余方程等价于同余方程组分别解同余方程，得到解这样，原同余方程的解可由下面的方程组决定：其中.利用孙子定理，令则 将所有可能的取值带入上式，得到原方程的全部解是9、判定同余方程是否有三个解.（理由：考察素数模的同余方程的解的个数，应用第四节的定理及定理4.）解：因为，所以，原方程与即等价.由于，所以，由定理4可知，原方程的解数小于.10、有一对士兵，若三人一组 则余一人，若五人一组，则余2人，若十一人一组，则余3人，已知这对士兵不超过170人，问这对士兵有几人？解：设士兵有人，则由题意得， 由孙子定理得 故人.12、求一个最小的自然数n，使得它的是一个平方数，它的是一个立方数，它的是一个5次方数.解：可设，由条件得由孙子定理得故.13、解同余方程组 解：再代入即方程组的解是14、证明不定方程没有整数解.证明：取.因为，于是同余式无解，由此知原方程无整数解.15、解同余方程.解：因，先解，用逐一代入法得解；再解，用逐一代入法得的解为，对于，令代入得，于是，即是的一个解，对于，令代入得，于是，即是的一个解； 最后构造同余方程组，由孙子定理得的两个解.16、设是素数，证明：.是同余方程的解.解：首先易知是整数，又由知方程解唯一，故只须将代入验证它是同余方程的解即可.17、证明：同余方程有解的充要条件是.若有解，则恰有个解，.解：必要性显然，下证充分性.当时，由定理2知命题成立.假设时结论已真，考虑，令，因为同余方程有解，其解数为，记，则解数为，.现在固定一个解，由归纳假定知 有解，其解数为，从而 有解，其解数为，.由归纳原理知命题对于一切成立.18、解同余方程：. 解：因 同余方程的解为， 同余方程的解为， 同余方程的解为， 故原同余方程有解，. 作同余方程组：，其中由孙子定理得原同余方程的解为.19、解同余方程组：解：因为，.故原同余方程组有解，解数唯一.将第一个同余方程的解 ，代入第二个同余方程得，即，代入第三个同余方程 得，即， 所以原同余方程组的解为.20、讨论并解答：解：且 且 且 原同余式组等价于 ，由得同理，=1，=1 21、解同余式解： 22、解同余式 （用三种方法解）解：同余式只有一个解法1：11是素数， 法2：法3：（求解不定方程）23、解同余式 解：设由定理3知解同余式可先分别解以下两同余式容易验证第一个同余式有解第二个同余式有解由孙子定理，当取时，得到的个解24、求相邻的四个整数，它们依次可被整除解：设这四个相邻的整数是，按要求应满足, , .所以，这是一个解同余方程组问题，这里两两既约.满足定理1的条件.,由知因此可取，由知因此可取由知 因此可取，由知 因此可取，因而由定理1知 所以满足要求的四个相邻整数有无穷多组，它们是 ,最小的这样的四个相邻的正整数是.25、解同余式，解：上式与同余式组等价，容易证第一个同余式有两个解即：，第二个同余式有三个解即，故题中所求同余式，有6个解，即同余式组的解， 由孙子定理得，以，的值分别代入即得全部解：26、求同余方程的解.解：当时，解数为，当时，解数为,当 时，同余方程可写为由于是解时，必可表为.带入上式得即所以必有因此，解必满足所以原方程的解是解数为.27、解同余方程组解：由题意可知： 解得得即为所求28、求 的整数解解： 由孙子定理得： 所有整数解为：29、解同余方程 解：同余方程(6)即是解同余方程 ，得到，因此方程的解是 30、解同余方程组 解：消去得解得 代入原方程组中的第二式得 即31、 解：有则所以32、解同余方程的解 解：， ， ， 33、解同余方程：解：因，同余方程的解为同，同余方程