初等数论练习题答案

更新时间:2024-01-26 05:36:01 阅读量: 教育文库 文档下载

说明:文章内容仅供预览,部分内容可能不全。下载后的文档,内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的,是否完整无缺。

初等数论练习题一

一、填空题

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 t?Z。. 6、分母是正整数m的既约真分数的个数为_?(m)_。 7、18100被172除的余数是_256。 8、??65?? =-1。 ?103?

9、若p是素数,则同余方程x p ? 1 ?1(mod p)的解数为 p-1 。 二、计算题

1、解同余方程:3x2?11x?20 ? 0 (mod 105)。

解:因105 = 3?5?7,

同余方程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解。

作同余方程组: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)。 2、判断同余方程x2≡42(mod 107)是否有解?

237)()()1071071071071073?1107?17?1107?1 ??2310727107222?()??1,()?(?1)()??()?1,()?(?1)22()??()??1107107331077742?()?11072?3?7解:(42)?()?( 故同余方程x2≡42(mod 107)有解。

3、求(127156+34)28除以111的最小非负余数。

解:易知1271≡50(mod 111)。

由502 ≡58(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)≡0 (mod p); (2)当a为偶数时,ap-1-(p-1)≡0 (mod p)。

证明:由欧拉定理知ap-1≡1 (mod p)及(p-1)≡-1 (mod p)立得(1)和(2)成立。 2、设a为正奇数,n为正整数,试证a2na

aa

≡1(mod 2n+2)。 …………… (1)

证明 设a = 2m ? 1,当n = 1时,有

a2 = (2m ? 1)2 = 4m(m ? 1) ? 1 ? 1 (mod 23),即原式成立。 设原式对于n = k成立,则有 其中q?Z,所以 a2k?1a2k? 1 (mod 2k + 2) ?a2= 1 ? q2k + 2,

k= (1 ? q2k + 2)2 = 1 ? q ?2k + 3 ? 1 (mod 2k + 3),

其中q ?是某个整数。这说明式(1)当n = k ? 1也成立。 由归纳法知原式对所有正整数n成立。

k3、设p是一个素数,且1?k?p-1。证明:Ckp?1 ? (-1 )(mod p)。

(p?1)(p?2)?(p?k) 证明:设A=Ckp?1? 得:

k! k!·A =(p-1)(p-2)…(p-k)≡(-1)(-2)…(-k)(mod p)

k

又(k!,p)=1,故A = Ck ? (-1 )(mod p) p?14、设p是不等于3和7的奇质数,证明:p6≡1(mod 84)。 说明:因为84=4×3×7,所以,只需证明:

p6≡1(mod 4) p6≡1(mod3) p6≡1(mod 7) 同时成立即可。 证明:因为84=4×3×7及p是不等于3和7的奇质数,所以

2

(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、费尔马(Fermat)数是指Fn=22+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、??46??=_1__. ?101?n9、若p是质数,n?p ? 1,则同余方程x n ? 1 (mod p) 的解数为n . 二、计算题

20031、试求20022004被19除所得的余数。

解:由2002≡7 (mod 19) 20022≡11(mod 19) 20023≡1 (mod 19) 又由20032004≡22004≡(22)1002≡1 (mod 3)可得:

200320022004≡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 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。

3

三、证明题

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,并且(n ? 1)! ? ?1 (mod n),则n是素数。 证明:假设n是合数,即n = n1n2,1 < n1 < n,由题设易知(n ? 1)! ? ?1 (mod n1),得

0 ? ?1 (mod n1),矛盾。故n是素数。

3、证明:设ps表示全部由1组成的s位十进制数,若ps是素数,则s也是一个素数。 证明:假设s是合数,即s=ab,1

10s?1(10a)b?110a?1 ps?11?1????M,其中M>1是正整数。 ???999s由pa>1也是正整数知ps是合数,这与题设矛盾。故s也是一个素数。

4、证明:若2p ? 1是奇素数,则 (p!)2 ? (?1)p ? 0 (mod 2p ? 1)。

证明:由威尔逊定理知 ?1 ? (2p)! = p!(p ? 1)?(2p) ? (?1)p(p!)2(mod 2p ? 1),

由此得(p!)2 ? (?1)p ? 0 (mod 2p ? 1)。

5、设p是大于5的质数,证明:p4≡1(mod 240)。(提示:可由欧拉定理证明)

证明:因为240=23×3×5,所以只需证:p4≡1(mod 8),p4≡1(mod 3),p4≡1(mod 5)即

可。事实上,由?(8)=4,?(3)=2,?(5)=4以及欧拉定理立得结论。

初等数论练习题三

一、单项选择题

1、若n>1,?(n)=n-1是n为质数的( C )条件。

A.必要但非充分条件 B.充分但非必要条件 C.充要条件 D.既非充分又非必要条件 2、设n是正整数,以下各组a,b使为既约分数的一组数是( D )。 A.a=n+1,b=2n-1 B.a=2n-1,b=5n+2 C.a=n+1,b=3n+1 D.a=3n+1,b=5n+2 3、使方程6x+5y=C无非负整数解的最大整数C是( A )。 A.19

B.24 C.25

D.30

ba4、不是同余方程28x≡21(mod 35)的解为( D )。

A.x≡2(mod 35) B. x≡7(mod 35) C. x≡17(mod 35) D. x≡29(mod 35)

4

5、设a是整数,(1)a≡0(mod9) (2)a≡2010(mod9) (3)a的十进位表示的各位数字之和可被9整除

(4)划去a的十进位表示中所有的数字9,所得的新数被9整除 以上各条件中,成为9|a的充要条件的共有( C )。 A.1个

B.2个 C.3个 D.4个

二、填空题

1、σ(2010)=_4896____;?(2010)=528。

202、数C100的标准分解式中,质因数7的指数是_3。

3、每个数都有一个最小质因数。所有不大于10000的合数的最小质因数中,最大者是97。 4、同余方程24x≡6(mod34)的解是x1≡13(mod34) x2≡30(mod34)_。 5、整数n>1,且(n-1)!+1≡0(mod n),则n为素数。 6、3103被11除所得余数是_5_。 7、??60??=_-1_。 ?97?三、计算题

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),其中r(x) = 6x2 ? 12x ? 15的系数不都是5的倍数,故原方程没有三个解。

(ⅱ) 因为这是对模5的同余方程,故原方程不可能有六个解。

32n?12、设n是正整数,求C1 的最大公约数。 2n,C2n,?,C2n132n?1132n?12n?1 解:设(C2n,C2n,?,C2n)?d,由C2n?C2n???C2n?2知d?22n?1,

|n,即2k +1||n , 设2k|n且2k+1?则由2k +1||C2n及21k?1|Ci2n?2ni?1C2n?1,i = 3, 5, ?, 2n ? 1 得d = 2k + 1。 i3、已知a=18,m=77,求使ax? 1 (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。

5

四、证明题

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=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(mod 8),

于是p2≡q2(mod 8)。故p2≡q2(mod 24)。

3、若x,y∈R,

(1)证明:[xy]?[x][y];

(2)试讨论{xy}与{x}{y}的大小关系。

注:我们知道,[x ? y] ?[x]+ [y],{x+y}?{x}+{y}。此题把加法换成乘法又如何呢? 证明:(1)设x=[x]+α,0?α<1,y=[y]+β,0?β<1。于是

xy=[x][y]+β[x]+α[y]+αβ

所以[xy]= [x][y]+ [β[x]+α[y]+αβ] ?[x][y]。 (2){xy}与{x}{y}之间等于、大于、小于三种关系都有可能出现。

11时,{xy}={x}{y}=; 243131 当x=, y=时,{xy}=,{x}{y}=,此时{xy}>{x}{y};

22441111 当x=-,y=-时,{xy}=,{x}{y}=,此时{xy}<{x}{y}。

2363cc4、证明:存在一个有理数,其中d < 100,能使 [k]=[k73]

dd100+

当x=y=

对于k=1,2,….,99均成立。

证明:由(73,100)=1以及裴蜀恒等式可知:存在整数c,d,使得 73d-100c=1

从而

73kkck(73d?100c)k-==,由k< 100可知: 100100dd100d6

0<

设[k73kc1k-< 100dddcd]=n,则kc<n+1=n?1d,于是

d73kc?1n?1k<d=n+1, ?100dd73故 [k]= n =[k100cd]。

初等数论练习题四

一、单项选择题

1、若Fn=22?1是合数,则最小的n是( D )。 A. 2 B. 3 C. 4 D. 5

|a. 以下各式中错误的一个是( B )。 2、记号ba‖a表示ba|a,但ba+1?nA. 218‖20! B. 105‖50! C. 119‖100! D. 1316‖200! 3、对于任意整数n,最大公因数(2n+1,6n-1)的所有可能值是( A )。

A. 1 B. 4 C. 1或2 D. 1,2或4 4、设a是整数,下面同余式有可能成立的是( C )。

A. a2≡2 (mod 4) B. a2≡5 (mod 7) C. a2≡5 (mod 11) D. a2≡6 (mod 13) 5、如果a≡b(mod m),c是任意整数,则下列错误的是( A ) A.ac≡bc(mod mc) 二、填空题

1、d(10010)=_32__,φ(10010)=_2880__。

2、对于任意一个自然数n,为使自N起的n个相继自然数都是合数,可取N=(n+1)! 3、为使3n-1与5n+7的最大公因数达到最大可能值,整数n应满足条件n=26k+9,k∈Z。 4、在5的倍数中,选择尽可能小的正整数来构成模12的一个简化系,则这组数是{5,25,35,55} 5、同余方程26x+1≡33 (mod 74)的解是x1≡24(mod74) x2≡61(mod74)_。 6、不定方程5x+9y=86的正整数解是_x=1,y=9或x=10,y=4。 7、?

B.m|a-b C.(a,m)=(b,m) D.a=b+mt,t∈Z

?54??=_-1_。 ?89?7

三、计算题

1、设n的十进制表示是13xy45z,若792?n,求x,y,z。 解:因为792 = 8?9?11,故792?n ? 8?n,9?n及11?n。

我们有8?n ? 8?45z? z = 6,以及

9?n ? 9?1 ? 3 ? x ? y ? 4 ? 5 ? z = 19 ? x ? y ? 9?x ? y ? 1, (1) 11?n ? 11?z ? 5 ? 4 ? y ? x ? 3 ? 1 = 3 ? y ? x ? 11?3 ? y ? x。 (2) 由于0 ? x, y ? 9,所以由式(1)与式(2)分别得出

x ? y ? 1 = 9或18, 3 ? y ? x = 0或11。

?x?y?1?a这样得到四个方程组:?

?3?y?x?b其中a取值9或18,b取值0或11。在0 ? x, y ? 9的条件下解这四个方程组, 得到:x = 8,y = 0,z = 6。 2、求3406的末二位数。

解:∵ (3,100)=1,∴3φ(100)≡1(mod 100),而φ(100)= φ(22·52)=40,

∴ 340≡1(mod 100) ∴ 3406=(340)10·36≡(32)2·32≡-19×9≡-171≡29(mod 100) ∴ 末二位数为29。

3、求(214928+40)35被73除所得余数。

解:(214928+40)35≡(3228+40)35≡[(32×32)14+40]35 ≡(102414+40)35 ≡(214+40)35 ≡(210

×24+40)35 ≡(25+40)35 ≡7235 ≡-1≡72(mod 73)

四、证明题

1、设a1, a2, ?, am是模m的完全剩余系,证明: (1)当m为奇数时,a1+ a2+ ?+ am ≡0(mod m); (2)当m为偶数时,a1+ a2+ ?+ am ≡

m(mod m)。 2 证明:因为{1, 2, ?, m}与{a1, a2, ?, am}都是模m的完全剩余系,所以

?ai??i?i?1i?1mmm(m?1)(mod m)。 2 8

mm?1m(m?1)m(m?1)?Z即得:m(1)当m为奇数时,由,故?ai??0(mod m)。 222i?1m(2)当m为偶数时,由(m,m+1)=1即得:?ai?i?1m(m?1)m?(mod m)。 22?(m)2、证明:若m>2,a1, a2, ?, a?(m)是模m的任一简化剩余系,则

?ai?1i?0(modm).

证明:若a1, a2, ?, a?(m)是模m的一个简化剩余系,则m-a1, m-a2, ?, m-a?(m) 也是模m

?(m)的一个简化剩余系,于是:

?a??(m?a)(modm). 从而:2?aiii?1i?1i?1?(m)?(m)i?m?(m)(modm).

又由于m>2,?(m)是偶数。故:

?(m)i?1?ai?m?(m)2?0(modm).

3、设m > 0是偶数,{a1, a2, ?, am}与{b1, b2, ?, bm}都是模m的完全剩余系,证明:{a1 ? b1, a2 ? b2, ?, am ? bm}不是模m的完全剩余系。

证明:因为{1, 2, ?, m}与{a1, a2, ?, am}都是模m的完全剩余系,所以

?ai??i?i?1i?1mmm(m?1)m?(mod m)。 (1) 22同理 ?bi?i?1mm(mod m)。 (2) 2如果{a1 ? b1, a2 ? b2, ?, am ? bm}是模m的完全剩余系,那么也有

?(ai?bi)?i?1mm(mod m)。 2联合上式与式(1)和式(2),得到 0?mmm??(mod m), 222这是不可能的,所以{a1 ? b1, a2 ? b2, ?, am ? bm}不能是模m的完全剩余系。 4、证明:(1)2730∣x13-x; (2)24∣x(x+2)(25x-1);

(3)504∣x9-x3; (4)设质数p>3,证明:6p∣xp-x。 证明:(1)因为2730=2×3×5×7×13,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;

9

2

由x13-x=x (x12-1)=x(x6-1)(x6+1)≡0 (mod 7)知:7∣x13-x。 故有2730∣x13-x。 同理可证(2)、(3)、(4)。

初等数论练习题五

一、单项选择题

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整除的数的个数是( 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。

q2、高斯称反转定律是数论的酵母,反转定律是指设p与q是不相同的两个奇质数, ()?(?1)pp?1q?1?22(p)

q3、20122012被3除所得的余数为_1__。 4、设n是大于2的整数,则(-1)?(n)=__1__。 5、单位圆上的有理点的坐标是(?零的整数。

6、若3258×a恰好是一个正整数的平方,则a的最小值为362。

?72?7、已知2011是一素数,则??=_-1_。

2011??2aba2?b2,?a2?b2a2?ba?b)或(?,?222a?b222aba2?b2),其中a与b是不全为

三、计算题

10

1、求32008×72009×132010的个位数字。

解:32008×72009×132010≡32008×(-3)2009×32010 ≡-32008+2009+2010 ≡-36027 ≡-3×(32)3013 ≡3(mod 10)。

2、求满足?(mn)=?(m)+?(n)的互质的正整数m和n的值。

解:由(m,n)=1知,?(mn)=?(m)?(n)。于是有:?(m)+?(n)= ?(m)?(n) 设?(m)=a, ?(n)=b,即有:a+b=ab。 显然a∣b,且b∣a,因此a=b。 于是由2a=a2 得a=2,即?(m)= ?(n)=2。 故 m=3,n=4或m=4,n=3。

3、甲物每斤5元,乙物每斤3元,丙物每三斤1元,现在用100元买这三样东西共100斤,问各买几斤?

解:设买甲物x斤,乙物y斤,丙物z斤,则

5x ? 3y ?z = 100, x ? y ? z = 100。

消去z,得到 7x ? 4y = 100。 (1) 显然x = 0,y = 25是方程(1)的解,因此,方程(1)的一般解是

13?x?4t , t?Z ?y?25?7t?因为x>0,y>0,所以 0<t ? 3。

即t可以取值t1 = 1,t2 = 2,t3 = 3。相应的x,y,z的值是

(x, y, z) = (4, 18, 78),(8, 11, 81),(12, 4, 84)。

四、证明题

1、已知2011是质数,则有2011|99????9。 ??2010个2011

证明:99=10-1≡0 (mod 2011)。 ???9???2010个2、设p是4n+1型的质数,证明若a是p的平方剩余,则p-a也是p的平方剩余。 证明:因为质数p=4n+1,a是p的平方剩余,所以

?p?a???a???1? ??p??=??p???p??=???????p?1?a??a?2???=(?1)?p??p??=1 ???? 即:p-a也是p的平方剩余。

3、已知p,q是两个不同的质数,且ap-1≡1 (mod q), aq-1≡1 (mod p), 证明:apq≡a (mod pq)。

11

证明:由p,q是两个不同的质数知(p,q)=1。于是由Fermat定理 ap≡a (mod p),

又由题设aq-1≡1 (mod p)得到:apq≡(aq)p≡ap (aq-1)p≡ap≡a (mod p)。 同理可证:apq≡a (mod q)。故:apq≡a (mod pq)。

4、证明:若m,n都是正整数,则?(mn)=(m,n)?([m,n])。

证明:易知mn与[m,n]有完全相同的质因数,设它们为pi (1?i?k),则

?mn(1? ?(mn)111)(1?)?(1?) p1p2pk111)(1?)?(1?) p1p2pk?([m,n])?[m,n](1?又mn=(m,n)[m,n]

?(m,n)[m,n](1?故?(mn)111)(1?)?(1?)?(m,n)?([m,n])。 p1p2pk 类似的题:设m=m1m2,m1与m由相同的质因数,证明:?(m)=m2?(m1)。

初等数论练习题六

一、填空题

1、为了验明2011是质数,只需逐个验算质数2,3,5,…p都不能整除2011,此时,质数p至少是_43___。

2、最大公因数(4n+3,5n+2)的可能值是_1,7__。

|40!,即3α‖40!,则α=_18_。 3、设3α∣40!,而3α+1?4、形如3n+1的自然数中,构成模8的一个完全系的最小那些数是{1,4,7,10,13,16,19,22}。

5、不定方程x2+y2=z2,2|x, (x,y)=1, x,y,z>0的整数解是且仅是x = 2ab,y = a2 ? b2,z = a2 ? b2,其中a > b > 0,(a, b) = 1,a与b有不同的奇偶性。

6、21x≡9 (mod 43)的解是x≡25 (mod 43)。 7、??73?? = -1。 ?199?二、计算题 1、将

17写成三个既约分数之和,它们的分母分别是3,5和7。 10517xyz???,即35x ? 21y ? 15z = 17,因(35, 21) = 7,(7, 15) = 1,1?17,故解:设

105357有解。

12

分别解 5x ? 3y = t 7t ? 15z = 17

得 x = ?t ? 3u,y = 2t ? 5u,u?Z,

t = 11 ? 15v,z = ?4 ? 7v,v?Z,

消去t得 x = ?11 ? 15v ? 3u,

y = 22 ? 30v ? 5u,

z = ?4 ? 7v, u,v?Z。

令u =0,v =-1得到:x =4,y =-8,z=3。即:

174?83??? 1053572、若3是质数p的平方剩余,问p是什么形式的质数?

p?1?3?2解:∵ 由二次互反律??p???(?1)???p????, ?3??p?注意到p>3,p只能为p??1(mod 3)且????3?p?1(mod4)?1? ?1p??1(mod4)?∴

?p?1(mod3)?3?只能下列情况 ???1??p?p?1(mod4)???d)?p??1(mo3 ?

d)?p??1(mo4∴ p?1(mod12)或p??1(mod12)。 3、判断不定方程x2+23y=17是否有解?

解:只要判断x2≡17(mod 23) 是否有解即可。 ∵ 17≡1(mod 4) ∴ ??17??23??6??2??3??3??17??2????????????????????????1 23???17??17??17??17??17??3??3?∴ x2≡17(mod 23)无解,即原方程无解。 三、论证题

1、试证对任何实数x,恒有〔x〕+〔x+〕=〔2x〕 证明:设x=[x]+α,0?α<1

①当0?α<

1211时, [x +]=[x], [2x]=2[x] ∴等式成立 221212②当?α< 1时, [x +]=[x]+1, [2x]=2[x]+1 ∴等式成立 故对任何实数x,恒有[x]+[x+]=[2x]。

2、证明:(1)当n为奇数时,3∣(2+1);

n

12 13

|(2+1)(2)当n为偶数时,3?。

证明:由2+1≡(-1)+1(mod 3)立得结论。 3、证明:(1)当3∣n(n为正整数)时,7∣(2-1);

n

n

n

n

|(2+1) (2)无论n为任何正整数,7?。

证明:(1)设n=3m,则2-1=8-1≡0(mod 7),即:7∣(2-1); (2)由于2≡1(mod 7)得 2+1≡2(mod 7),2

3m

3m+1

3m

n

m

n

n

+1≡3(mod 7),2

n

3m+2

+1≡5(mod 7)。

|(2+1) 故无论n为任何正整数,7?。

4、设m>0,n>0,且m为奇数,证明:(2-1,2+1)=1。 证明一:由m为奇数可知:2n+1︱2+1,又有2m-1︱2-1,

于是存在整数x,y使得:(2n+1)x=2+1, (2m-1)y=2-1。 从而(2n+1)x-(2m-1)y=2。这表明:

(2m-1,2n+1)︱2

由于2n+1,2m-1均为奇数可知:(2m-1,2n+1)=1。

证明二:设(2-1,2+1)=d,则存在s,t∈Z,使得2=sd+1, 2=td-1。由此得到: 2=(sd+1), 2=(td-1)

mn

n

mn

m

m

n

m

n

m

n

mnmn

mnmn

于是 2

mn

=pd + 1=qd – 1,p,q∈Z。所以:(q -p)d =2。

从而 d∣2,就有d =1或2。由因为m为奇数,所以d =1。

即(2-1,2+1)=1。

注:我们已证过:记Mn = 2n ? 1,对于正整数a,b,有(Ma, Mb) = M(a, b) 。

显然当a≠b,a,b为质数时,(Ma, Mb) =1。

m

n

初等数论练习题七

一、单项选择题

1、设a和b是正整数,则(

[a,b][a,b],)=( A ) ab14

A.1 B.a C.b D.(a,b)

2、176至545的正整数中,13的倍数的个数是( B ) A.27

B.28 C.29

D.30

3、200!中末尾相继的0的个数是( A ) A.49 B.50 C.51

D.52

4、从以下满足规定要求的整数中,能选取出模20的简化剩余系的是( B ) A.2的倍数 B.3的倍数 C.4的倍数

D.5的倍数

5、设n是正整数,下列选项为既约分数的是( A ) A.

21n?4n?12n?1n?1 B. C. D.

14n?32n?15n?23n?1二、填空题

1、314162被163除的余数是_1__。(欧拉定理) 2、同余方程3x≡5(mod13)的解是x≡5(mod13)。 3、(365)=1。 18474、[-π]=-4。

5、为使n-1与3n的最大公因数达到最大的可能值,则整数n应满足条件n=3k+1,k∈Z。 6、如果一个正整数具有21个正因数,问这个正整数最小是26×32=576。 7、同余方程x3+x2-x-1≡0(mod 3)的解是x≡1,2(mod 3)。 三、计算题

1、求不定方程x ? 2y ? 3z = 41的所有正整数解。 解:分别解x ? 2y = t

t ? 3z = 41

得 x = t ? 2u

y = u u?Z, t = 41 ? 3v

z = v v?Z,

消去t得 x = 41 ? 3v ? 2u

y = u

z = v u,v?Z。

由此得原方程的全部正整数解为

(x, y, z) = (41 ? 3v ? 2u, u, v),u > 0,v > 0,41 ? 3v ? 2u > 0。

15

2、有一队士兵,若三人一组,则余1人;若五人一组,则缺2人;若十一人一组,则余3人。已知这队士兵不超过170人,问这队士兵有几人?

解:设士兵有x人,由题意得x ? 1 (mod 3),x ? ?2 (mod 5),x ? 3 (mod 11)。

在孙子定理中,取 m1 = 3, m2 = 5, m3 = 11,m = 3?5?11 = 165,

M1 = 55,M2 = 33,M3 = 15, M1? = 1,M2? = 2,M3? = 3,

则 x ? 1?55?1 ? (-2)?33?2 ? 3?15?3 ? 58 (mod 165), 因此所求的整数x = 52 + 165t,t?Z。

由于这队士兵不超过170人,所以这队士兵有58人。

23、判断同余方程x?286(mod443)是否有解?

解:286=2×143,433是质数,(143,443)=1

奇数143不是质数,但可用判定雅可比符号计算的勒让德符号

?286??2??143?????????(?1)?443??243??443?4432?12?(?1)143?1443?1?22?443??14??2??7??????????? 143143143143?????????(?1)143?18?(?1)7?1143?1?223??1??143??????????1 ∴原方程有解。 ??

?7??3??7?四、证明题

1、设(a, m) = 1,d0是使a d ? 1 (mod m)成立的最小正整数,则

(ⅰ) d0??(m);

j

(ⅱ)对于任意的i,j,0 ? i, j ? d0 ? 1,i ? j,有a i??a (mod m)。 (1)

证明:(ⅰ) 由Euler定理,d0 ? ?(m),因此,由带余数除法,有

?(m) = qd0 ? r,q?Z,q > 0,0 ? r < d0。 因此,由上式及d0的定义,利用欧拉定理得到

qd?r1 ?a?(m)?a0?ar(mod m),

即整数r满足 a r ? 1 (mod m),0 ? r < d0 。 由d0的定义可知必是r = 0,即d0??(m)。

(ⅱ) 若式(1)不成立,则存在i,j,0 ? i, j ? d0 ? 1,i ? j,使a i ? a j (mod m)。 不妨设i > j。因为(a, m) = 1,所以 ai ? j ? 0 (mod m),0 < i ? j < d0。

16

这与d0的定义矛盾,所以式(1)必成立。

2、证明:设a,b,c,m是正整数,m > 1,(b, m) = 1,并且

b a ? 1 (mod m),b c ? 1 (mod m) (1)

记d = (a, c),则bd ? 1 (mod m)。

证明:由裴蜀恒等式知,存在整数x,y,使得ax ? cy = d,显然xy < 0。

若x > 0,y < 0,由式(1)知:1 ? b ax = b db ?cy = b d(b c) ?y ? b d (mod m)。 若x < 0,y > 0,由式(1)知:1 ? b cy = b db ?ax = b d(ba) ?x ? b d (mod m)。

3、设p是素数,p?bn ? 1,n?N,则下面的两个结论中至少有一个成立:

(ⅰ) p?bd ? 1对于n的某个因数d < n成立; (ⅱ) p ? 1 ( mod n )。

|n,p > 2,则(ⅱ)中的mod n可以改为mod 2n。 若2?证明:记d = (n, p ? 1),由b n ? 1,b p ? 1 ? 1 (mod p),及第2题有

b d ? 1 (mod p)。

若d < n,则结论(ⅰ)得证。

若d = n,则n?p ? 1,即p ? 1 (mod n),这就是结论(ⅱ)。

|n,p > 2,则p ?1 (mod 2)。由此及结论(ⅱ),并利用同余的基本性质, 若2?得到p ? 1 (mod 2n)。

初等数论练习题八

一、单项选择题

1、设n > 1,则n为素数是(n ? 1)! ? ?1 (mod n)的( C )。 A.必要但非充分条件 B.充分但非必要条件 C.充要条件 D.既非充分又非必要条件 2、小于545的正整数中,15的倍数的个数是( C )

A.34 B.35 C.36 D.37 3、500!的标准分解式中7的幂指数是( D )

A.79 B.80 C.81 D.82 4、以下各组数中,成为模10的简化剩余系的是( D )

A.1,9,-3,-1 B.1,-1,7,9 C.5,7,11,13 D.-1,1,-3,3 5、设n是正整数,下列选项为既约分数的是( A )

17

A.

3n?15n?2 B.n?12n?1 C.2n?1n?15n?2 D.3n?1 二、填空题

1、σ(120)=360。 2、7355的个位数字是3。

3、同余方程3x≡5(mod14)的解是x≡11(mod14)。 4、(

1723)=1。 5、[-2]=-2。

6、如果一个正整数具有6个正因数,问这个正整数最小是12。 7、同余方程x3+x2-x-1≡0(mod 5)的解是x≡±1(mod5)。 三、计算题

1、已知563是素数,判定方程x2 ? 429 (mod 563)是否有解。

解:把??429??563??看成Jacobi符号,我们有

?429?1563?14292?1?429?2.2??563??563??1348??563???(?1)?429?????429??????429?????2??67??429????429???(?1)?67??429??67?1429?27?1????67????(?1)2.12??429?????2.67?12??429??67??429??67??????27??67????(?1)?67??27?????67??27??

27?1???13???(?2.13?12??27??27?1)?13?????1??13???1, 故方程x2 ? 429 (mod 563)有解。

2、求出模23的所有的二次剩余和二次非剩余。 解:模23的所有的二次剩余为

x?1,2,3,4,6,8,9,12,13,16,18 (mod 23); 模23的所有的二次非剩余为

x?5,7,10,11,14,15,17,19,20,21,22 (mod 23)。

3、试求出所有正整数n ,使得1n+2n+3n+4n 能被5整除。

解:若n为奇数,则1n+2n+3n+4n?1n+2n+(-2)n+(-1)n ? 0 (mod 5); 若n=2m,m∈Z,则1n+2n+3n+4n?12m+22m+(-2)2m+(-1)2m

?2+2×22m =2+2×4m =2+2×(-1)m(mod 5);

18

-)

当m为奇数时,1n+2n+3n+4n?0(mod 5); 当m为偶数时,1n+2n+3n+4n?4(mod 5)。

|n时,5∣1+2+3+4。 故当4?n

n

n

n

四、证明题

1、证明:若质数p>2,则2P-1的质因数一定是2pk+1形。

证明:设q是2p-1的质因数,由于2p-1为奇数,∴ q≠2,(2,q)=1。

由条件q|2p-1,即2p≡1(mod q)。

设h是使得2x≡1(mod q)成立最小正整数,若1

2、设(m,n)=1,证明:m

?(n)

+n

?(m)

≡1 (mod mn)。

?(m)

证明:因为(m,n)=1,所以由欧拉定理知: n 于是 m

?(n)

≡1 (mod m),m

?(n)

≡1 (mod n)

+n

?(m)

≡1 (mod m), m

?(n)

?(n)

+n

?(m)

≡1 (mod n)。

又因为(m,n)=1,所以 m+n

?(m)

≡1 (mod mn)。

注:此题也可这样表述:若两个正整数a,b互质,则存在正整数m,n,使得

am+bn≡1(mod ab)。

ap?bp3、设(a,b)=1,a+b≠0,p为一个奇质数,证明:(a?b,)?1或p。

a?bap?bp 说明:事实上,设(a?b,)?d,只需证明:d | p 即可。

a?b证明:由a+b≡0(mod a+b),即a≡-b (mod a+b),知a≡(-b) (mod a+b)。

ppa?b其中0?k?p-1。又?ap?1?ap?2b???abp?2?bp?1?bp?1?bp?1???bp?1?pbp?1m(oda?bkk

a?b)。

p-1 ap?bp令(a?b,。 又(a,b)=1,d |(a+b)知(d,b)=1。 )?d,则d | pb

a?b(否则设(d,b)=d′>1,立即得到d′︱a和d′︱b,这与(a,b)=1矛盾。)

于是(d ,b

p-1

)=1。故d | p,即 d =1或p。

19

初等数论练习题九

一、单项选择题

1、以下Legendre符号等于-1的30被-1是( D )

3?A. ???

?11?4?B. ??? C.

?11??5? D. ???11??6? ???11?2、100至500的正整数中,能被17整除的个数是( B ) A. 23

B. 24

C. 25

D. 26

3、设 3?|500!,但3??1?,则α=( C ) |500!A. 245

B.246

C.247

D. 248

4、以下数组中,成为模7的完全剩余系的是( C ) A. -14,-4,0,5,15,18,19 C. -4,-2,8,13,32,35,135

B. 7,10,14,19,25,32,40 D. -3,3,-4,4,-5,5,0

5、设n是正整数,则以下各式中一定成立的是( B ) A. (n+1,3n+1)=1 C.(2n,n+1)=1 二、填空题

1、25736被50除的余数是1。

2、同余方程3x≡5(mod16) 的解是x≡7(mod16)。 3、不定方程9x-12y=15的通解是x = -1 + 4t,y = -2 +3t,t?Z。 4、??323?? =1。 41??B.(2n-1,2n+1)=1 D.(2n+1,n-1)=1

5、实数的小数部分记为{x} ,则 {-}=0.75。

6、为使3n与4n+1 的最大公因数达到最大可能值,整数n应满足条件n=3k+2,k∈Z。 7、如果一个正整数具有35个正因数,问这个正整数最小是26×34=5184。 三、计算题

1、解不定方程9x+24y-5z=1000。

解:解 因(9,24)=3,(3,-5)=1知原方程有解。原方程化为

9x ? 24y = 3t, 即 3x ? 8y = t, (1) 3t -5z = 1000 3t -5z = 1000, (2)

20

54

?t?5u解(2)得 ?, u?Z,

z??200?3u??x??u?8v再解3x ? 8y =5u得到 ?, u,v?Z。

y?u?3v??x??u?8v?故 ?y?u?3v, u, v?Z。

?z??200?3u?2、设A = {x1, x2, ?, xm}是模m的一个完全系,以{x}表示x的小数部分,若(a, m) = 1,

ax?b求?{i}。

mi?1m解:当x通过模m的完全剩余系时,ax ? b也通过模m的完全剩余系,因此对于任意的

i(1 ? i ? m),axi ? b一定与且只与某个整数j(1 ? j ? m)同余,即存在整数k,使得axi ? b = km ? j,(0 ? j ? m-1)。从而:

m?1m?1m?1axi?bjjj1m(m?1)m?1 {}?{k?}?{}????。????mmm22i?1j?0j?1mj?1mm3、设整数n ? 2,求:

1?i?n(i,n)?1?i。即在数列1, 2, ?, n中,与n互素的整数之和。

解:设在1, 2, ?, n中与n互素的?(n)个数是

a1, a2, ?, a?(n),(ai, n) = 1,1 ? ai ? n ? 1,1 ? i ? ?(n), 则 (n ? ai, n) = 1,1 ? n ? ai ? n ? 1,1 ? i ? ?(n),

因此,集合{a1, a2, ?, a?(n)}与集合{n ? a1, n ? a2, ?, n ? a?(n)}是相同的,于是

a1 ? a2 ? ? ? a?(n) = (n ? a1) ? (n ? a2) ? ? ? (n ? a?(n)),

2(a1 ? a2 ? ? ? a?(n)) = n?(n), 因此:a1 ? a2 ? ? ? a?(n) =n?(n)。 4、设m > 1,(a, m) = 1,x1, x2, ?, x?(m)是模m的简化剩余系,求:?{axi}。

i?112?(m)m 21

其中{x}表示x的小数部分。

解:设axi = mqi ? ri,0 ? ri < m,由xi通过模m的简化剩余系知:axi也通过模m的简化剩

余系,从而ri通过模m的最小非负简化剩余系,于是:

?(m)?(m)?(m)axiriri1?(m)11{}?{q?}??r?m?(m)??(m)。 ????iimmmm2m2i?1i?1i?1i?1四、证明题

1、证明:设a是有理数,b是使ba为整数的最小正整数,若c和ca都是整数,则 b∣c。(提示:利用带余数除法解决。)

证明:设c=bq+r,0?r<b,q∈Z,则ca=(ba)q+ra。

因为ca,ba∈Z,所以ra∈Z,于是ra=0,由a≠0得r=0。故b∣c。

2、设p是素数,证明:

(ⅰ) 对于一切整数x,xp ? 1 ? 1 ? (x ? 1) (x ? 2)?(x ? p ? 1) (mod p); (ⅱ) (p ? 1)! ? ? 1 (mod p)。

证明:(ⅰ) xp ? 1 ? 1 ? 0 (mod p)有解x ? 1,2,?,p ? 1 (mod p),

故对于一切整数x,xp ? 1 ? 1 ? (x ? 1) (x ? 2)?(x ? p ? 1) (mod p);。 (ⅱ) 在(ⅰ)中令x = p。

?a?n

|n,p是奇质数,p∣a-1,则?3、证明:若2??p???1。

?? 证明:由p∣a-1知:a ? 1(mod p)。又(p,a)=1得到a

|n,所以(a 因为2?n?122nnn+1

? a(mod p)。

?a?2

)?a(modp),即x ? a(mod p)有解。故 ??p???1。

??m()?1。 4、证明:若p=4m+1是一质数,则pm4m?1 证明:()?()?()?(?1)pppp?12?(?1)2m?1。

p?12)!)? ?1 (mod p) 25、设p是奇质数,p ? 1 (mod 4),则:(?(解 由Wilson定理有:

22

?1?(p?1)!?(?1)p?12(p?1)!?(?1)p?121?2?p?1p?1p?12 ?(p?1)?(?()!)(modp)。222注:(1)设p为质数且p=4m+1,则同余方程x2??1(modp)的解是x??1?2?(2m)(modp)。 (2)设p为质数且p=4m+1,若且唯若存在一个正整数a,使得 a2≡?1 (mod p)。

初等数论练习题十

一、单项选择题

1、设p是大于1的整数,如果所有不大于p的质数都不能整除p,则p一定是( A )。 A.素数 B.合数 C.奇数 D. 偶数 2、两个质数p,q,满足p+q=99,则A.9413 B.

9413 194pq?的值是( B ) qpC.

94139413 D. 991113、2010!的标准分解式中,7的最高幂指数为( C ) A.331 B.332 C.333 D.334 4、n为正整数,若2n+1为质数,则n是( D )

A.质数 B.合数 C.1 D.2k(k为非负整数) 5、当n>2时,欧拉函数?(n)一定是( B )。 A.奇数 B.偶数 C.1 D.2 二、填空题

1、如果p是质数,a是整数,则有(a,p)=1或者p∣a。 2、设p是奇质数,(a,p)=1,则a是模p的平方非剩余的充要条件是a3、从1000开始到2010结束的所有整数中13的倍数有78个。 4、2756839-1的末位数是7。

5、不定方程ax+by=c有解的充要条件是(a, b)?c。

p?12??1(modp)

6、写出模12的一个最小非负简化系,要求每项都是7的倍数,此简化系为{7,35,49,77}。 7、已知563是质数,则?三、计算题

1、若3是质数p的平方剩余,问p是什么形式的质数?

23

?2??=-1。 ?563?3?解:∵ 由二次互反律????(?1)?p???p?12?p????, ?3??3???1p??1p?1(mod3)注意到p>3,p只能为p??1(mod 4)且? ????

p??1(mod3)∴

?3??p?1(mod3) ,只能是下列情况???1?p?????p?1(mod4)p??1(mo3d) ? ?d)?p??1(mo4∴ p?1(mod12)或p??1(mod12)。 2、求使12347!被35k整除的最大的k值。 解:k=2054. 四、证明题

1、证明:设p?7是一个质数,则存在唯一的一个正整数x,使得:

x??1,2,?,p?1?且120?p-6?!?x?0?modp?

证明:存在性:因为p?7是一个素数,由Wilson定理我们有:?p?1?!?1?0?modp?,

然而?p?1?!??p?1??p?2??p?3??p?4??p?5??p?6?!??120?p?6?!?modp?,所以120?p?6?!??p?1??0?modp?,

故存在x?p?1,使得120?p-6?!?x?0?modp?。

唯一性:若还存在y??1,2,?,p?1?且120?p-6?!?y?0?modp?, 则x?y?modp?,注意到x,y??1,2,?,p?1?,所以x?y是唯一的。

2、已知9901是素数,试证:9901(174950?1)。

证明:由9901是素数,计算Legendre符号得:

17?19901?17?117?13?17?1?17??9901??7??17??3??7??1?222222??1???1???1????????????????????????1?9901??17??17??7??7??3??3?

所以17是模9901的平方非剩余,因此由Euler判别条件可知:

179901?12??1?mod9901? 即 9901(174950?1)。

3、证明:若p=10n-1是个质数,则p55n?1?1。(提示:利用勒让德符号解决。) 说明:要证p55n?1?1,只需证明55n?1?1(modp),即证:

24

55n?1?510n?1?12?5p?12?1(modp) 这样就转化为证明:(5)?1。

p 证明:因为(5)?(p)?(10n?1)?(?1)?1(modp)。

p555 所以55n?1?510n?1?12?5p?12?1(modp)。 故:p55n?1?1。

4、设p=4n+3是质数,证明当q=2p+1也是质数时,梅森数Mp=2p-1不是质数。 由此证明:23|(2-1),47|(2-1),503|(2

11

23

251

-1)。

q证明:由条件:q=2p+1=8n+7?-1(mod 8),从而:(p)=1,

即1?2q?12p

?24n+3?2p (mod q),于是q|(2p-1)。故:梅森数Mp=2-1不是质数。

11

23

251

当n=2,n= 5,n=62时立得:23|(2-1),47|(2-1),503|(2

-1)。

注:此题还可以进一步表述为:设p=4n+3是质数,证明:2p+1是质数的充要条件是

2p≡1(mod 2p+1)。必要性已证。下证充分性:若2p≡1(mod 2p+1),则

p∣?(2p+1),因此必有?(2p+1)= p 或2p 。由于?(2p+1)为偶数,故?(2p+1)=2p 。

5、证明:设p是大于5的质数,则

(p?1)!?p?1?Z。

p(p?1)说明:只需证明:p(p+1) | (p-1)!+p+1。又因为(p,p+1)=1,所以需证: p | (p-1)!+p+1 与(p+1) | (p-1)!+p+1同时成立即可。 证明:由Wilson定理:?p?1?!?1?0?modp?知:p | (p-1)!+p+1;

又p是大于5的质数,可设p+1=2n,其中2<n<p-1,于是 (p+1) | (p-1)!+p+1。 故:p(p+1) | (p-1)!+p+1。即

(p?1)!?p?1?Z。

p(p?1) 25

本文来源:https://www.bwwdw.com/article/6hzw.html

Top