初等数论练习题答案

初等数论练习题答案

原点教育培训学校

初等数论练习题一

一、填空题

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

3

111）知5028 ≡（509）×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为正整数，试证a证明 设a = 2m ? 1，当n = 1时，有

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

a

a

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

a2k? 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。证明：Ck ? （-1 ）(mod p)。 p?1（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的奇质数，所以

（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.既非充分又非

?67???????(?1)429??67?1429?1.22?429??429??27?????????????(?1)?67??67??67?27?167?1.22?67??67?

??????27??27??13?????(?1)?27?27?113?1.22?27??1???????1， ?13??13?故方程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)；

当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 n)

≡1 (mod m)，m

?(n)

≡1 (mod

于是 m

?(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)。 其

中

0

?

kk

k?p-1。

a?mb)。

o又

dap?bp?ap?1?ap?2b???abp?2?bp?1?bp?1?bp?1???bp?1?pbp?1(a?bp-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。

初等数论练习题九

一、单项选择题

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

|500！3、设 3?|500!，但3??1?，则α=( C )

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)

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,

ax?bm) = 1，求?{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?}?{}????。????mmmmm22i?1j?0j?1j?1m3、设整数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其中{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

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

?? 证明：由p∣a-1知：a ? 1(mod p)。又（p，a）=1得到a

|n， 因为2?所以(an?122nnn+1

? a(mod p)。

?a?2

即x ? a(mod p)有解。故 ?)?a(modp)，?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定理有：

?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)(mopd)。

（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是什么形式的质数？

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

?3???1p??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?，

,p?1?，所以x?y是唯一的。

则x?y?modp?，注意到x,y??1,2,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)，即证：

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

pp10n?1?1()?()?()?()?1(modp)。 p5555n?1 所以5?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?2不是质数。

当n=2，n= 5，n=62时立得：23|（2-1），47|（2-1），503|（2

11

23

251

q?12p

?24n+3?2p （mod q)，于是q|（2p-1）。故：梅森数Mp=2-1

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

本文来源：https://www.bwwdw.com/article/v8ro.html