福师期末考试《初等数论》复习题及参考答案

福师期末考试初等数论复习题及参考答案本复习题页码标注所用教材为：教材名称单价作者版本出版社初等数论14.20闵嗣鹤，严士健第三版高等教育出版社复习题及参考答案一一、填空(40%)1 、求所有正约数的和等于15的最小正数为 考核知识点：约数，参见P14-192、若是模11的一个完全剩余系，则 也是模11的 剩余系.考核知识点：完全剩余系，参见P54-573模13的互素剩余系为 考核知识点：互素剩余系，参见P584.自176到545的整数中是13倍数的整数个数为 考核知识点：倍数，参见P11-135、如果是素数,是任意一个整数,则被整除或者 考核知识点：整除，参见P1-46、的公倍数是它们最小公倍数的 .考核知识点：最小公倍数，参见P11-137、如果是两个正整数,则存在 整数,使,.考核知识点：整除，参见P1-48、如果，则15（ ）.考核知识点：整除，参见P1-4二、(10%)试证：6|n(n+1)(2n+1)，这里n是任意整数。考核知识点：整除的性质，参见P9-12提示： i)若 则 ii)若 则 iii)若 则 又 三、(10%)假定是任意整数，求证或考核知识点：二次同余式，参见P88提示:要证明原式成立，只须证明，或者成立即可。四、（10）设p是不小于5的素数，试证明考核知识点：同余的性质，参见P48-52提示： 且是不小于5的素数 又 且是不小于5的素数 只能是奇数且 即 即 五、(15%)解同余式组 考核知识点：同余式，参见P74-75提示 (14，8)=2 且 2 | 2 14x2(mod8) 有且仅有二个解解7x1(mod4) x3 (mod4) 6x10(mod8)的解为 x3，3+4(mod8)原同余式组等价于 或 分别解出两个解即可。六、（15%)证明形如的整数不能写成两个平方数的和.考核知识点：同余，参见P48-53设是正数,并且, 如果, 则因为对于模4,只与0,1,2,-1等同余, 所以只能与0,1同余, 所以 而这与的假设不符, 即定理的结论成立. 初等数论复习题及参考答案二一、填空(40%)1、如果，则= 。考核知识点：最大公因数，参见P4-82、若是模11的一个完全剩余系，则也是模11的 剩余系。考核知识点：完全剩余系，参见P54-573、小于30的素数的个数是 。考核知识点：素数，参见P14-194、在整数中正素数的个数有 。考核知识点：素数，参见P14-195、24871与3468的最大公因数是 。考核知识点：最大公因数，参见P4-86、的正整数解的个数是 。考核知识点：二元一次不定方程，参见P25-317、同余方程的解的个数是 0 。考核知识点：高次同余式的解法，参见P80-848、不定方程的整数解为 。考核知识点：二元一次不定方程，参见P25-31二、(10%)证明：若m - pmn + pq，则m - pmq + np。考核知识点：整除，参见P1-4提示：由恒等式mq + np = (mn + pq) - (m - p)(n - q)及条件m - pmn + pq可知m - pmq + np。三、（10）若 则 考核知识点：整除，参见P1-4证明： 四、(10%)证明：若p是奇素数，N = 1 + 2 + L + ( p - 1)，则(p - 1)! p - 1 (mod N)。考核知识点：同余式，参见P74-75提示：由(p - 1)! p - 1 (mod p)，(p - 1)! p - 1 (mod p - 1)以及(p, p - 1) = 1得(p - 1)! p - 1 (mod p(p - 1)，又2N = p(p - 1)，故(p - 1)! p - 1 (mod N)。五、(15%)解同余方程组：。考核知识点：同余方程组，参见P74-75提示：消去y得8x 41 (mod 47)，解得x 11 (mod 47)，代入原方程组中的第二式得y 1 (mod 47)。故原方程组的解为x 11 (mod 47)，y 1 (mod 47)。六、（15%)设m 3，g是模m的原根，x1, x2, L, xj(m)是模m的简化剩余系，证明：() -1 (mod m)；() x1x2Lxj(m) -1 (mod m)。考核知识点：原根及n次剩余，参见P130-137解： (i) 因g1, g2, L, gj(m)为模m的简化剩余系，设同余方程x2 1 (mod m)的解为x g r (mod m)，即(g r)2 = g 2r 1 (mod m)，由此得2r 0 (mod j(m)，j(m)2r，又由m 3知j(m)是偶数，得或j(m)。另一方面，同余方程x2 1 (mod m)至少有解x 1，-1 (mod m)，由gj(m) 1 (mod m)推出 -1 (mod m)。 (ii) 因g1, g2, L, gj(m)也为模m的简化剩余系，故x1x2Lxj(m) g1g2Lgj(m) -1 (mod m)。初等数论复习题及参考答案三一、填空(40%)1、如果，则a与b的关系为 。考核知识点：整除，参见P1-42、小于30的素数的个数为 。考核知识点：素数，参见P14-193、模7的互素剩余系为 。考核知识点：互素剩余系，参见P54-564、如果 ，则不定方程有解.考核知识点：不定方程有解的条件，参见P255、解同余式 。考核知识点：解同余式，参见P74-756、求最大公因数 。考核知识点：最大公因数，参见P4-87、求同余式 。考核知识点：解同余式，参见P74-758、求不定方程的整数解 。考核知识点：解不定方程，参见P25-31二、(10%)解同余方程：2x + 7y 5 (mod 12)。考核知识点：解同余方程，参见P74-75提示：因为(2, 12) = 2，(2, 7) = 15，故同余方程有解，其解数为1 122 -1 = 12，mod 12。先解同余方程7y 5 (mod 2)，得y 1 (mod 2)，写成y 1 + 2t (mod 12)，t = 0, 1, 2, L,5，对于固定的t，解同余方程2x 5 - 7(1 + 2t) -2 - 2t (mod 12)，得x -1 - t (mod 6)， 写成x -1 - t + 6s (mod 12)，s = 0, 1，故原方程组的解为x -1 - t + 6s (mod 12)，y 1 + 2t (mod 12)，s = 0, 1，t = 0, 1, 2, L,5。三、(10%)解同余方程组：考核知识点：同余方程组，参见P74-75提示：因为(15, 8) = 18 - 5，(15, 25) = 58 - 13，(8, 25) = 15 - 13，故原同余方程组有解，解数唯一，mod 15, 8, 25 = 600。将第一个同余方程的解x = 8 + 15t1，t1Z，代入第二个同余方程得t1 3 (mod 8)，即t1 = 3 + 8t2，t2Z，x = 53 + 120t2，代入第三个同余方程得t2 3 (mod 5)，即t2 = 3 + 5t3，t3Z，x = 413 + 600t3，所以原同余方程组的解为x 413 (mod 600)。四、(10%)解同余方程：3x2 + 11x - 20 0 (mod 105)。考核知识点：高次同余式的解法，参见P80-84提示：因105 = 357，同余方程3x2 + 11x - 20 0 (mod 3)的解为x 1 (mod 3)，同余方程3x2 + 11x - 38 0 (mod 5)的解为x 0，3 (mod 5)，同余方程3x2 + 11x - 20 0 (mod 7)的解为x 2，6 (mod 7)，故原同余方程有4解，mod 105。作同余方程组：x b1 (mod 3)，x b2 (mod 5)，x b3 (mod 7)，其中b1 = 1，b2 = 0，3，b3 = 2，6，由孙子定理得原同余方程的解为x 13，55，58，100 (mod 105)。五、(15%)证明：同余方程a1x1 + a2x2 + L + anxn b (mod m)有解的充要条件是(a1, a2, L, an, m) = db。考核知识点：同余式，参见P74-75提示：必要性显然，下证充分性。当n = 1时，由定理2知命题成立。假设n = k时结论已真，考虑a1x1 + a2x2 + L + akxk + ak + 1xk + 1 b (mod m)，令(a1, a2, L, ak, m) = d1，(d1, ak + 1) = d，因为同余方程ak + 1xk + 1 b (mod d1)有解，其解数为d，mod d1，记m = d1m1，则解数为dm1，mod m。现在固定一个解xk + 1，由归纳假定知a1x1 + a2x2 + L + akxk b - ak + 1xk + 1 (mod m)有解，其解数为d1 mk -1，mod m，从而a1x1 + a2x2 + L + akxk + ak + 1xk + 1 b (mod m)有解，其解数为dm1d1mk -1 = dmk，mod m。由归纳原理知命题对于一切n 1成立。六、（15%)设p和q = 4p + 1都是素数，证明：2是模q的一个原根。考核知识点：原根，参见P12