1、初等数论作业(第三章)1. 证明: 若n为正整数, a为实数, 则(1) ,(2) .证明:(1) 设na=nq+r+na, 0rn, 则na=nq+r,左边=, 右边=所以.(2) 设na=nq+r+na, 0rn, 则na=nq+r, a=q+(r+na)/n. r=0时, a=q+na/n, 左边=q+q+q=nq. 右边=nq. r1时, 左边=nq+=nq+0+n-1-(n-r)+1=nq+r=na=右边. #2. 证明不等式2a+2ba+a+b+b证明:设a=m+a, b=n+b, m, nZ, 0a, b0, b0, n0, 满足n|an-bn, 则n|(an-bn)/(a-b)
2、.证明: 设pm|n, p为一个素数, a-b=t, 若pt, 则由pm|an-bn, 自然有pm|(an-bn)/t. 现设p|t, 而=因为 (1)在i=1, 2, , n时, i!中含p的最高方幂是又因pi-1|ti-1, pm|n, 故由(1)可知pm|.即 pm|(an-bn)/(a-b). 把n作因子分解并考察每一个素因子, 这就证明了n|(an-bn)/(a-b). #4. 证明: 若n5, 2bn, 则. (1)证明: 若bn, 则b(b-1)|(n-1)!, 即, 且Z, 故(1)成立. 若b=n, n是一个合数且不是一个素数的平方, 可设b=n=rs, 1rsn, 由(n,
3、 n-1)=1知sn-1, 故b(b-1)=rs(n-1)|(n-1)!, (1)式成立. 若b=n=p2, p是一个素数, 由n=p25知, 1p2pp2-1=n-1, 故p, 2p, n-1是小于n的三个不同的数. 故p2p(n-1)=2b(b-1)|(n-1)!, 故(1)式成立.若b=n=p, p是一个素数, 由(p-1)!+10 (mod p)知即, 而(p, p-1)=1知(p-1), (1)成立. #5. 证明: 对于任意的正整数n, 是一个整数. 证明: 因为vp(2n)!)=, vp(n)!)=, vp(n+1)!)=. 所以只需证 i1, . (*)设n=qpi+r, 0r
4、pi, 则若rpi-1, 则(*)式成立. 若r=pi-1, 则而,故此时(*)式也成立. 所以 Z. #6. 证明: 设, 则(1) 是一个整数;(2) 如n是一个素数, 而max(n1, , nk)n, 则.证明:(1) 证法一 只需设n1, n2, nk均为正数, 设p为任意素数, 则vp(n)!)=, vp(nj)!)=, 只需证对i1均成立, 而由P64 性质2知这是显然的, 故Z.证法二 n=2时, , 假设n-1时结论成立, 则当n时(由归纳假设知, 又Z.) (2) 若n是素数, 且max(n1, n2,nk)n, 故n|n!, 而nn1!, n2!, , nk!, 所以. #
5、7. 证明: 如果在自然数列1a1a2n, 则k.证明:断言: 对于2n的任意n+1个正整数中, 至少有一个被另一个所整除. 设1a1a2an+12n, ai=2libi, li0, 2bi, 1in+1, 其中bi2n. 因为在1, 2, , 2n中只有n个不同的奇数1, 3, , 2n-1, 故b1, b2, , bn+1中至少有两个相同. 设bi=bj, 1ijn+1, 于是在ai=2libi和aj=2ljbi中, 由aiaj知li 当n=2t时, k, 故a1, , ak为k(kt+1)个小于等于2t的数, 故$ i, j, 1i=t+1, 因为1, 2, , n=2t+1中只能有t+
6、1个奇数, 故k个数a1, a2, , ak中有一对数i, j, 1i0, 则.证明:若$ d, 使得j(d)=k,则(1) 22|d, 则u(d)=0不考虑. (2) 2|d, 则(d/2, 2)=1, 所以j(d)=j(2d/2)=j(2)j(d/2)=j(d/2)=k. 而 u(d)+u(d/2)=0. (3) 2d, 则j(2d)=j(2)j(d)=j(d)=k, 而u(2d)+u(d)=0. 故u(d)0|u(d)=k可分成若干对, 每对为u(d)+u(2d)=0. 故. #9. 证明.证明:由u(n)的定义有,当n中不含有平方因子时, 显然当n中含有平方因子时, 设n=n02m,
7、n01, m不含平方因子, 则.故u2(n). #其实, 采用类似的方法可证.10. 证明: 对于任一个素数p,.证明:n=1结论显然. 若n=pa, a1, 则.若(n, p)=1, 则.若n=pan1, n11, 则 #11. 证明证明:n=1时结论显然.n1时, 由于u(n), j(n)均是积性函数, 所以u2(d)/j(d), 也是积性函数. 设n=p1a1psas, 则右边=.左边=.故 . #12. 证明: 的充分必要条件是.证明:设n=, p1, , pk为不同的素数, ai1, i=1, 2, , k. =所以, . #13. 证明: .证明:n=1时结论显然.假设对n=k时成
8、立, 即.则n=k+1时, 有=. #证法二 因为, 所以. #14. 计算S(n)=.解:若n=1, S(1)=1,若n=p1pk, 则S(n)=u(1)u(p1p2pk)+u(p1)u(p2pk)+u(pk)u(p1pk-1)+u(p1p2pk)u(1)=(-1)k()=2k(-1)k若n=p12p2pk, 则S(n)=其余情形S(n)=0. # 15. 证明: n是素数的充分必要条件是s(n)+j(n)=nd(n). 证明:“” 若n为素数, 则s(n)=1+n, j(n)=n-1, d(n)=2, 所以有s(n)+j(n)=nd(n). “” n, d(n), j(n), s(n)均是
9、极性函数, 若n不为素数的方幂, n=n1n2, (n1, n2)=1, s(n1n2)+j(n1n2)=s(n1)s(n2)+j(n1)j (n2)(s(n1)+j(n1)( s(n2)+ j (n2)=n1n2d(n1n2).若n=pa, a1, s(n)=1+p+pa-1+pa, j(n)=pa-pa-1, d(n)=a+1, 1+p+pa-2+2pa=(a+1)pa, 只有a=1时s(n)+j(n)=nd(n)才成立, 即n是素数. #16. 证明: 如果有正整数n满足j(n+3)=j(n)+2, (1)则n=2pa或n+3=2pa, 其中a1, p3(mod4), p是素数.证明:经
10、验证可知n=1, 2不满足(1)式, 设n2, 则j(n), j(n+3)均为偶数. 由(1)知j(n)和j(n+3)不能同时被4整除, 故只能有j(n)2 (mod 4), j(n+3)0 (mod 4)或j(n)0 (mod 4), j(n+3)2 (mod 4). 令n=2a1p2a2pkak, 则j(n)=2a1-1p2a2-1(p2-1)pkak-1(pk-1). 由于j(n)中2a1-1, (p2-1), , (pk-1)均被2整除, 若j(n)2 (mod 4), 则n只能含有一个奇素数因子, 因此n有三种情况: (1) n=2a1, 此时a1=2, 故n=4; (2) n=p2
11、a2, 此时p2满足p23 (mod 4); (3) n=2a1p2a2, 此时a1=1, p23 (mod 4), 即n=2p2a2. 因为j(4)j(1)+2, 所以若j(n+3)2 (mod 4), 经类似的分析可得n+3=pa, 2pa, a1, p3 (mod 4). 设n=pa, 由(1)得j(pa+3)=pa-pa-1+2 (2)设2t|pa+3, t1, 由(2)得pa-pa-1+2=j(2t(pa+3)/2t)=2t-1j( (pa+3)/2t )2t-1( (pa+3)/2t-1)=(pa+3)/2-2t-1即有 pa-pa-1+2(pa+3)/2-1, 化简得pa2pa-
12、1-3, 也即3pa-1(2-p)由于p2, 故3pa-1(2-p)不能成立. 同样可证n+3=pa时, (1)式不成立, 故n=2pa或n+3=2pa. #17. 证明j(n)n/d(n).证明:设n的标准分解式为, 故j(n)d(n)=n(1-1/p1)(1-1/ps)(l1+1)(ls+1)n(1/2)s2s=n于是得j(n)n/d(n). #18. 求出满足j(mn)=j(m)+j(n) (1)的全部正整数对(m,n).解:设(m ,n)=d, 则从j(n)的公式不难有j(mn)=dj(m)j(n)/j(d), 由(1)得j(m)+j(n)=dj(m)j(n)/j(d), (2)设j(
13、m)/j(d)=a, j(n)/j(d)=b, a, b都是正整数, (2)化为1/a+1/b=d (3)d2时, 易证(3)无正整数解, 在d=1和d=2时, (3)分别仅有正整数解a=b=2和a=b=1. 在d=1, a=b=2时, j(m)=j(n)=2, 因此(m, n)=(3, 4), (4, 3); 在d=2, a=b=1时, j(m)=j(n)=1, 于是(m, n)=(2, 2). #19. 若n0, 满足24|n+1, 则24|s(n).证明:由24|n+1知n-1(mod 3)和n-1(mod 8), 设因子d|n, 则3d, 2d, 可设d1, 2 (mod 3), d1
14、, 3, 5, 7(mod 8). 因为d(n/d)=n-1 (mod 3)和d(n/d)=n-1(mod 8), 由此推出, d1 (mod 3), n/d2 (mod 3)或d2 (mod 3), n/d1 (mod 3), 和d3 (mod 8), n/d5 (mod 8)或d5 (mod 8), n/d3 (mod 8)或d1 (mod 8), n/d7 (mod 8)或d7 (mod 8), n/d1 (mod 8).每一种情形都有d+n/d0 (mod 3), d+n/d0 (mod 8), 故d+n/d0 (mod24). 又若d=n/d, 则n=d2, d1, 则因为2n, 所
15、以2d, 但n=d21 (mod8)矛盾. 所以n的所有正因子可以配对, 每对为d, n/d, 故24|s(n). #20. 证明: 若n=p1a1 p2a2 pkak, k8, 则j(n)n/6.证明:j(n)=而pi越大, 1-1/pi越大, 故只要证p1, p2, , p8为前8个素数时, j(n)n/6成立即可, 即要证, 而左边=, 即结论成立. #21. 设w(1)=0, n1, w(n)是n的不同的素因子的个数, 证明:f(n)=w(n)*m(n)=0或1.证明:若n=pa (a2)f(n)=w(n)*u(n)=u(1)w(pa)+u(p)w(pa-1)=u(1)1+(-1)1=
16、0.若n=p, f(n)=w(n)*u(n)=w(1)u(p)+w(p)u(1)=1若n=p1a1 p2a2 pkak, k2, 则f(n)=w(n)*u(n)=0 #22. 设f(x)的定义域是0,1中的有理数, F(n)=, F*(n)=,证明: F*(n)=m(n)*F(n).证明: 由Mobius变换定理知, 等价于证明F(n)=F*(n)*e(n), 即要证F(n)=.而对于r/n, r=1, 2, , n的每个分数, 既约后均为k/d, d|n, kd, (k, d)=1的形式, 即为某个r/n, 1rn. 故, 即F(n)=, 再由Mobius逆变换即得. #23. 证明: 若f
17、(n)是完全积性函数, 则对所有的数论函数g(n),h(n), 有f(n)(g(n)* h(n)=(f(n)g(n)*(f(n)h(n).证明:f(n)(g(n)*h(n)=f(n)()=(f(n)g(n)*(f(n)h(n) #24. 证明: 若f(n)和f1(n)各为g(n)和g1(n)的麦比乌斯变换, 则.证明:f(n)=, f1(n)=,令b=n/d, 则(n/d)|(n/a)a|d. 于是.故与展开式中每一项均相等, 因此. #证法二f=g*e, f1=g1*e, 则f*g1=g*e*g1=g*g1*e=g*(g1*e)=g*f1. #25. 设f(x)是一个整系数多项式, y(n)
18、代表f(0), f(1),f(n-1) (1)中与n互素的数的个数, 证明:(1)y(n)是积性数论函数;(2)y(pa)=pa-1(p-bp), bp代表(1)中被素数p整除的数的个数.证明:(1) 需证 (m, n)=1, f(0), f(1), , f(n-1)f(n), f(n+1), , f(2n-1)f(m-1)n), f(m-1)n+1), , f(m-1)n+n-1)中与mn互素的个数为y(m)y(n)个. 又f(x)为整系数多项式, 故f(i+n)f(i) mod nf(i+m)f(i) mod m故上述mn个数中每一行与n互素的有y(n)个, 所以f(0), f(1), .
19、, f(m-1)n+n-1)中共有my(n)个与n互素的数. 而f(i), f(n+i), , f(m-1)n+i)由于i, n+i, , (m-1)n+i恰好通过mod m的一组完系, 所以上述my(n)个与n互素的数中有y(m)y(n)个与m互素, 因此有y(mn)=y(m)y(n). (2) (a, pa)=1(a, p)=1, 而f(0), f(1), , f(p-1)f(p), f(p+1), , f(2p-1)f(pa-1-1)p), f(pa-1-1)p+1), , f(pa-1-1)p+p-1)每一行与p互素个数为p-bp, 于是y(pa)=pa-1(p-bp). #26. 证
20、明证明:因为d为积性函数, 故d3, d3*e, (d*e)2均为积性函数, 故只需对n=1及n=pa证明上式即可!n=1时, 左边=1=右边, 故命题成立. n=pa时, p为素数, a1时. #27. 找出所有的正整数n分别满足(1) j(n)=n/2; (2) j(n)=j(2n); (3) j(n)=12.证明: 设n=p1a1 p2a2 pkak, p1p2pk, 则j(n)=n(1-1/p1)(1-1/pk).(1) 若j(n)=n/2, 则(1-1/p1)(1-1/pk)=1/2.若t=1, 则p1=2, n=2a即为所求. 若p12, (1-1/p1)(1-1/pk)=1/2,
21、 则2(p1-1)(pk-1)=p1p2pk, 而p1, p2, , pk均为不同的奇素数, 所以此时j(n)=n/2不成立. (2) 若n为奇数, p1, p2, , pk均为不同的奇素数, 则.若n为偶数, 设p1=2, 则.所以当n是奇数时, j(n)=j(2n). (3) 若j(n)=p1a1-1(p1-1) p2a2-1(p2-1) pkak-1(pk-1)=12, 则pi-1|12, i=1, 2, , k. 故pi2, 3, 5, 7, 13且k3, ai3, i=1, 2, , k. 则若2n, j(n)=12, 则n = 13, 37; 若2|n, 则n=213, 237;
22、若4|n, 则n=47. 若2k|n (k3), 则j(n)=j(2k)j(n/2k)=2k-1j(n/2k)=12没有整数解, 所以j(n)=12的解只有n=13, 37, 213, 237, 47. #28. 证明: 设pn表示第n个素数, 则存在正常数C1,C2使C1 nlognpn1时, logxx/2, 所以loglogpnlogpn/2. 所以由(3)式, 有logpn/2log8n. logpn2log8n8logn (因为n2, (8n)2n8)再由(2)有, pn nlogn/12, 故取C1=1/12即可. 即(1/12) nlognpnn, (fm,fn)=f(m,n).
23、 若m=n, 显然. 事实上, 设m=nq+r, 0rn.(因若n|m, 由(2)显然).由(1)及(2)有: (fm,fn)=(fnq+r,fn) =(fnq-1fr+fnqfr+1,fn) (fnq-1fr,fn)而fn|fnq, (fnq-1,fnq)=1, (fnq-1,fn)=1,(fm,fn)=(fr,fn)令n=q1r+r0, 同上又有(fr,fn)=(fr,fr0)=f(m,n). #30. 证明: 设f(n)是一个积性函数, 则对素数的方幂pa(a1)有f(pa)=f(p)a,则f(n)是完全积性函数.证明:设m=p1a1 p2a2 pkak, n=p1b1 p2b2 pkbk, ai0, bi0, i=1, 2 , , k. f(m)=f(p1a1 p2a2 pkak)=f(p1a1)f(pkak)=f(p1)a1f(pk)ak.同理, f(n)=f(p1)b1f(pk)bk. 所以f(mn)=f(p1a1+b1p2a2+b2 pkak+bk)=f(p1)a1+b1f(pk)ak+bk. #31. 证明: 若F(n),f(n)是两个数论函数, 则F(n)=f(d)的充分必要条件是f(n)=F(d)m(n/d).证明:“”= (d=d1t)=f(n)“” = (d=d1t)=F(n) #17
浙ICP备2021020529号-1 | 浙B2-20240490 
