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

1、福师期末考试初等数论复习题及参考答案本复习题页码标注所用教材为：教材名称单价作者版本岀版社初等数论14.20闵嗣鹤，严士健第三版高等教育岀版社复习题及参考答案一、填空(40%)1、求所有正约数的和等于15的最小正数为考核知识点：约数，参见P14-19 2、若b1,b2丄 L , b11是模ii的一个完全剩余系，则8b 1,8b21,L L ,8b111也是模11的剩余系考核知识点：完全剩余系，参见P54-573.模13的互素剩余系为考核知识点：互素剩余系，参见P584、自176到545的整数中是13倍数的整数个数为 考核知识点：倍数，参见 P11-135、如果p是素数，a是任意一个整数，则a被

2、P整除或者 考核知识点：整除，参见 P1-46、a，b的公倍数是它们最小公倍数的考核知识点：最小公倍数，参见P11-137、如果a,b是两个正整数,则存在整数q，r ,使a bq r, 0 r b .考核知识点：整除，参见 P1-48、如果 3n， 5n，则 15()n .考核知识点：整除，参见P1-4(10%)试证：6|n(n +1)(2 n+1)，这里n是任意整数。10 / 8考核知识点：整除的性质，参见 P9-12提示：2*(旳 +1)今 2 ”(昭 +1)(2« +1)i) 若越弓则弘(廉*叽2卄1)ii) 若耳张十贝y总+1 恥了” 今 3”仏 +1)(2« +

3、1)iii) 若' - 贝y '_ f.' + 2 - . F ;, +=3|2k + 1二3*3 十 1)(2沪 1)又/2 = 1目片®十1)2总十1)2三、(10%)假定a是任意整数，求证 a a 10(mod3)或2a a 0(mod3)考核知识点：二次同余式，参见 P88提示：要证明原式成立，只须证明3 a2 a 1,或者3 a2 a成立即可。四、(10%)设p是不小于5的素数，试证明 p2 1(mod 24)考核知识点：同余的性质，参见 P48-52 提示且"是不小于5的素数./ p = 3ki ; =1,2>1 展那=賢三

4、77;l(mod 3)=> 甘三又I ''' Ij-且芒是不小于5的素数.'心只能是奇数且=>卫=1, § 5 ,7(皿0砒) 即_ 1 ,'''.n 甘三 l(mo<i8):;-;亠| 即 - / I -,五、(15%)解同余式组5x 1(mod7)14x2(mod8)考核知识点：同余式，参见 P74-75提示 (14 , 8)=2 且 2 | 214x = 2(mod8) 有且仅有二个解解 7x= 1(mod4)? x = 3 (mod4) 6x = 10(mod8)的解为x= 3, 3+4(mod8)原同

5、余式组等价于x 3 mod 7x 3 mod8x 3 mod 7x 7 mod8分别解出两个解即可。六、(15%)证明形如4n1的整数不能写成两个平方数的和考核知识点：同余，参见 P48-53设n是正数，并且n 1(mod 4),如果n x2 y2,则因为对于模4, x,y只与0,1,2,-1 等同余,所以x2, y2只能与0,1同余，所以 x2 y20,1,2(mod 4)而这与n 1(mod 4)的假设不符即定理的结论成立初等数论复习题及参考答案二一、填空(40%)1 如果(a，b)1，则(ab，a b)=。考核知识点：最大公因数，参见P4-82、若b1,b2丄L ,b"是模11

6、的一个完全剩余系，则3b1 15,3 15,L L ,3b11 15也是模 11 的剩余系。考核知识点：完全剩余系，参见P54-573、 小于30的素数的个数是。考核知识点：素数，参见P14-194、 在整数中正素数的个数有 。考核知识点：素数，参见P14-195、24871与3468的最大公因数是 。考核知识点：最大公因数，参见P4-86、 9x 11y 100的正整数解的个数是 。考核知识点：二元一次不定方程，参见P25-317、 同余方程x4 x3 x2 x 1 0(mod5)的解的个数是0考核知识点：高次同余式的解法，参见P80-84&不定方程126x 102y 18的整数解为

