初等数论试卷

故同余方程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成立,则有

2其中q?Z,所以 ak?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成立。

k

3、设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 = Ckp?1 ? (-1 )(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) 同时成立即可。 证明:因为84=4×3×7及p是不等于3和7的奇质数,所以

(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。

三、证明题

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)

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,

设2k|n且2k+1?|n,即2k +1||n , 则由2k +1||C2n及22k + 1。

3、已知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。

四、证明题

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)。

1k?1|Ci2n?2ni?1C2n?1,i = 3, 5, ?, 2n ? 1 得d = i

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4