一、填空题
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、65 =-1。 103
9、若p是素数，则同余方程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 = 2，6，
由孙子定理得原同余方程的解为x 13，55，58，100 (mod 105)。 2、判断同余方程x2≡42(mod 107)是否有解？
237）（）（）107107107107107311071711071 ••231072710722222（）1，（）（1）（）（）1，（）（1）（）（）1107107331077742（）1107237解：(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)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为正整数，试证a2n≡1(mod 2n+2)。 …………… （1）
证明 设a = 2m 1，当n = 1时，有
a2 = (2m 1)2 = 4m(m 1) 1 1 (mod 23)，即原式成立。 设原式对于n = k成立，则有 其中qZ，所以 a2k1a2k 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。证明：Ckp1 （-1 ）(mod p)。
（p1）(p2)(pk) 证明：设A=Ckp1 得：
k! k!·A =（p-1）(p-2)…（p-k）≡（-1）(-2)…（-k）(mod p)
k
又（k!，p）=1，故A = Ck （-1 ）(mod p) p14、设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__. 101n9、若p是质数，np 1，则同余方程x n 1 (mod p) 的解数为n . 二、计算题 1、试求200220032004被19除所得的余数。
解：由2002≡7 (mod 19) 20022≡11(mod 19) 20023≡1 (mod 19) 又由20032004≡22004≡（22）1002≡1 (mod 3)可得：
200220032004≡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 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的同余方程，故原方程不可能有六个解。 32n12、设n是正整数，求C1 的最大公约数。 2n,C2n,,C2n132n1132n12n1 解：设(C2n,C2n,,C2n)d，由C2nC2nC2n2知d22n1， |n，即2k +1||n ， 设2k|n且2k+1则由2k +1||C2n及21k1|Ci2n2ni1C2n1，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(73d100c)k-==，由k< 100可知： 100100dd100d6 0＜ 设[k73kc1k-＜ 100ddc]=n，则kc＜n+1=n1d,于是 ddd73kc1n1≤k＜d=n+1， 100dd73故 [k]= n =[k100c]。 d初等数论练习题四 一、单项选择题 1、若Fn=221是合数，则最小的n是( D )。 A. 2 B. 3 C. 4 D. 5 2、记号ba‖a表示ba｜a,但ba+1|a. 以下各式中错误的一个是( 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) 二、填空题 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、 nB．m|a-b C．(a,m)=(b,m) D．a=b+mt,t∈Z 54=_-1_。 897 三、计算题 1、设n的十进制表示是13xy45z，若792n，求x，y，z。 解：因为792 = 8911，故792n 8n，9n及11n。 我们有8n 845z z = 6，以及 9n 91 3 x y 4 5 z = 19 x y 9x y 1， (1) 11n 11z 5 4 y x 3 1 = 3 y x 113 y x。 (2) 由于0 x, y 9，所以由式(1)与式(2)分别得出 x y 1 = 9或18， 3 y x = 0或11。 xy1a这样得到四个方程组： 3yxb其中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的完全剩余系，所以 aiii1i1mmm(m1)(mod m)。 2 8 mm(m1)m(m1)m10(mod m)。 （1）当m为奇数时，由，故aiZ即得：m222i1m（2）当m为偶数时，由（m,m+1）=1即得：aii1m(m1)m(mod m)。 22（m）2、证明：若m＞2，a1, a2, , a(m)是模m的任一简化剩余系，则 ai1i0(modm). 证明：若a1, a2, , a(m)是模m的一个简化剩余系，则m-a1, m-a2, , m-a(m) 也是模m （m）的一个简化剩余系，于是： a(ma)(modm). 从而：2aiii1i1i1(m)（m）im(m)(modm). 又由于m＞2，(m)是偶数。故： （m）i1aim（m）20(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的完全剩余系，所以 aiii1i1mmm(m1)m(mod m)。 (1) 22同理 bii1mm(mod m)。 (2) 2如果{a1 b1, a2 b2, , am bm}是模m的完全剩余系，那么也有 m(aibi)2(mod m)。 mi1联合上式与式(1)和式(2)，得到 0mmm(mod m)， 222这是不可能的，所以{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，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 由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)pp1q122(p) q3、20122012被3除所得的余数为_1__。 4、设n是大于2的整数，则(-1)(n)=__1__。 5、单位圆上的有理点的坐标是(零的整数。 6、若3258×a恰好是一个正整数的平方，则a的最小值为362。 727、已知2011是一素数，则=_-1_。 20112aba2b2,a2b2a2bab)或(,222ab222aba2b2)，其中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)的一般解是 13x4t ， tZ y257t因为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|999。 2010个 证明：999=102011-1≡0 (mod 2011)。 2010个2、设p是4n+1型的质数，证明若a是p的平方剩余，则p-a也是p的平方剩余。 证明：因为质数p=4n+1，a是p的平方剩余，所以 p1paa1aa2(1) ===ppppp=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α+14、形如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，117，故解：设 105357有解。 12 分别解 5x 3y = t 7t 15z = 17 得 x = t 3u，y = 2t 5u，uZ， t = 11 15v，z = 4 7v，vZ， 消去t得 x = 11 15v 3u， y = 22 30v 5u， z = 4 7v， u，vZ。 令u =0，v =-1得到：x =4，y =-8，z=3。即： 17483 1053572、若3是质数p的平方剩余，问p是什么形式的质数？ 3解：∵ 由二次互反律p(1)p12p， 3p1(mod4)p1注意到p>3，p只能为p1(mod 3)且 p1(mod4)31∴ p1(mod3)3只能下列情况 1pp1(mod4)p1(mod3) p1(mod4)∴ p1(mod12)或p1(mod12)。 3、判断不定方程x2+23y=17是否有解？ 解：只要判断x2≡17(mod 23) 是否有解即可。 ∵ 17≡1(mod 4) ∴ 172362331721 23171717171733∴ 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︱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。 证明二：设（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 于是 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． 21n4n12n1n1 B． C． D． 14n32n15n23n1二、填空题 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 uZ， t = 41 3v z = v vZ， 消去t得 x = 41 3v 2u y = u z = v u，vZ。 由此得原方程的全部正整数解为 (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 = 3511 = 165， M1 = 55，M2 = 33，M3 = 15， M1 = 1，M2 = 2，M3 = 3， 则 x 1551 （-2）332 3153 58 (mod 165)， 因此所求的整数x = 52 + 165t，tZ。 由于这队士兵不超过170人，所以这队士兵有58人。 23、判断同余方程x286(mod443)是否有解? 解：286=2×143，433是质数，(143，443)=1 奇数143不是质数，但可用判定雅可比符号计算的勒让德符号 2862143(1)443243443443212(1)14314431224431427 143143143143(1)14318(1)71143122311431 ∴原方程有解。 737四、证明题 1、设(a, m) = 1，d0是使a d 1 (mod m)成立的最小正整数，则 (ⅰ) d0(m)； j (ⅱ)对于任意的i，j，0 i, j d0 1，i j，有a ia (mod m)。 （1） 证明：(ⅰ) 由Euler定理，d0 (m)，因此，由带余数除法，有 (m) = qd0 r，qZ，q > 0，0 r < d0。 因此，由上式及d0的定义，利用欧拉定理得到 qdr1 a(m)a0ar(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是素数，pbn 1，nN，则下面的两个结论中至少有一个成立： (ⅰ) pbd 1对于n的某个因数d < n成立； (ⅱ) p 1 ( mod n )。 若2|n，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，则np 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. 3n15n2 B.n12n1 C.2n1n15n2 D.3n1 二、填空题 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)是否有解。 解：把429563看成Jacobi符号,我们有 42915631429214292.25635631348563(1)429429429267429429(1)674296714291271671672.2429(1)4294292.267672767(1)67276727 27113113(12.22727)131131， 故方程x2 429 (mod 563)有解。 2、求出模23的所有的二次剩余和二次非剩余。 解：模23的所有的二次剩余为 x1,2,3,4,6,8,9,12,13,16,18 (mod 23)； 模23的所有的二次非剩余为 x5,7,10,11,14,15,17,19,20,21,22 (mod 23)。 3、试求出所有正整数n ，使得1n＋2n＋3n＋4n 能被5整除。 解：若n为奇数，则1n＋2n＋3n＋4n1n＋2n＋（-2）n＋（-1）n 0 (mod 5)； 若n=2m，m∈Z，则1n＋2n＋3n＋4n12m＋22m＋（-2）2m＋（-1）2m 2+2×22m =2+2×4m =2+2×(-1)m(mod 5)； 18 -） 当m为奇数时，1n＋2n＋3n＋4n0(mod 5)； 当m为偶数时，1n＋2n＋3n＋4n4(mod 5)。 故当4|n时，5∣1n＋2n＋3n＋4n 。 四、证明题 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 证明：因为（m,n）=1，所以由欧拉定理知： n (m) ≡1 (mod m)，m(n) ≡1 (mod n) 于是 m(n)+n (m) ≡1 (mod m)， m(n)+n (m) ≡1 (mod n)。 又因为（m,n）=1，所以 m(n)+n (m) ≡1 (mod mn)。 注：此题也可这样表述：若两个正整数a,b互质，则存在正整数m,n，使得 am+bn≡1(mod ab)。 apbp3、设（a,b）=1,a+b≠0,p为一个奇质数，证明：(ab,)1或p。 abapbp 说明：事实上，设(ab,)d，只需证明：d | p 即可。 ab证明：由a+b≡0(mod a+b)，即a≡-b (mod a+b)，知ak≡(-b)k (mod a+b)。 ppab其中0≤k≤p-1。又 ap1ap2babp2bp1bp1bp1bp1pbp1(modab)。abapbpp-1 令(ab,。 又（a,b）=1，d |（a+b）知（d,b）=1。 )d，则d | pb ab（否则设（d,b）=d′＞1，立即得到d′︱a和d′︱b，这与（a,b）=1矛盾。） 于是（d ，bp-1）=1。故d | p，即 d =1或p。 19 初等数论练习题九 一、单项选择题 1、以下Legendre符号等于-1的30被-1是( D ) 3A. 114B. C. 115 D. 116 112、100至500的正整数中，能被17整除的个数是( B ) A. 23 B. 24 C. 25 D. 26 3、设 3|500!，但31，则α=( 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，tZ。 4、323 =1。 41B.（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 54t5u解(2)得 ， uZ， z2003uxu8v再解3x 8y =5u得到 ， u，vZ。 yu3vxu8v故 yu3v， u, vZ。 z2003u2、设A = {x1, x2, , xm}是模m的一个完全系，以{x}表示x的小数部分，若(a, m) = 1，求{i1maxib}。 m解：当x通过模m的完全剩余系时，ax b也通过模m的完全剩余系，因此对于任意的 i（1 i m），axi b一定与且只与某个整数j（1 j m）同余，即存在整数k，使得axi b = km j，（0 j m-1）。从而： m1m1m1axibjjj1m(m1)m1 {}{k}{}。mmmmm22i1j0j1j1m3、设整数n 2，求： 1in(i,n)1i。即在数列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}。 i112(m)m 21 其中{x}表示x的小数部分。 解：设axi = mqi ri，0 ri < m，由xi通过模m的简化剩余系知：axi也通过模m的简化剩 余系，从而ri通过模m的最小非负简化剩余系，于是： (m)(m)(m)axiriri1(m)11{}{q}rm(m)(m)。 iimmmm2m2i1i1i1i1四、证明题 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，p是奇质数，p∣an-1,则3、证明：若2p1。 证明：由p∣an-1知：an 1(mod p)。又（p，a）=1得到an+1 a(mod p)。 |n，所以(a 因为2n122a)a(modp)，即x2 a(mod p)有解。故 p1。 m（）1。 4、证明：若p=4m+1是一质数，则pm4m1 证明：（）（）()(1)pppp12(1)2m1。 p12)!) 1 (mod p) 25、设p是奇质数，p 1 (mod 4)，则：((解 由Wilson定理有： 22 1(p1)!(1)p12(p1)!(1)p1212p1p1p12 (p1)(()!)(modp)。222注：（1）设p为质数且p＝4m+1，则同余方程x21(modp)的解是x12(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。 p121(modp) 6、写出模12的一个最小非负简化系，要求每项都是7的倍数，此简化系为{7,35,49,77}。 7、已知563是质数，则三、计算题 1、若3是质数p的平方剩余，问p是什么形式的质数？ 23 2=-1。 5633解：∵ 由二次互反律(1)pp12p， 3p1p1(mod3)注意到p>3，p只能为p1(mod 4)且 31p1(mod3)∴ 3p1(mod3) ，只能是下列情况1pp1(mod4)p1(mod3) p1(mod4)∴ p1(mod12)或p1(mod12)。 2、求使12347!被35k整除的最大的k值。 解：k=2054. 四、证明题 1、证明：设p7是一个质数，则存在唯一的一个正整数x，使得： x1,2,,p1且120p-6!x0modp 证明：存在性：因为p7是一个素数，由Wilson定理我们有：p1!10modp， 然而p1!p1p2p3p4p5p6!120p6!modp，所以120p6!p10modp， 故存在xp1，使得120p-6!x0modp。 唯一性：若还存在y1,2,,p1且120p-6!y0modp， ,p1，所以xy是唯一的。 则xymodp，注意到x,y1,2,2、已知9901是素数，试证：9901(1749501)。 证明：由9901是素数，计算Legendre符号得： 171990117117131711799017173712222221111990117177733 所以17是模9901的平方非剩余，因此由Euler判别条件可知： 179901121mod9901 即 9901(1749501)。 3、证明：若p=10n-1是个质数，则p55n11。（提示：利用勒让德符号解决。） 说明：要证p55n11，只需证明55n11(modp)，即证： 24 55n1510n1125p121(modp) 这样就转化为证明：(5)1。 p 证明：因为(5)(p)(10n1)(1)1(modp)。 p555 所以55n1510n1125p121(modp)。 故：p55n11。 4、设p=4n+3是质数，证明当q=2p+1也是质数时，梅森数Mp=2p-1不是质数。 由此证明：23|（211-1），47|（223-1），503|（2251-1）。 证明：由条件：q=2p+1=8n+7-1(mod 8)，从而：(p)=1， q即12q1224n+32p （mod q)，于是q|（2p-1）。故：梅森数Mp=2p-1不是质数。 当n=2，n= 5，n=62时立得：23|（211-1），47|（223-1），503|（2251-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的质数，则 (p1)!p1Z。 p(p1)说明：只需证明：p(p+1) | (p-1)!+p+1。又因为(p，p+1)=1，所以需证： p | (p-1)!+p+1 与(p+1) | (p-1)!+p+1同时成立即可。 证明：由Wilson定理：p1!10modp知：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。即 (p1)!p1Z。 p(p1) 25 因篇幅问题不能全部显示，请点此查看更多更全内容