7、 。考核知识点：二元一次不定方程，参见P25-31二、(10%)证明：若 m p mn pq，贝U m p mq np。考核知识点：整除，参见P1-4pq可知提示：由恒等式 mq np = (mn pq) (m p)(n q)及条件 m p mn m p mq np。三、(10%)若-则 5小"'考核知识点：整除，参见P1-4证明：J 1-' L' :':j-厂 J-i十(口上 (a,6)( 十妇)举乩幽)犠(佔十打關)上)随+上禺切T (壮)(耐"卸帕7(狞屁占)1=(HKA'/. (& +B.JW)(£1出)(此

8、十焜却叨(爲上)四、(10%)证明：若p是奇素数，N = 12( p 1),则(p 1)! p 1 (mod N)。考核知识点：同余式，参见 P74-75提示：由(p 1)!p 1 (mod p)，(p 1)! p1 (mod p1)以及(p, p 1) = 1 得(p 1)!p 1 (mod N)。p 1 (mod p(p 1)，又 2N = p(p 1)，故(p 1)!五、(15%)解同余方程组:3x 5y 38(mod 47)x y 10(mod 47)考核知识点：同余方程组，参见P74-75提示：消去y得8x 41 (mod 47)，解得x 11 (mod 47)，代入原方程组中的第

9、二式得 y 1 (mod 47)。故原方程组的解为 x 11 (mod 47)，y 1 (mod 47)。六、(15%)设m 3，g是模m的原根，X1, x2, , x (m)是模m的简化剩余系，证明：(m)(i ) g 21 (mod m);(ii) X1X2 x (m)1 (mod m)。考核知识点：原根及 n次剩余，参见P130-137解：(i)因g1, g2, , g 为模m的简化剩余系，设同余方程x2 1 (mod m) 的解为 x gr (mod 口)，即(gr)2 = g 2r 1 (mod m)，由此得 2r 0 (mod (m)，(m) 2r，又由m 3知(m)是偶数，得号|

10、，r或(m)。另一方面，同余方程 x2 1 (mod m)至少有解 x 1， 1 (mod m)，由 g (m) 1 (mod m)推出(m)gT 1 (mod m)。(ii)因g1, g2, , g (m)也为模m的简化剩余系，故12(、(m)( (m) 1)(m)(m)(m)(m)X1X2x (m) g1g2g (m)g 2g丁 gh1 (mod m)。初等数论复习题及参考答案三一、填空(40%)1、 如果ba，ab，则a与b的关系为。考核知识点：整除，参见 P1-42、 小于30的素数的个数为 。考核知识点：素数，参见 P14-193、 模7的互素剩余系为。考核知识点：互素剩余系，参见P

11、54-564、 如果，则不定方程ax by c有解.考核知识点：不定方程有解的条件，参见 P255、解同余式 58x 87(mod 47)。考核知识点：解同余式，参见P74-756、求最大公因数(168, 180,495)。考核知识点：最大公因数，参见P4-87、求同余式 7x 1(mod 31)。考核知识点：解同余式，参见P74-75&求不定方程15x 19y 1的整数解。考核知识点：解不定方程，参见P25-31二、(10%)解同余方程：2x 7y 5 (mod 12)。考核知识点：解同余方程，参见P74-75提示：因为(2, 12) = 2, (2, 7) = 1 5,故同余方程有

12、解，其解数为1 122 1 = 12, mod 12。先解同余方程 7y 5 (mod 2)，得 y 1 (mod 2)，写成 y 1 2t (mod 12)， t = 0, 1, 2, ,5，对于固定的 t ，解同余方程 2x 5 7(1 2t) 2 2t (mod 12)，得x 1t (mod 6), 写成 x1 t 6s (mod 12), s = 0, 1,故原方程组的解为x 1t 6s (mod 12),y1 2t (mod 12), s = 0, 1 , t= 0, 1, 2, ,5。x8(mod 15)三、 (10%)解同余方程组：x5(mod 8)x13(mod 25)考核知识

13、点：同余方程组,参见P74-75提示： 因为(15, 8) = 1 8 5，(15, 25) = 5 8 13，(8, 25) = 1 5 13，故原同余 方程组有解，解数唯一， mod 15, 8, 25 = 600。将第一个同余方程的解 x = 8 15ti, ti Z,代入第二个同余方程得 ti 3 (mod 8),即 ti = 3 8t2, t2 Z , x = 53120t2,代入第三个同余方程得 t23 (mod 5),即t2 = 3 5t3, t3 Z, x = 413600t3,所以原同余方程组的解为 x 413 (mod 600)。四、(10%)解同余方程：3x211x 20

14、0 (mod 105)。考核知识点：高次同余式的解法,参见 P80-84提示：因 105 = 357,同余方程 3x211x 20 0 (mod 3)的解为 x 1 (mod 3),同余方程 3x211x 38 0 (mod 5)的解为 x 0, 3 (mod 5),同余方程 3x211x20 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,5

15、8,100 (mod 105)。五、(15%)证明：同余方程a1x1 a2x2anxn b (mod m)有解的充要条件是(a1, a2, , an, m) = d b。考核知识点：同余式,参见 P74-75 提示：必要性显然,下证充分性。当 n = 1时,由定理 2知命题成立。 假设 n = k 时结论已真，考虑 a1x1 a2x2akxk ak + 1xk + 1 b (mod m)，令(a1, a2, , ak,m) = d1, (d1, ak + 1) = d,因为同余方程ak + 1xk + 1 b (mod d”有解，其解数为d, mod d1,记m = d1m1，则解数为dm1, mod m。现在固定一个解 xk + 1,由归纳假定知 aixi a2X2akxk b ak + ixk + i (mod m)有解，其解数为 di mk 1,mod m,从而 aixi a2X2akxk ak + ixk + i b (mod m)有解，其解数为dmi dimk i = d mk, mod m。由归纳原理知命题对于一切 n i成立。六、(i5%)设p和q = 4p i都是素数，证