1、初等数论练习题一 一、填空题 1、 d(2420)=12; (2420)=_880_ 2、设 a,n 是大于 1 的整数，若 an-1 是质数，则 a=_2. 3、模 9 的绝对最小完全剩余系是 _-4， -3， -2， -1,0,1,2,3,4. 4、 同余方程 9x+12 0(mod 37)的解是 x 11(mod 37)。 5、 不定方程 18x-23y=100 的通解是 x=900+23t， y=700+18t tZ。 . 6、 分母是正整数 m 的既约真分数的个数为 _(m)_。 7、 18100 被 172 除的余数是 _256。 8、 10365=-1。 9、若 p 是素数，则同
2、余方程 x p 1 1(mod p)的解数为 p-1 。 二、计算题 1、解同余方程 ： 3x211x20 0 (mod 105)。 解 ： 因 105 = 357， 同余方程 3x211x20 0 (mod 3)的解为 x 1 (mod 3)， 同余方程 3x211x38 0 (mod 5)的解为 x 0， 3 (mod 5)， 同余方程 3x211x20 0 (mod 7)的解为 x 2， 6 (mod 7)， 故原同余方程有 4 解。 作同余方程组： x b1 (mod 3)， x b2 (mod 5)， x b3 (mod 7)， 其中 b1 = 1， b2 = 0， 3， b3 =
3、2， 6， 由孙子定理得原同余方程的解为 x 13， 55， 58， 100 (mod 105)。 2、判断同余方程 x2 42(mod 107)是否有解？ 11 0 74217271 0 711 0 7713231 0 711 0 7311 0 721 0 771 0 731 0 721 0 77321 0 7422110721721107213)(）（）（）（）（），（）（）（）（），（）（）（）（）（解： 故同余方程 x2 42(mod 107)有解。 3、求（ 127156+34） 28 除以 111 的最小非负余数。 2 解：易知 1271 50（ mod 111）。 由 502 5
4、8（ mod 111） , 503 58 50 14（ mod 111）， 509 143 80（ mod 111）知 5028 （ 509） 3 50 803 50 803 50 68 50 70（ mod 111） 从而 5056 16（ mod 111）。 故 （ 127156+34） 28 （ 16+34） 28 5028 70（ mod 111） 三、证明题 1、已知 p 是质数，（ a,p） =1，证明： （ 1）当 a 为奇数时， ap-1+(p-1)a 0 (mod p)； （ 2）当 a 为偶数时， ap-1-(p-1)a 0 (mod p)。 证明：由欧拉定理知 ap-1
5、1 (mod p)及 (p-1)a -1 (mod p)立得（ 1）和（ 2）成立。 2、设 a 为正奇数， n为正整数，试证 n2a 1(mod 2n+2)。 （ 1） 证明 设 a = 2m 1，当 n = 1 时，有 a2 = (2m 1)2 = 4m(m 1) 1 1 (mod 23)，即原式成立。 设原式对于 n = k 成立，则有 ka2 1 (mod 2k + 2) ka2 = 1 q2k + 2， 其中 qZ，所以 12ka = (1 q2k + 2)2 = 1 q 2k + 3 1 (mod 2k + 3)， 其中 q 是某个整数。这说明式 (1)当 n = k 1 也成立
6、。 由归纳法知原式对所有正整数 n 成立 。 3、设 p 是一个素数，且 1 k p-1。证明： kp1C （ -1 ） k(mod p)。 证明：设 A= ! )()2(1C1 k kpppkp ）（得： k! A =（ p-1） (p-2)（ p-k）（ -1） (-2)（ -k） (mod p) 又（ k!， p） =1，故 A = kp1C （ -1 ） k(mod p) 4、设 p 是不等于 3 和 7 的奇质数，证明： p6 1(mod 84)。 说明：因为 84=4 3 7，所以，只需证明： p6 1(mod 4) p6 1(mod3) p6 1(mod 7) 同时成立即可。 证
7、明：因为 84=4 3 7及 p 是不等于 3 和 7 的奇质数，所以 3 （ p， 4） =1，（ p， 3） =1，（ p， 7） =1。 由欧拉定理知： p(4) p2 1(mod 4)，从而 p6 1(mod 4)。 同理可证： p6 1(mod3) p6 1(mod 7)。 故有 p6 1(mod 84)。 注：设 p 是不等于 3 和 7 的奇质数，证明： p6 1(mod 168)。（见赵继源 p86） 初等数 论练习题二 一、填空题 1、 d(1000)=_16_； (1000)=_2340_. 2、 2010!的标准分解式中，质数 11 的次数是 199_. 3、费尔马 (F
8、ermat)数是指 Fn= n2 +1,这种数中最小的合数 Fn中的 n=5。 4、 同余方程 13x 5(mod 31)的解是 x 29(mod 31)_ 5、 分母不大于 m的既约真分数的个数为 (2)+ (3)+ (m)。 6、设 7 (80n-1),则最小的正整数 n=_6_. 7、使 41x+15y=C 无非负整 数解的最大正整数 C=_559_. 8、 10146=_1_. 9、若 p 是质数， np 1， 则 同余方程 x n 1 (mod p) 的解数为 n . 二、计算题 1、试求 200420032002 被 19 除所得的余数。 解 ： 由 2002 7 (mod 19)
9、 20022 11(mod 19) 20023 1 (mod 19) 又由 20032004 22004（ 22） 1002 1 (mod 3)可得： 200420032002 20023n+1 (20023)n 2002 7(mod 19) 2、 解同余方程 3x14 4x10 6x 18 0 (mod 5)。 解：由 Fermat 定理， x5 x (mod 5)， 因此，原同余方程等价于 2x2 x 3 0 (mod 5) 将 x 0， 1， 2 (mod 5)分别代入上式进行验证，可知这个同余方程解是 x 1 (mod 5)。 3、已知 a=5， m=21,求 使 a x 1 (mod
10、 m)成立的最小自然数 x。 解：因为 （ 5,21） =1，所以有欧拉定理知 5(21) 1(mod 21)。 又由于 (21)=12，所以 x|12，而 12 的所有正因数为 1,2,3,4,6,12。 于是 x 应为其中使 5 x 1 (mod 12)成立的最小数，经计算知： x=6。 4 三、证明题 1、试证 13|(54m+46n+2000)。 (提示：可取模 13 进行计算性证明 ) 证明： 54m+46n+2000 252m+642n+2000 （ -1） 2m+（ -1） 2n+2000 2002 0(mod 13)。 2、证明 Wilson 定理的逆定理：若 n 1，并且 (
11、n 1)! 1 (mod n)，则 n 是素数。 证明：假设 n 是合数，即 n = n1n2， 1 1， 且 (n-1)!+1 0(mod n),则 n为 素数 。 6、 3103 被 11 除所得余数是 _5_。 7、 9760=_-1_。 三、计算题 1、判定 ( ) 2x3 x2 3x 1 0 (mod 5)是否有三个解； ( ) x6 2x5 4x2 3 0 (mod 5)是否有六个解？ 解： ( ) 2x3 x2 3x 1 0 (mod 5)等价于 x3 3x2 4x 3 0 (mod 5)，又 x5 x = (x3 3x2 4x 3)(x2 3x 5) + (6x2 12x 15
12、)，其中 r(x) = 6x2 12x 15 的系数不都是 5的倍数，故原方程没有三个解。 ( ) 因为这是对模 5 的同余方程，故原方程不可能有六个解。 2、 设 n 是正整数，求 1223212 C,C,C nnnn 的最大公约数。 解：设 1212232121223212 2CCC)C,C,(C nnnnnnnnn d ，由知 d22n1， 设 2k|n 且 2k+1 | n，即 2k +1|n ， 则由 2k +1| 1122112 C2C2C | i ni nkn in及， i = 3, 5, , 2n 1 得 d = 2k + 1。 3、已知 a=18,m=77,求 使 ax 1
13、(mod m)成立的最小自然数 x。 解：因为（ 18,77） =1，所以有欧拉定理知 18(77) 1(mod 77)。 又由于 (77)=60，所以 x|60，而 60 的所有正因数为 1,2,3,4,5,6,10,12,15,20,30, 60。 于是 x 应 为其中使 18x 1 (mod 77)成立的最小数，经计算知： x=30。 6 四、证明题 1、 若质数 p 5,且 2p+1 是质数，证明： 4p+1 必是合数。 证明：因为 质数 p 5,所以（ 3， p） =1，可设 p=3k+1 或 p=3k+2。 当 p=3k+1 时， 2p+1=6k+3 是合数，与题设矛盾，从而 p=
14、3k+2， 此时 2p+1 是形如 6k+5 的质数，而 4p+1=12k+9=3(4k+3)是合数。 注 ：也可设 p=6k+r， r=0,1,2,3,4,5。再分类讨论。 2、设 p、 q 是两个大于 3 的质数，证明： p2 q2(mod 24)。 证明：因为 24=3 8，（ 3,8） =1，所以只需证明： p2 q2(mod 3) p2 q2(mod 8)同时成立。 事实上， 由于（ p， 3） =1，（ q， 3） =1，所以 p2 1(mod 3) ， q2 1(mod 3)， 于是 p2 q2(mod 3)，由于 p， q 都是奇数，所以 p2 1(mod 8) ， q2 1(
15、mod 8)， 于是 p2 q2(mod 8)。故 p2 q2(mod 24)。 3、若 x,y R+ ， （ 1）证明： xy xy； （ 2）试讨论 xy与 xy的大小关系。 注：我们知道， x y x+ y， x+y x+y。此题把加法换成乘法又如何呢？ 证明： （ 1） 设 x=x+ ,0 0 是偶数， a1, a2, , am与 b1, b2, , bm都是模 m 的完全剩余系，证明： a1 b1, a2 b2, , am bm不是模 m 的完全剩余系。 证明：因为 1, 2, , m与 a1, a2, , am都是模 m 的完全剩余系，所以 mimiimmmia1 1 22)1(m
16、od m)。 (1) 同理 mi imb1 2(mod m)。 (2) 如果 a1 b1, a2 b2, , am bm是模 m 的完全剩余系，那么也有 mi ii mba1 2)( (mod m)。 联合上式与式 (1)和式 (2)，得到 0222 mmm (mod m)， 这是不可能的，所以 a1 b1, a2 b2, , am bm不能是模 m 的完全剩余系。 4、证明： （ 1） 2730 x13-x； （ 2） 24 x(x+2)(25x2-1)； （ 3） 504 x9-x3； （ 4）设质数 p 3，证明： 6p xp-x。 证明：（ 1）因为 2730=2 3 5 7 13，
17、2,3,5， 7,13 两两互质，所以： 由 x13-x=x (x12-1) 0 (mod 2)知 ： 2 x13-x； 13 x13-x； 由 x13-x=x (x12-1)=x(x2-1)(x2+1)(x8+x4+1) 0 (mod 3)知 ： 3 x13-x； 由 x13-x=x (x12-1)=x(x4-1)(x8+x4+1) 0 (mod 5)知 ： 5 x13-x； 10 由 x13-x=x (x12-1)=x(x6-1)(x6+1) 0 (mod 7)知 ： 7 x13-x。 故有 2730 x13-x。 同理可证（ 2）、（ 3）、（ 4）。 初等数论练习题五 一、单项选择题
18、1、设 x、 y 分别通过模 m、 n的完全剩余系，若（ C ）通过模 mn 的完全剩余系。 A. m、 n都是质数，则 my nx B. m n，则 my nx C. （ m， n） =1，则 my nx D. （ m， n） =1，则 mx ny 2、 1 3 5 2003 2005 2007 2009 2011 标准 分解式中 11 的幂指数是 ( A )。 A.100 B.101 C.99 D.102 3、 n为正整数，若 2n-1 为质数，则 n 是 ( A )。 A.质数 B.合数 C.3 D.2k(k 为正整数 ) 4、从 100 到 500 的自然数中，能被 11 整除的数的个
19、数是 ( B )。 A.33 B.34 C.35 D.36 5、模 100 的最小非负简化剩余系中元素的个数是 ( C )。 A.100 B.10 C.40 D.4 二、填空题 1、同余方程 ax+b 0(modm)有解的充分必要条件是 (a,m) b。 2、高斯称反转定律是数论的酵母，反转定律是 指设 p 与 q 是不相同的两个奇质数， )()( 2121)1(qppqqp 3、 20122012 被 3 除所得的余数为 _1_。 4、设 n 是大于 2 的整数，则 (-1) (n)=_1_。 5、单位圆上的有理点的坐标是 )()(2222 2222 2222 2,2 ba abba baba baba ab 或， 其中 a 与 b 是不 全为零的整数 。 6、若 3258 a 恰好是一个正整数的平方，则 a 的最小值为 362。 7、已知 2011 是一素数，则 201172=_-1_。 三、计算题
