数论之同余(二)

数论-同余（二）一同余练习1. 设是不被整除的偶数，则的十位数字为 ；的百位数字为 .2. 已知，求两位数.3. 设都是正整数，则【证明】记由于（a,b）|a及（a,b）|b，易知及，故，另一方面设m模d的阶是k，则由推出，k|a及k|b，故k|（a，b）.因此综合两方面可知，证毕.4. 若正整数，满足，证明：.5. 求最小的正整数，使得存在正整数满足。解：当时，若存在，使得，则，且，若为奇数，则，从而，又为正整数，所以；若为偶数，则，从而，所以，综上知，。又当时，所以的最小值为。6. 求最小的质数，使得不存在自然数满足。解：注意到，。 下面证明：不存在自然数，使得。情形一：若，显然，两边模有，故为偶数，这时，显然，两边模有，故也为偶数，设，则，所以，解得，无解。情形二：若，则，两边模有，但模只可能等于或，矛盾。综上知满足条件的最小素数。7. 证明：若为素数，且，则.8. 证明：在中至少有一个数能被整数，其中为大于的奇数。证明：考察数： 它们被除的余数设为：因为是大于的奇数，所以不能整除，。所有这个余数只有这种情形，因而有两个余数相等，不妨设为，。于是，即，因为，所以。由于，则是中的一个。问题得证。9.（1）设是奇素数，证明：的任一素因了具有形式是正整数.证明：设是的任一素因子，则.设2模q的阶是k，则由知k|p，故k=1或p（因p是素数，这是能确定阶k的主要因素）.显然k1，否则这不可能，因此k=p.现在由费马小定理推出因p、q都是奇数，故q1=2px（x是个正整数），证毕.（2）设是奇素数，证明：的素因子或者是，或者具有形式（是正整数）。证明：因是奇数，故其素因子必是奇素数，设为其任意一个素因子，则.于是有，又由知，可得。记为模的阶，则有。由且是奇素数知，或，或，或。易知；当时，可得；当或时，可得（其中为正整数）。10. 证明：费马数的任意一个约数都满足。证明：只需证明费马数的任意一个素因子都满足.显然。设模的阶为，由得，故，从而，所以是的方幂，设，其中，若，则由知，结合知，这不可能。故只有，即。又，所以，即。二同余方程定理1. 设，则同余方程有解的充要条件是。定理2. 设，则同余方程恰有个解： 其中是的唯一解。定理3（中国剩余定理）设是个两两互素的正整数，则同余方程组有唯一解：，其中.例1：解同余方程组。2. 求出最小的正整数，它的是整数的平方，它的是整数的立方，它的是整数的五次方.3. 设，证明：一定存在个连续的正整数，使其中任何一个都不是某个质数的整数幂.4. 设是两两互素的正整数，求证：存在个相邻整数，使得第个整数能被整除.三不定方程中的同余法1. 求证：存在无穷多个这样的正整数，它们不能表示成少于十个奇数的平方和分析：对于否定性问题，我们常利用同余解：设正整数能够表示成其中为奇数，若，则由及知，即若，则由及知，从而这说明若，则综上所述，被8除余2，被9除余3，即具有形式的正整数便不能表示成，故命题得证评注：对于某些问题，常常需要多次选择不同的模进行同余处理2. 试证：当时，不存在个连续自然数，使得它们的平方和是完全平方数.解析：设是非负整数.假若结论不成立,即存在使即 记 则当时，分别由 和令，代入得即把代入后将分别得到但这是不可能的，故. 当时,由得 若则由知,，由于的任意性，所以只能有因此要使成立,只能,于是由知有,这是不可能的,故同理可证若,则由可得,这是不可能的,故综上,命题得证.3. 求最大的正整数，使得方程组有整数解（2003年越南数学奥林匹克）分析：我们利用平方数的性质处理问题解：所求最大正整数当时，进而得易得所给方程组有整数解当时，则，奇偶交替出现从而且若，为奇数，则由是偶数得，而由即得出式矛盾若，为偶数，则，为奇数同理可得出式矛盾所以无解而当时显然无解综上可得所求最大正整数4. 证明：不定方程无整数解解析：给我们的第一个印象是同为奇数或同为偶数。若同为偶数，则也就是，进一步有为奇数，因为奇数的平方模8余1，矛盾。若同为奇数，则需进一步讨论，关键是取模为多少比较好讨论。结合费马小定理如，则，从而，但是。比较两者我们就可以到相应的结论5. 证明：方程没有正整数解（2004年韩国数学奥林匹克）分析：我们选择适当的模对进行分类处理问题证明：当时，设，而方程左边，矛盾所以此时无解当时，设，而，均为完全平方数但由知不可能是完全平方数所以此时无解当时，设时，令，则令，则与类似，均为完全平方数其中不可能是完全平方数，矛盾所以此时无解综上所述，原方程无正整数解评注：方程右边可因式分解，而左边系数为3，因而选择模3对进行分类处理6. 求方程的正整数解。解析：首先，从而，为偶数。方程可以转化，。所以，即得，下面研究，当时，通过尝试的方法可以得到：，在考虑模7的余数，矛盾。所以，由此可以得到方程的解为。7. 、是质数，解方程（2004年巴尔干地区数学奥林匹克）分析：我们要充分利用、是质数的条件解：（）若，则显然不可能（）若，则而、是质数，由费马小定理，得即由费马小定理，得即若，则由知，由知即又是质数且，故是奇质数从而，不是质数矛盾所以此时无解若，则由知故这与（）矛盾若，则由、，得当时，由，得质数不满足当时，由，得质数或3不满足当时，由，得质数不满足当时，由，得质数或3仅有满足，且满足原方程当时，由，得质数或7不满足当时，由，得质数满足，且满足原方程综上，为所求方程的解评注：在处理有关质数幂的问题中，费马小定理常发挥重要作用8. 求所有满足方程的正整数解解析：首先从同余的角度可以发现