初等数论习题(第三章)

1初等数论作业(第三章)1.证明:若n为正整数,为实数,则(1)][][nn,(2)nnnn1...1.证明:(1)设nnqr{n},0rn,则[n]nqr,左边qnrqnrnqnn][,右边qnnrqnnrnqnn}{}{所以nn][.(2)设nnqr{n},0rn,则[n]nqr,q(r{n})/n.r0时,q{n}/n,左边qq…qnq.右边nq.r1时,左边nnnrqnnrqnnrq1}{...1}{}{nq101}{}{rnknrnknknrnknrnq0n1(nr)1nqr[n]右边.#2.证明不等式[2][2][][][]证明:设ma,nb,m,nZ,0a,b1.不妨设ab,则[2][2][2m2a][2n2b]2m2n[2a][2b]2而[][][][ma][nb][mnab]2m2n[a][b][ab]2m2n[ab]下证[2a][2b][ab]而ab,故[2a][ab],自然有[2a][2b][ab].#3.证明:若a0,b0,n0,满足n|anbn,则n|(anbn)/(ab).证明:设pm||n,p为一个素数,abt,若p|t,则由pm|anbn,自然有pm|(anbn)/t.现设p|t,而tbtbtbannnn)(niiintbin11因为!)1)...(1(11itbinnntbiniiniin(1)在i1,2,…,n时,i!中含p的最高方幂是111kkkkipipipi又因pi1|ti1,pm|n,故由(1)可知pm|nitbiniin,...,1,1.即pm|(anbn)/(ab).把n作因子分解并考察每一个素因子,这就证明了n|(anbn)/(ab).#4.证明:若n5,2bn,则bnb)!1(1.(1)3证明:若bn,则b(b1)|(n1)!,即bnb)!1(1,且bn)!1(Z,故(1)成立.若bn,n是一个合数且不是一个素数的平方,可设bnrs,1rsn,由(n,n1)1知sn1,故b(b1)rs(n1)|(n1)!,(1)式成立.若bnp2,p是一个素数,由np25知,1p2pp21n1,故p,2p,n1是小于n的三个不同的数.故p2p(n1)2b(b1)|(n1)!,故(1)式成立.若bnp,p是一个素数,由(p1)!10(modp)知pppppppppp)1()!1(11)!1(11)!1()!1(即)1()!1()!1(ppppp,而(p,p1)1知(p1)pn)!1(,(1)成立.#5.证明:对于任意的正整数n,)!1(!)!2(nnn是一个整数.证明:因为vp((2n)!)12iipn,vp((n)!)1iipn,vp((n1)!)11iipn.所以只需证i1,iiipnpnpn12.(*)设nqpir,0rpi,则若rpi1,则,,1qpnqpnii(*)式成立.若rpi1,则,,11qpnqpnii而iiiiiipnpnqppqppqpni1121122222,故此时(*)式也成立.所以)!1(!)!2(nnnZ.#46.证明:设kjjnn1,则(1)!!...!!21knnnn是一个整数;(2)如n是一个素数,而max(n1,…,nk)n,则!!...!!|21knnnnn.证明:(1)证法一只需设n1,n2,…,nk均为正数,设p为任意素数,则vp((n)!)1iipn,vp((nj)!)kjpniij0,1,只需证kjijikpnpnn11...对i1均成立,而由P64性质2知这是显然的,故!!...!!21knnnnZ.证法二n2时,Znnnnnn111)!(!!,假设n1时结论成立,则当n时Znnnnnnnnnnnnnnnnnnnnkkkk)!()!...)((!!)!(!!...!)!...(!!...!!213212121212121(由归纳假设知Znnnnnnk)!()!...)((21321,又!!)!(2121nnnnZ.)(2)若n是素数,且max(n1,n2,…,nk)n,故n|n!,而n|n1!,n2!,…,nk!,所以!!...!!|21knnnnn.#7.证明:如果在自然数列1a1a2…akn中,任意两个数ai,aj的最小公倍数[ai,aj]n,则k21n.证明:断言:对于2n的任意n1个正整数中,至少有一个被另一个所整除.5设1a1a2…an12n,ai2ibi,i0,2|bi,1in1,其中bi2n.因为在1,2,…,2n中只有n个不同的奇数1,3,…,2n1,故b1,b2,…,bn1中至少有两个相同.设bibj,1ijn1,于是在ai2ibi和aj2jbi中,由aiaj知ij.故ai|aj.若k,21n当n2t时,ktn21,故a1,…,ak为k(kt1)个小于等于2t的数,故i,j,1ijk,使得ai|aj.故[ai,aj]ajn,矛盾!若n2t1,则k21nt1,因为1,2,…,n2t1中只能有t1个奇数,故k个数a1,a2,…,ak中有一对数i,j,1ijk,使得ai|aj,所以[ai,aj]ajn矛盾.故k21n.#8.证明:若k0,则kddu)(0)(.证明:若d,使得(d)k,则(1)22|d,则u(d)0不考虑.(2)2||d,则(d/2,2)1,所以(d)(2d/2)(2)(d/2)(d/2)k.而u(d)u(d/2)0.(3)2|d,则(2d)(2)(d)(d)k,而u(2d)u(d)0.故{u(d)0|u(d)k}可分成若干对,每对为u(d)u(2d)0.故kddu)(0)(.#9.证明ndnudu|22)()(.证明:由u(n)的定义有中含有平方因子中不含有平方因子nnnu,0,1)(2,当n中不含有平方因子时,显然6ndudu|21)1()(当n中含有平方因子时,设nn02m,n01,m不含平方因子,则0)()()()(1||.||02022022ndndmndnddudududu.故nddu|2)(u2(n).#其实,采用类似的方法可证其它若,11,|,0)(|mnmdukndk.10.证明:对于任一个素数p,ndnpnndpudu|,01,,21,1)),(()(是其余情形若若若.证明:n1结论显然.若np,1,则2)()()1()1()),(()(|pupuuudpudund.若(n,p)1,则0)()),(()(||ndnddudpudu.若npn1,n11,则0)()()()()()()),(()(111|1|),(|1),(||ndndppdndpdndndpududupudududpudu#11.证明ndddunn|2)()()(证明:n1时结论显然.n1时,由于u(n),(n)均是积性函数,所以u2(d)/(d),ndddu|2)()(也是积性函7数.设np11…pss,则右边skskskkkkkkkkpppppuppukk111221111)()(...)()(1.左边skkkskksskkssppppppppppss111111111)1(...1......11.故ndnnddu|2)()()(.#12.证明:ndddu|0)()(的充分必要条件是)2(mod0n.证明:设nkkpp...11,p1,…,pk为不同的素数,i1,i1,2,…,k.)...()...(...)()()1()1()()(111|kkkiiindppppuppuuddukiikkiipp11)1()1(...)1)(1(1kiip1)11(所以,npdduind|220)()(|某个.#13.证明:)0(2)1()(1nnndndnd.证明:n1时结论显然.假设对nk时成立,即2)1()(1kkdkdkd.则nk1时,有)1(1)()(1)(1111kdkdkddkddkdkdkdkd8)1()(2)1(11|kdkkkdkd1|)(2)1(kddkk12)1(kkk2)2)(1(kk.#证法二因为dnkdn11,所以dnkndndddnd1111)()(dnkndd11)(nkkndd11)(nkknk1)()(1kknnk)(...)3(3)2(2)1(nnnnndddddd|2|1|)(...)()(n...212)1(nn.#14.计算S(n)nddnudu|)(.解:若n1,S(1)1,若np1…pk,则S(n)nddnudu|)(u(1)u(p1p2…pk)u(p1)u(p2…pk)…u(pk)u(p1…pk1)…u(p1p2…pk)u(1)(1)k(kkkkCCC...10)2k(1)k若np12p2…pk,则S(n)ndkkpppupudnudu|1211)1()...()()(9其余情形S(n)0.#15.证明:n是素数的充分必要条件是(n)(n)nd(n).证明:“”若n为素数,则(n)1n,(n)n1,d(n)2,所以有(n)(n)nd(n).“”n,d(n),(n),(n)均是极性函数,若n不为素数的方幂,nn