初等数论练习题答案.doc

初等数论练习题一
一、填空题
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的既约真分数的个数为_j(m)_。
7、18100被172除的余数是_256。
8、 =-1。
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)是否有解？

故同余方程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)a≡0 (mod p)；
（2）当a为偶数时，ap-1-(p-1)a≡0 (mod p)。
证明：由欧拉定理知ap-1≡1 (mod p)及(p-1)a≡-1 (mod p)立得（1）和（2）成立。
2、设a为正奇数，n为正整数，试证≡1(mod 2n+2)。 …………… （1）
证明 设a = 2m + 1，当n = 1时，有
a2 = (2m + 1)2 = 4m(m + 1) + 1 º 1 (mod 23)，即原式成立。
设原式对于n = k成立，则有 º 1 (mod 2k + 2) Þ= 1 + q2k + 2，
其中qÎZ，所以 = (1 + q2k + 2)2 = 1 + q ¢2k + 3 º 1 (mod 2k + 3)，
其中q ¢是某个整数。这说明式(1)当n = k + 1也成立。
由归纳法知原式对所有正整数n成立。
3、设p是一个素数，且1≤k≤p-1。证明： º （-1 ）k(mod p)。
证明：设A= 得：
k!·A =（p-1）(p-2)…（p-k）≡（-1）(-2)…（-k）(mod p)
又（kp）=1，故A = º （-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) 同时成立即可。
证明：因为84=4×3×7及p是不等于3和7的奇质数，所以
（p，4）=1，（p，3）=1，（p，7）=1。
由欧拉定理知：pj(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=+1,这种数中最小的合数Fn中的n=5。
4、同余方程13x≡5(mod 31)的解是x≡29(mod 31)___
5、分母不大于m的既约真分数的个数为j(2)+ j(3)+…+ j(m)。
6、设7∣(80n-1),则最小的正整数n=_6__.
7、使41x+15y=C无非负整数解的最大正整数C=__559__.
8、=_1__.
9、若p是质数，n½p - 1，则同余方程x n º 1 (mod p) 的解数为n .
二、计算题
1、试求被19除所得的余数。
解：由2002≡7 (mod 19) 20022≡11(mod 19) 20023≡1 (mod 19)
又由20032004≡22004≡（22）1002≡1 (mod 3)可得：
≡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，所以有欧拉定理知5j(21)≡1(mod 21)。
又由于j(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为240=23×3×5，所以只需证：p4≡1(mod 8)，p4≡1(mod 3)，p4≡1(mod 5)即可。事实上，由j(8)=4，j(3)=2，j(5)=4以及欧拉定理立得结论。
初等数论练习题三
一、单项选择题
1、若n＞1，j(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
4、不是同余方程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。
2、数的标准分解式中，质因数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、=_-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)，其中r(x) = 6x2 - 12x + 15的系数不都是5的倍数，故原方程没有三个解。
(ⅱ) 因为这是对模5的同余方程，故原方程不可能有六个解。
2、设n是正整数，求 的最大公约数。
解：设知d½22n-1，
设2k|n且2k+1n，即2k +1||n ，
则由2k +1||，i = 3, 5, L, 2n - 1 得d = 2k + 1。
3、已知a=18,m=77,求使axº 1 (mod m)成立的最小自然数x。
解：因为（18,77）=1，所以有欧拉定理知18j(77)≡1(mod 77)。
又由于j(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≡1mod 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}之间等于、大于、小于三种关系都有可能出现。
当x=y=时，{xy}={x}{y}=；
当x=， y=时，{xy}=，{x}{y}=，此时{xy}＞{x}{y}；
当x=-，y=-时，{xy}=，{x}{y}=，此时{xy}＜{x}{y}。
4、证明：存在一个有理数，其中d < 100,能使 =
对于k=1，2，….，99均成立。
证明：由（73，100）=1以及裴蜀恒等式可知：存在整数c，d，使得
73d-100c=1
从而-==，由k< 100可知：
0＜-＜
设=n，则＜n+1=,于是
＜≤=n+1，
故 = n =。
初等数论练习题四
一、单项选择题
1、若Fn=是合数，则最小的n是( D )。
A. 2 B. 3 C. 4 D. 5
2、记号ba‖a表示ba｜a,但ba+1a. 以下各式中错误的一个是( B )。
A. 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) B．m|a-b C．(a,m)=(b,m) D．a=b+mt,t∈Z
二、填空题
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、=_-1_。
三、计算题
1、设n的十进制表示是，若792½n，求x，y，z。
解：因为792 = 8×9×11，故792½n Û 8½n，9½n及11½n。
我们有8½n Û 8½ Þ 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。
这样得到四个方程组：
其中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, L, am是模m的完全剩余系，证明：
（1）当m为奇数时，a1+ a2+ L+ am ≡0（mod m）；
（2）当m为偶数时，a1+ a2+ L+ am ≡（mod m）。
证明：因为{1, 2, L, m}与{a1, a2, L, am}都是模m的完全剩余系，所以
(mod m)。
（1）当m为奇数时，即得：，故(mod m)。
（2）当m为偶数时，由（m,m+1）=1即得：(mod m)。
2、证明：若m＞2，a1, a2, L, aj(m)是模m的任一简化剩余系，则
证明：若a1, a2, L, aj(m)是模m的一个简化剩余系，则m-a1, m-a2, L, m-aj(m) 也是模m的一个简化剩余系，于是： 从而： 又由于m＞2，j(m)是偶数。故：
3、设m > 0是偶数，{a1, a2, L, am}与{b1, b2, L, bm}都是模m的完全剩余系，证明：{a1 + b1, a2 + b2, L, am + bm}不是模m的完全剩余系。
证明：因为{1, 2, L, m}与{a1, a2, L, am}都是模m的完全剩余系，所以
(mod m)。 (1)
同理 (mod m)。 (2)
如果{a1 + b1, a2 + b2, L, am + bm}是模m的完全剩余系，那么也有
(mod m)。
联合上式与式(1)和式(2)，得到 0(mod m)，
这是不可能的，所以{a1 + b1, a2 + b2, L, 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，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；
由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。
2、高斯称反转定律是数论的酵母，反转定律是指设p与q是不相同的两个奇质数，
3、20122012被3除所得的余数为_1__。
4、设n是大于2的整数，则(-1)n)=__1__。
5、单位圆上的有理点的坐标是，其中a与b是不全为零的整数。
6、若3258×a恰好是一个正整数的平方，则a的最小值为362。
7、已知2011是一素数，则=_-1_。
三、计算题
1、求32008×72009×132010的个位数字。
解：32008×72009×132010≡32008×（-3）2009×32010 ≡-32008+2009+2010
≡-36027 ≡-3×（32）3013 ≡3(mod 10)。
2、求满足j(mn)=j(m)+j(n)的互质的正整数m和n的值。
解：由（m，n）=1知，j(mn)=j(m)j(n)。于是有：j(m)+j(n)= j(m)j(n)
设j(m)=a， j(n)=b，即有：a+b=ab。 显然a∣b，且b∣a，因此a=b。
于是由2a=a2 得a=2，即j(m)= j(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)的一般解是
， tÎZ
因为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|。
证明：=102011-1≡0 (mod 2011)。
2、设p是4n+1型的质数，证明若a是p的平方剩余，则p-a也是p的平方剩余。
证明：因为质数p=4n+1，a是p的平方剩余所以
====1
即：p-a也是p的平方剩余。
3、已知p,q是两个不同的质数，且ap-1≡1 (mod q), aq-1≡1 (mod p),
证明：apq≡a (mod pq)。
证明：由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都是正整数，则j(mn)=（m,n）j([m,n])。
证明：易知mn与[m,n]有完全相同的质因数，设它们为pi (1≤i≤k)，则

又mn=（m,n）[m,n]
故。
类似的题：设m=m1m2，m1与m由相同的质因数，证明：j(m)=m2j(m1)。
初等数论练习题六
一、填空题
1、为了验明2011是质数，只需逐个验算质数2，3，5，…p都不能整除2011，此时，质数p至少是_43___。
2、最大公因数(4n+3,5n+2)的可能值是_1,7__。
3、设3α∣40!,而3α+140!，即3α‖40!，则α=_18_。
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、 = -1。
二、计算题
1、将写成三个既约分数之和，它们的分母分别是3，5和7。
解：设，即35x + 21y + 15z = 17，因(35, 21) = 7，(7, 15) = 1，1½17，故有解。
分别解 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。即：
2、若3是质数p的平方剩余，问p是什么形式的质数？
解：∵ 由二次互反律，
注意到p>3，p只能为p1(mod 3)且
∴ 只能下列情况
∴ 或。
3、判断不定方程x2+23y=17是否有解？
解：只要判断x2≡17(mod 23) 是否有解即可。
∵ 17≡1(mod 4) ∴
∴ x2≡17(mod 23)无解，即原方程无解。
三、论证题
1、试证对任何实数x,恒有〔x〕+〔x+〕=〔2x〕
证明：设x=[x]+α,0≤α<1
①当0≤α< 时, [x +]=[x], [2x]=2[x] ∴等式成立
②当≤α< 1时, [x +]=[x]+1, [2x]=2[x]+1 ∴等式成立
故对任何实数x,恒有[x]+[x+]=[2x]。
2、证明：（1）当n为奇数时，3∣（2n+1）；
（2）当n为偶数时，3（2n+1）。
证明：由2n+1≡（-1）n+1（mod 3）立得结论。
3、证明：（1）当3∣n（n为正整数）时，7∣（2n-1）；
（2）无论n为任何正整数，7（2n+1）。
证明：（1）设n=3m，则2n-1=8m -1≡0（mod 7），即：7∣（2n-1）；
（2）由于23m ≡1（mod 7）得
23m +1≡2（mod 7），23m+1 +1≡3（mod 7），23m+2 +1≡5（mod 7）。
故无论n为任何正整数，7（2n+1）。
4、设m＞0，n＞0，且m为奇数，证明：（2m-1，2n+1）=1。
证明一：由m为奇数可知：2n+1︱2mn+1，又有2m-1︱2mn-1，
于是存在整数x,y使得：（2n+1）x=2mn+1, (2m-1)y=2mn-1。
从而（2n+1）x-(2m-1)y=2。这表明：
（2m-1，2n+1）︱2
由于2n+1，2m-1均为奇数可知：（2m-1，2n+1）=1。
证明二：设（2m-1，2n+1）=d，则存在s,t∈Z,使得2m=sd+1, 2n =td-1。由此得到：
2mn=(sd+1) n, 2mn =(td-1) m
于是 2mn =pd + 1=qd – 1,p,q∈Z。所以：（q -p）d =2。
从而 d∣2，就有d =1或2。由因为m为奇数，所以d =1。
即（2m-1，2n+1）=1。
注：我们已证过：记Mn = 2n - 1，对于正整数a，b，有(Ma, Mb) = M(a, b) 。
显然当a≠b，a,b为质数时，(Ma, Mb) =1。
初等数论练习题七
一、单项选择题
1、设a和b是正整数，则=（　A　）
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． B． C． D．
二、填空题
1、314162被163除的余数是_1__。（欧拉定理）
2、同余方程3x≡5(mod13)的解是x≡5(mod13)。
3、=1。
4、［-π］＝-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。
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人。
3、判断同余方程是否有解?
解：286=2×143，433是质数，(143，443)=1
奇数143不是质数，但可用判定雅可比符号计算的勒让德符号

∴原方程有解。
四、证明题
1、设(a, m) = 1，d0是使a d º 1 (mod m)成立的最小正整数，则
(ⅰ) d0½j(m)；
(ⅱ)对于任意的i，j，0 £ i, j £ d0 - 1，i ¹ j，有a ia j (mod m)。 （1）
证明：(ⅰ) 由Euler定理，d0 £ j(m)，因此，由带余数除法，有
j(m) = qd0 + r，qÎZ，q > 0，0 £ r < d0。
因此，由上式及d0的定义，利用欧拉定理得到
1 º(mod m)，
即整数r满足 a r º 1 (mod m)，0 £ r < d0 。
由d0的定义可知必是r = 0，即d0½j(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。
这与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 )。
若2n，p > 2，则(ⅱ)中的mod n可以改为mod 2n。
证明：记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)，这就是结论(ⅱ)。
若2n，p > 2，则p º1 (mod 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 ）
A. B. C. D.
二、填