数论-第三章

第三章 同 余§1 同余的概念及其基本性质。

，所有奇数；所有偶数，例如，。

不同余，记作：对模则称；若所得的余数不同，同余，记作：对模则称所得的余数相同，与去除两个整数，称之为模。

若用设)2(mod 1)2(mod 0)7(mod 18)(mod ,)(mod ,≡≡≡≡/≡∈+a a m b a m b a m b a m b a b a m m Z 定义1。

故同余关系是等价关系；（传递性），则，、若；（对称性），则、若；（反身性）、：关系，它具有下列性质同余是整数之间的一种)(mod )(mod )(mod 3)(mod )(mod 2)(mod 1m c a m c b m b a m a b m b a m a a ≡≡≡≡≡≡。

则，，，设。

，，即同余的充分必要条件是对模整数)(|)()(mod ,0)(|,2121212211b a m q q m b a r r m b a m r r r mq b r mq a t mt b a b a m m b a -⇔-=-⇔=⇔≡<≤+=+=∈+=-证明定理1Z。

，则若；，则，若)(mod )(mod )2()(mod )(mod )(mod )1(21212211m b c a m c b a m b b a a m b a m b a -≡≡++≡+≡≡性质1。

，则特别地，若；，则，若)(mod )(mod )(mod )(mod )(mod 21212211m kb ka m b a m b b a a m b a m b a ≡≡≡≡≡性质2。

，则，；特别地，若则，，，若)(mod ,,2,1,0)(mod )(mod ,,2,1)(mod )(mod 0110111111111111m b x b x b a x a x a n i m b a m y y Bx x Ak i m y x m B A n n n n n n n n i i k k i i kk kkk kk k +++≡+++=≡≡=≡≡----∑∑ αααααααααααααααα定理2。

数论讲义答案(第三章)1. 证明: 若n 为正整数, α为实数, 则(1) ][][αα=⎥⎦⎤⎢⎣⎡n n , (2) [][]ααααn n n n =⎥⎦⎤⎢⎣⎡-+++⎥⎦⎤⎢⎣⎡++1...1. 证明:(1) 设n α = nq + r + {n α}, 0 ≤ r < n , 则[n α] = nq + r ,左边 = q n r q n r nq n n =⎥⎦⎤⎢⎣⎡+=⎥⎦⎤⎢⎣⎡+=⎥⎦⎤⎢⎣⎡][α, 右边 = []q n n r q n n r nq n n =⎥⎦⎤⎢⎣⎡++=⎥⎦⎤⎢⎣⎡++=⎥⎦⎤⎢⎣⎡=}{}{αααα 所以[]αα=⎥⎦⎤⎢⎣⎡n n ][. (2) 设n α = nq + r + {n α}, 0 ≤ r < n , 则[n α] = nq + r , α = q +( r + {n α})/n . r = 0时, α = q +{n α}/n , 左边 = q + q + … + q = nq . 右边 = nq .r ≥ 1时, 左边 = ⎥⎦⎤⎢⎣⎡-+++++⎥⎦⎤⎢⎣⎡++++⎥⎦⎤⎢⎣⎡++n n n r q n n r q n n r q 1}{...1}{}{ααα = nq +∑∑--=--=⎥⎦⎤⎢⎣⎡+++⎥⎦⎤⎢⎣⎡++11}{}{r n k n r n k n k n r n k n r αα = nq + 0 + n - 1 - (n - r ) + 1 = nq + r=[n α] = 右边. #2. 证明不等式[2α] + [2β] ≥ [α] + [α + β] + [β]证明:设α = m + a , β = n + b , m , n ∈Z , 0 ≤ a , b < 1. 不妨设a ≥ b , 则 [2α] + [2β] = [2m +2a ] + [2n + 2b ]= 2m + 2n + [2a ] + [2b ]而[α] + [α + β] + [β] = [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. 证明: 若a > 0, b > 0, n > 0, 满足n | a n - b n , 则n | (a n - b n )/(a -b ).证明:设p m || n , p 为一个素数, a - b = t , 若p |/t , 则由p m | a n - b n , 自然有p m | (a n - b n )/t . 现设p | t , 而tb t b t b a nn n n -+=-)( = ∑=--⎪⎪⎭⎫ ⎝⎛ni i i n t b i n 11因为!)1)...(1(11i t b i n n n t b i n i i n i i n ----+--=⎪⎪⎭⎫ ⎝⎛ (1) 在i = 1, 2, …, n 时, i !中含p 的最高方幂是∑∑∞=∞=≤-=<⎥⎦⎤⎢⎣⎡111k k kk i p ip i p i 又因p i -1 | t i -1, p m | n , 故由(1)可知p m | n i t b i n i i n ,...,1,1=⎪⎪⎭⎫ ⎝⎛--.即 p m | (a n - b n )/(a -b ). 把n 作因子分解并考察每一个素因子, 这就证明了n | (a n - b n )/(a -b ). #4. 证明: 若n ≥ 5, 2 ≤ b ≤ n , 则⎥⎦⎤⎢⎣⎡--b n b )!1(1. (1) 证明:若b < n , 则b (b -1) | (n -1)!, 即⎥⎦⎤⎢⎣⎡--b n b )!1(1, 且⎥⎦⎤⎢⎣⎡-b n )!1(∈Z , 故(1)成立. 若b = n , n 是一个合数且不是一个素数的平方, 可设b = n = rs , 1 < r < s < n , 由(n , n -1) = 1知s < n -1, 故b (b -1) = rs (n -1) | (n -1)!, (1)式成立.若b = n = p 2, p 是一个素数, 由n = p 2 ≥ 5知, 1 < p < 2p < p 2 - 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 (mod p )知p p p p p p p p p p )1()!1(11)!1(11)!1()!1(---=-+-=⎥⎦⎤⎢⎣⎡-+-=⎥⎦⎤⎢⎣⎡- 即)1()!1()!1(---=⎥⎦⎤⎢⎣⎡-p p p p p , 而(p , p -1) = 1知(p -1)⎥⎦⎤⎢⎣⎡-p n )!1(, (1)成立. #5. 证明: 对于任意的正整数n ,)!1(!)!2(+n n n是一个整数.证明: 因为pot p ((2n )!) = ∑∞=⎥⎦⎤⎢⎣⎡12i i p n , pot p ((n )!) = ∑∞=⎥⎦⎤⎢⎣⎡1i i p n , pot p ((n +1)!) = ∑∞=⎥⎦⎤⎢⎣⎡+11i i p n .所以只需证∀ i ≥ 1, ⎥⎦⎤⎢⎣⎡++⎥⎦⎤⎢⎣⎡≥⎥⎦⎤⎢⎣⎡i i i p n p n p n 12. (*)设n = qp i + r , 0 ≤ r < p i , 则若r < p i - 1, 则,,1q p n q p n i i =⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡+(*)式成立. 若r = p i - 1, 则,,11q p n q p n i i =⎥⎦⎤⎢⎣⎡+=⎥⎦⎤⎢⎣⎡+而⎥⎦⎤⎢⎣⎡+⎥⎦⎤⎢⎣⎡+=+≥⎥⎦⎤⎢⎣⎡-++=⎥⎦⎤⎢⎣⎡-+=⎥⎦⎤⎢⎣⎡i i i i i i p n p n q p p q p p q p n i 1121122222, 故此时(*)式也成立. 所以)!1(!)!2(+n n n ∈Z . #6. 证明: 设∑==kj j n n 1, 则(1)!!...!!21k n n n n 是一个整数;(2) 如n 是一个素数, 而max(n 1, …, n k ) < n , 则!!...!!|21k n n n n n .证明:(1) 证法一 只需设n 1, n 2,…, n k 均为正数, 设p 为任意素数, 则v p ((n )!) = ∑∞=⎥⎦⎤⎢⎣⎡1i i p n , v p ((n j )!) = k j p n i i j ≤≤⎥⎦⎤⎢⎣⎡∑∞=0,1, 只需证∑=⎥⎦⎤⎢⎣⎡≥⎥⎦⎤⎢⎣⎡++k j i j ik p n p n n 11...对∀i ≥ 1均成立, 而由P64 性质2知这是显然的, 故!!...!!21k n n n n ∈Z .证法二 n = 2时,Z n n n n n n ∈⎪⎪⎭⎫ ⎝⎛=-111)!(!!, 假设n - 1时结论成立, 则当n 时Z n n n n n n n n n n n n n n n n n n n n k k k k ∈++++++=+++=)!()!...)((!!)!(!!...!)!...(!!...!!213212*********(由归纳假设知Z n n n n n n k ∈+++++)!()!...)((21321, 又!!)!(2121n n n n +∈Z .)(2) 若n 是素数, 且max(n 1, n 2,…,n k ) < n , 故n | n !, 而n |/n 1!, n 2!, …, n k !, 所以 !!...!!|21k n n n n n . #7. 证明: 如果在自然数列1 ≤ a 1 < a2 < … < a k ≤ n中, 任意两个数a i , a j 的最小公倍数[a i , a j ] > n , 则k ≤ ⎥⎦⎤⎢⎣⎡+21n . 证明:断言: 对于≤2n 的任意n + 1个正整数中, 至少有一个被另一个所整除. 设1 ≤ a 1 < a 2 < … < a n +1 ≤ 2n , a i = 2λi b i , λi ≥ 0, 2|/b i , 1 ≤ i ≤ n +1, 其中b i < 2n . 因为在1, 2, …, 2n 中只有n 个不同的奇数1, 3, …, 2n -1, 故b 1, b 2, …, b n +1中至少有两个相同. 设b i = b j , 1 ≤ i < j ≤ n +1, 于是在a i = 2λi b i 和a j = 2λj b i 中, 由a i < a j 知λi < λj . 故a i | a j .若k > ,21⎥⎦⎤⎢⎣⎡+n 当n = 2t 时, k > t n =⎥⎦⎤⎢⎣⎡+21, 故a 1, …, a k 为k (k ≥ t +1)个小于等于2t 的数, 故∃ i , j , 1 ≤ i < j ≤ k , 使得a i | a j . 故[a i , a j ] = a j ≤ n , 矛盾!若n = 2t + 1, 则k > ⎥⎦⎤⎢⎣⎡+21n = t + 1, 因为1, 2, …, n = 2t + 1中只能有t + 1个奇数, 故k 个数a 1, a 2, …, a k 中有一对数i , j , 1 ≤ i < j ≤ k , 使得a i | a j , 所以[a i , a j ] = a j ≤ n 矛盾. 故k ≤ ⎥⎦⎤⎢⎣⎡+21n . # 8. 证明: 若k > 0, 则∑==kd d u )(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. 故∑==kd d u )(0)(ϕ. # 9. 证明∑=nd n u d u |22)()(.证明:由u (n )的定义有⎩⎨⎧=中含有平方因子中不含有平方因子n n n u ,0,1)(2, 当n 中不含有平方因子时, 显然∑==nd u d u |21)1()(当n 中含有平方因子时, 设n = n 02m , n 0 > 1, m 不含平方因子, 则0)()()()(1||.||0222022====∑∑∑∑>n d n d mn d nd d u d u d u d u .故=∑nd d u |2)(u 2(n ). #其实, 采用类似的方法可证⎩⎨⎧>=∑其它若,11,|,0)(|m n m d u k n d k. 10. 证明: 对于任一个素数p ,∑⎪⎩⎪⎨⎧≥===n d n p n n d p u d u | ,01, ,21,1)),(()(是其余情形若若若αα. 证明:n = 1结论显然. 若n = p α, α ≥ 1, 则2)()()1()1()),(()(|=+=∑p u p u u u d p u d u nd .若(n , p ) = 1, 则0)()),(()(||==∑∑nd nd d u d p u d u .若n = p αn 1, n 1 > 1, 则0)()()()()()()),(()(111|1|),(|1),(||=+=+=∑∑∑∑∑==n d n d pp d n d p d n d nd p u d u d u p u d u d u d p u d u #11. 证明∑=n d d d u n n |2)()()(ϕϕ 证明:n = 1时结论显然.n > 1时, 由于u (n ), ϕ(n )均是积性函数, 所以u 2(d )/ϕ(d ), ∑nd d d u |2)()(ϕ也是积性函数. 设n = p 1α1…p s αs , 则右边 = ∏∏∏===-=⎪⎪⎭⎫ ⎝⎛-+=⎪⎪⎭⎫ ⎝⎛+++sk s k s k kk k k k k k p p p p p u p p u k k 111221111)()(...)()(1ααϕϕ. 左边 =()∏∏∏===---=-=-sk k ksk kssk kssp p pp p pp p p p s s 111111111)1(...1 (11)αααα. 故 ∑=n d n n d d u |2)()()(ϕϕ. # 12. 证明: ∑=nd d d u |0)()(ϕ的充分必要条件是)2(mod 0≡n .证明:设n = k k p p αα (1)1, p 1, …, p k 为不同的素数, αi ≥ 1, i = 1, 2, …, k .)...()...(...)()()1()1()()(111|k kki iind p p pp u p p u u d d u ϕϕϕϕ+++=∑∑==∏∑==--++--+ki ikki i pp 11)1()1(...)1)(1(1=∏=--ki i p 1)11(所以,n pd d u ind |220)()(|⇔=∃⇔=∑某个ϕ. #13. 证明:)0(2)1()(1>+=⎥⎦⎤⎢⎣⎡∑=n n n d n d nd ϕ. 证明:n = 1时结论显然.假设对n = k 时成立, 即2)1()(1+=⎥⎦⎤⎢⎣⎡∑=k k d k d kd ϕ. 则n = k + 1时, 有)1(1)()(1)(1111++⎪⎪⎭⎫ ⎝⎛⎥⎦⎤⎢⎣⎡-⎥⎦⎤⎢⎣⎡++⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡+∑∑∑==+=k d k d k d d k d d k d kd k d k d ϕϕϕϕ =)1()(2)1(11|++++∑+<+k d k k k d k d ϕϕ = ∑+++1|)(2)1(k d d k k ϕ =12)1(+++k k k = 2)2)(1(++k k . #证法二 因为∑⎥⎦⎤⎢⎣⎡==⎥⎦⎤⎢⎣⎡d n k d n 11, 所以∑∑∑⎥⎦⎤⎢⎣⎡====⎥⎦⎤⎢⎣⎡d n k nd nd d d n d 1111)()(ϕϕ∑∑⎥⎦⎤⎢⎣⎡===d n k n d d 11)(ϕ∑∑=⎥⎦⎤⎢⎣⎡==nk k n d d 11)(ϕ∑=⎥⎦⎤⎢⎣⎡=n k k n k 1)(ϕ)(1k k n n k ϕ∑=⎥⎦⎤⎢⎣⎡= )(...)3(3)2(2)1(n n n n ϕϕϕϕ++⎥⎦⎤⎢⎣⎡+⎥⎦⎤⎢⎣⎡+=∑∑∑+++=nd d d d d d |2|1|)(...)()(ϕϕϕn +++=...21 2)1(+=n n . # 14. 计算S (n ) = ∑⎪⎭⎫⎝⎛n d d n u d u |)(.解:若n = 1, S (1) = 1, 若n = p 1…p k , 则S (n ) = ∑⎪⎭⎫⎝⎛nd d n u d u |)(= u (1)u (p 1p 2…p k ) + u (p 1)u (p 2…p k ) + … + u (p k )u (p 1…p k -1) +… + u (p 1p 2…p k )u (1)= (-1)k (k k kk C C C +++ (1)0) = 2k (-1)k若n = p 12p 2…p k , 则S (n ) = ∑+-==⎪⎭⎫⎝⎛nd k k p p p u p u d n u d u |1211)1()...()()(其余情形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 1n 2, (n 1, n 2) = 1,σ(n 1n 2) + ϕ(n 1n 2) = σ(n 1)σ(n 2) + ϕ(n 1)ϕ (n 2)≠ (σ(n 1)+ϕ(n 1))⋅( σ(n 2)+ ϕ (n 2)) = n 1n 2d (n 1n 2).若n = p α, α ≥ 1, σ(n ) = 1 + p + … + p α-1 + p α, ϕ(n ) = p α - p α-1, d (n ) = α + 1, 1 + p + … + p α-2 + 2p α = (α + 1)p α, 只有α = 1时σ(n ) + ϕ(n ) = nd (n )才成立, 即n 是素数. # 16. 证明: 如果有正整数n 满足ϕ(n + 3) = ϕ(n ) + 2, (1)则n = 2p α 或n + 3 = 2p α, 其中α ≥ 1, p ≡ 3 (mod 4), p 是素数. 证明:经验证可知n = 1, 2不满足(1)式, 设n > 2, 则ϕ(n ), ϕ(n +3)均为偶数. 由(1)知ϕ(n )和ϕ(n +3)不能同时被4整除, 故只能有ϕ(n ) ≡ 2 (mod 4), ϕ(n +3) ≡ 0 (mod 4)或ϕ(n ) ≡ 0 (mod 4), ϕ(n +3) ≡ 2 (mod 4).令n = 2α1p 2α2…p k αk , 则ϕ(n ) = 2α1-1p 2α2-1(p 2-1)…p k αk -1(p k -1). 由于ϕ(n )中2α1-1, (p 2-1), …, (p k -1)均被2整除, 若ϕ(n ) ≡ 2 (mod 4), 则n 只能含有一个奇素数因子, 因此n 有三种情况: (1) n = 2α1, 此时α1 = 2, 故n = 4; (2) n = p 2α2, 此时p 2满足p 2 ≡ 3 (mod 4); (3) n = 2α1p 2α2, 此时α1 = 1, p 2 ≡ 3 (mod 4), 即n = 2p 2α2. 因为ϕ(4) ≠ ϕ(1) + 2, 所以若ϕ(n +3) ≡ 2 (mod 4), 经类似的分析可得n + 3 = p α, 2p α, α ≥ 1, p ≡ 3 (mod 4). 设n = p α, 由(1)得ϕ(p α+3) = p α - p α-1 + 2 (2)设2t || p α + 3, t ≥ 1, 由(2)得 p α - p α-1 + 2 = ϕ(2t ⋅(p α + 3)/2t )= 2t -1⋅ϕ( (p α + 3)/2t ) ≤ 2t -1⋅( (p α + 3)/2t -1) = (p α + 3)/2-2t -1即有 p α - p α-1 + 2 ≤ (p α + 3)/2 - 1, 化简得p α ≤ 2p α-1 - 3, 也即3 ≤ p α-1(2-p ) 由于p > 2, 故 3 ≤ p α-1(2-p )不能成立. 同样可证n + 3 = p α时, (1)式不成立, 故n = 2p α或n + 3= 2p α. # 17. 证明ϕ(n ) ≥ n /d (n ).证明:设n 的标准分解式为s l s l p p n ...11=, 故ϕ(n )d (n ) = n (1-1/p 1)…(1-1/p s )(l 1 + 1)…(l s + 1) ≥ n (1/2)s 2s = n于是得ϕ(n ) ≥ n /d (n ). # 18. 求出满足ϕ(mn ) = ϕ(m ) + ϕ(n ) (1)的全部正整数对(m , n ). 解:设(m ,n ) = d , 则从ϕ(n )的公式不难有ϕ(mn ) = d ⋅ϕ(m )⋅ϕ(n )/ϕ(d ), 由(1)得ϕ(m ) + ϕ(n ) = d ⋅ϕ(m )⋅ϕ(n )/ϕ(d ), (2)设ϕ(m )/ϕ(d ) = a , ϕ(n )/ϕ(d ) = b , a , b 都是正整数, (2)化为1/a + 1/b = d (3)d > 2时, 易证(3)无正整数解, 在d = 1和d = 2时, (3)分别仅有正整数解a = b = 2和a = b = 1. 在d = 1, a = b = 2时, ϕ(m ) = ϕ(n ) = 2, 因此(m , n ) = (3, 4), (4, 3); 在d = 2, a = b = 1时, ϕ(m ) = ϕ(n ) = 1, 于是(m , n ) = (2, 2). # 19. 若n > 0, 满足24 | n + 1, 则24 | σ(n ). 证明:由24 | n + 1知n ≡ -1(mod 3)和n ≡ -1(mod 8), 设因子d | n , 则3|/d , 2|/d , 可设d ≡ 1, 2 (mod 3), d ≡ 1, 3, 5, 7(mod 8).因为d ⋅(n /d ) = n ≡ -1 (mod 3)和d ⋅(n /d ) = n ≡ -1(mod 8), 由此推出, d ≡ 1 (mod 3), n /d ≡ 2 (mod 3) 或d ≡ 2 (mod 3), n /d ≡ 1 (mod 3), 和d ≡ 3 (mod 8), n /d ≡ 5 (mod 8) 或d ≡ 5 (mod 8), n /d ≡ 3 (mod 8) 或d ≡ 1 (mod 8), n /d ≡ 7 (mod 8) 或d ≡ 7 (mod 8), n /d ≡ 1 (mod 8).每一种情形都有d + n /d ≡ 0 (mod 3), d + n /d ≡ 0 (mod 8), 故d + n /d ≡ 0(mod 24). 又若d = n /d , 则n = d 2, d > 1, 则因为2|/n , 所以2|/d , 但n = d 2 ≡ 1 (mod 8)矛盾. 所以n 的所有正因子可以配对, 每对为d , n /d , 故24 | σ(n ). # 20. 证明: 若n = p 1α1 p 2α2⋅⋅⋅ p k αk , k ≤ 8, 则ϕ(n ) > n /6. 证明:ϕ(n ) = ⎪⎪⎭⎫⎝⎛-⎪⎪⎭⎫ ⎝⎛-k p p n 11...111 而p i 越大, 1 - 1/p i 越大, 故只要证p 1, p 2, …, p 8为前8个素数时, ϕ(n ) > n /6成立即可, 即要证611911...511311211>⎪⎭⎫ ⎝⎛-⎪⎭⎫ ⎝⎛-⎪⎭⎫ ⎝⎛-⎪⎭⎫ ⎝⎛-, 而左边=6132332355296>, 即结论成立. # 21. 设w (1) = 0, n > 1, w (n )是n 的不同的素因子的个数, 证明:f (n ) = w (n )*μ(n ) = 0或1.证明:若n = p α (α ≥ 2)f (n ) = w (n )*u (n ) = ∑⎪⎭⎫⎝⎛nd d n w d u |)( = u (1)⋅w (p α) + u (p )⋅w (p α-1) = u (1)⋅1 + (-1)⋅1 = 0.若n = p ,f (n ) = w (n )*u (n ) = w (1)⋅u (p ) + w (p )⋅u (1) = 1若n = p 1α1 p 2α2⋅⋅⋅ p k αk , k ≥ 2, 则 f (n ) = w (n )*u (n )= ∑⎪⎭⎫⎝⎛nd d n w d u |)(= )1()1())1(()1(...)1()1()1(1110w C k k C k u C k u C k k k k k k kk -⋅+---⋅++-⋅-⋅+⋅⋅-- = 1|)')1((=-x k x= 0 # 22. 设f (x )的定义域是[0, 1]中的有理数,F (n ) = ()nknk f 1=∑, F *(n ) = ()n k nn k k f 1),(1==∑,证明: F *(n ) = μ(n )*F (n ). 证明:由Mobius 变换定理知, 等价于证明F (n ) = F *(n )*e (n ), 即要证F (n ) = ∑∑∑==⎪⎭⎫ ⎝⎛=nd dd k k nd d k f d F |1),(1|*)(. 而对于r /n , r = 1, 2, …, n 的每个分数, 既约后均为k /d , d | n , k ≤ d , (k , d ) = 1的形式, 即为某个r /n , 1 ≤ r ≤ n . 故∑∑∑===⎪⎭⎫⎝⎛=⎪⎭⎫ ⎝⎛n r nd dd k k n r f d k f 1|1),(1, 即F (n ) = ∑nd d F |*)(, 再由Mobius 逆变换即得. #23. 证明: 若f (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 )⋅(∑⎪⎭⎫⎝⎛nd d n h d g |)()= ∑⎪⎭⎫⎝⎛nd d n h d g n f |)()(= ∑⎪⎭⎫⎝⎛⎪⎭⎫ ⎝⎛nd d n h d n f d g d f |)()(= (f (n )⋅g (n ))*(f (n )⋅h (n )) #24. 证明: 若f (n )和f 1(n )各为g (n )和g 1(n )的麦比乌斯变换, 则()()d nnd dn nd f d g g d f 1|1|)()(∑=∑. 证明:f (n ) = ∑nd d g |)(, f 1(n ) = ∑nd d g |11)(,∑∑∑⎪⎭⎫⎝⎛=⎪⎭⎫ ⎝⎛nd n d dc d n g c g d n g d f |||11)()( ∑∑∑∑∑==⎪⎭⎫⎝⎛an b na n a an b n d b g a g b g a g d n f d g ||1||1|1)()()()()( 令b = n /d , 则(n /d ) | (n /a )⇒ a | d . 于是∑∑∑∑⎪⎭⎫⎝⎛=n d d a an b na d n g a gb g a g ||1||1)()()(.故∑∑⎪⎭⎫⎝⎛n d dc d n g c g ||1)(与∑∑n a an b b g a g ||1)()(展开式中每一项均相等, 因此()()d nnd dn nd f d g g d f 1|1|)()(∑=∑. # 证法二f = g *e ,f 1 =g 1*e , 则f *g 1 = g *e *g 1 = g *g 1*e = g *(g 1*e ) = g *f 1. # 25. 设f (x )是一个整系数多项式, ψ(n )代表f (0), f (1), ⋅⋅⋅ , f (n -1) (1)中与n 互素的数的个数, 证明: (1) ψ(n )是积性数论函数;(2) ψ(p α) = p α-1( p -b p ), b p 代表(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 互素的个数为ψ(m )ψ(n )个. 又f (x )为整系数多项式, 故 f (i + n ) ≡ f (i ) mod n f (i + m ) ≡ f (i ) mod m故上述mn 个数中每一行与n 互素的有ψ(n )个, 所以f (0), f (1), …., f ((m -1)⋅n + n -1)中共有m ψ(n )个与n 互素的数. 而f (i ), f (n + i ), …, f ((m -1)⋅n + i )由于i , n + i , …, (m -1)⋅n + i 恰好通过mod m 的一组完系, 所以上述m ψ(n )个与n 互素的数中有ψ(m )ψ(n )个与m 互素, 因此有ψ(mn ) = ψ(m )ψ(n ). (2) (a , p α) = 1⇔(a , p ) = 1, 而f (0), f (1), …, f (p -1) f (p ), f (p + 1), …, f (2p -1) ……f ((p α-1-1)⋅p ), f ((p α-1-1)⋅p + 1), …, f ((p α-1-1)⋅p + p -1) 每一行与p 互素个数为p -b p , 于是ψ(p α) = p α-1(p -b p ). # 26. 证明.))((())((2|3|t d t d nt nt ∑=∑证明:因为d 为积性函数, 故d 3, d 3*e , (d *e )2均为积性函数, 故只需对n = 1及n = p α证明上式即可!n = 1时, 左边 = 1 = 右边, 故命题成立. n = p α时, p 为素数, α ≥ 1时()()223330303|32141)1(...21)1())(())((++=++++=+==∑∑∑==ααααααi i ipt i p d t d ()()∑∑∑∑=++=⎪⎭⎫ ⎝⎛+=⎪⎭⎫ ⎝⎛=⎪⎪⎭⎫ ⎝⎛==ααααααp t i i i p t t d i p d t d |32220202|))((2141)1()()(. # 27. 找出所有的正整数n 分别满足(1) ϕ(n ) = n /2; (2) ϕ(n ) = ϕ(2n ); (3) ϕ(n ) = 12.证明: 设n = p 1α1 p 2α2⋅⋅⋅ p k αk , p 1 < p 2 < … < p k , 则ϕ(n ) = n (1-1/p 1)…(1-1/p k ).(1) 若ϕ(n ) = n /2, 则(1-1/p 1)…(1-1/p k ) = 1/2.若t = 1, 则p 1 = 2, n = 2α即为所求.若p 1 ≠ 2, (1-1/p 1)…(1-1/p k ) = 1/2, 则2(p 1-1)…(p k -1) = p 1p 2…p k , 而p 1, p 2, …, p k 均为不同的奇素数, 所以此时ϕ(n ) = n /2不成立.(2) 若n 为奇数, p 1, p 2, …, p k 均为不同的奇素数, 则)(11...1111...112112)2(11n p p n p p n n k k ϕϕ=⎪⎪⎭⎫ ⎝⎛-⎪⎪⎭⎫ ⎝⎛-=⎪⎪⎭⎫ ⎝⎛-⎪⎪⎭⎫ ⎝⎛-⎪⎭⎫ ⎝⎛-=. 若n 为偶数, 设p 1 = 2, 则)(211...211211...112112)2(2n p n p p n n t ϕϕ=⎪⎪⎭⎫ ⎝⎛-⎪⎭⎫ ⎝⎛-=⎪⎪⎭⎫ ⎝⎛-⎪⎪⎭⎫ ⎝⎛-⎪⎭⎫ ⎝⎛-=. 所以当n 是奇数时, ϕ(n ) = ϕ(2n ).(3) 若ϕ(n ) = p 1α1-1(p 1-1) p 2α2-1(p 2-1)⋅⋅⋅ p k αk -1(p k -1) = 12, 则p i - 1 | 12, i = 1,2, …, k . 故p i ∈ {2, 3, 5, 7, 13}且k ≤ 3, αi ≤ 3, i = 1, 2, …, k . 则若2|/n , ϕ(n ) = 12, 则n = 13, 3⨯7; 若2||n , 则n = 2⨯13, 2⨯3⨯7; 若4 || n , 则n = 4⨯7. 若2k || n (k ≥ 3), 则ϕ(n ) = ϕ(2k )⋅ϕ(n /2k ) = 2k -1⋅ϕ(n /2k ) = 12没有整数解, 所以ϕ(n ) = 12的解只有n = 13, 3⨯7, 2⨯13, 2⨯3⨯7, 4⨯7. #28. 证明: 设p n 表示第n 个素数, 则存在正常数C 1, C 2使C 1 n log n < p n < C 2 n log n .证明:n ≥ 2时, 由第7节定理1有nnn n n log 12)(log 81≤≤π将n 换成p n , 有nn n np p n p p log 12log 81≤≤. (1)上面不等式左边给出 p n ≤ 8n log p n . (2) 两边取对数有 log p n ≤ log8n + loglog p n . (3) 又x > 1时, log x < x /2, 所以loglog p n < log p n /2. 所以由(3)式, 有log p n /2<log8n . log p n <2log8n ≤8log n (因为n ≥ 2, (8n )2 ≤ n 8)再由(2)有, p n <64n log n , 取C 2 = 64即可. 而(1)的右边给出p n ≥ n log p n /12> n log n /12, 故取C 1 = 1/12即可. 即(1/12) n log n < p n < 64 n log n . #29. 证明: 设f 1 = f 2 = 1, F n +2 = F n +1 + F n (n ≥ 0), 则(F m , F n ) = F (m , n ).证明:(1) 首先证明对于n ≥ 2, m ≥ 1有f n +m = f n -1f m + f n f m +1, (*)对m 归纳证之m = 1时, 要证f n +1 = f n -1f 1 + f n f 2 = f n -1 + f n 即可. 假设小于m 时(*)成立. 则等于m 时, 由题设 f n +m = f n +m -1 + f n +m -2= (f n -1f m -1 + f n f m ) + (f n -1f m -2+f n f m -1) (归纳假设) = f n -1(f m -1 + f m -2) + f n (f m + f m -1) = f n -1 f m + f n f m +1 (m ≥ 3)m = 2时, f n +2 = f n +1 + f n = f n + f n -1 + f n = 2f n + f n -1f 2 = f n -1f 2 + f n f 3 故(*)成立.(2) 若m | n , 则f m | f n , 事实上, 设n = mn 1, 对n 1归纳, n 1 = 1时显然, 设f m | f mn 1, 则f m (n 1+1) = f mn 1+m )1(=f mn 1-1⋅f m + f mn 1⋅f m +1 故f m | f m (n 1+1) 故m | n 时, f m | f n . (3) (f n , f n + 1) = 1, n ≥ 1设(f n , f n + 1) = d , 则由题设 f n + 1 = f n +f n - 1 ⇒ d | f n - 1, 继续下去得d | f 1 = 1, 即d = 1. (4) 设m > n , (f m , f n ) =f (m , n ). 若m = n , 显然. 事实上, 设m = nq + r , 0 < r < n .(因若n | m , 由(2)显然). 由(1)及(2)有:(f m , f n ) = (f nq + r , f n )= (f nq - 1f r + f nq f r + 1, f n ) nqn f f |=(f nq - 1f r , f n )而f n | f nq , (f nq - 1, f nq ) = 1, ∴(f nq - 1, f n ) = 1, ∴(f m , f n ) = (f r , f n )令n = q 1r + r 0, 同上又有(f r , f n ) = (f r , f r 0) =…=f (m , n ). # 30. 证明: 设f (n )是一个积性函数, 则对素数的方幂p α (α ≥ 1)有f ( p α) = f ( p )α,则f (n )是完全积性函数. 证明:设m = p 1α1 p 2α2⋅⋅⋅ p k αk , n = p 1β1 p 2β2⋅⋅⋅ p k βk , αi ≥ 0, βi ≥ 0, i = 1, 2 , …, k .f (m ) = f (p 1α1 p 2α2⋅⋅⋅ p k αk ) = f (p 1α1)…f (p k αk ) = f (p 1)α1…f (p k )αk .同理, f (n ) = f (p 1)β1…f (p k )βk . 所以f (mn ) = f (p 1α1+β1p 2α2+β2⋅⋅⋅ p k αk +βk ) = f (p 1)α1+β1…f (p k )αk +βk . #31. 证明: 若F (n ), f (n )是两个数论函数, 则F (n ) = nd |∏f (d )的充分必要条件是f (n ) = nd |∏F (d )μ(n /d ).证明:“⇒”)/(||1|)/(1)()(d n u n d dd nd d n u d f d F ∏∏∏== )/(|)/(|1111)(td n u n d d n t d f ∏∏(d = d 1t )= ∑∏)1/(|11)/(|1)(d n t td n u nd d f = ∏=11|1)(d n nd d f= f (n )“⇐”)/(||1|)/(1)()(d n u n d dd nd d n u d F d f ∏∏∏== )/(|)/(|1111)(td n u n d d n t d F ∏∏ (d = d 1t )= ∑∏)1/(|11)/(|1)(d n t td n u nd d F= ∏=11|1)(d n n d d F= F (n ) #。

第三章 同余§1习题（P53）1． 证明定理2及性质庚、壬 01定理2 若11(mod )k k A B m αααα≡(mod )i i x y m ≡ ，1,2,,i k =则1111k k kk A x x αααααα≡∑ 1111(mod )k k kk B y y m αααααα∑证：由(mod )i i x y m ≡ ⇒戊(mod )ii ii x y m αα≡11kkx x αα⇒≡戊11(mod )k k y y m αα111kk k A x x αααα⇒≡ 戊111(mod )k kk B y y m αααα1111kk kkA x x αααααα⇒∑≡ 丁1111(mod )k k kk B y y m αααααα∑02庚证：（i ）(mod )a b m ≡∵ 由P48定理1m a b km ka kb ⇒−⇒−，0(mod )km ak bk mk >⇒≡ （ii ）设1a a d =，1b b d =，1m m d =0m >∵，100d m >⇒>(mod )a b m ≡∵ 111()m a b dm d a b ⇒−⇒−111111(mod )(mod a b mm a b a b m d d d⇒−⇒≡⇒≡2． 设正整数101010nn a a a a =+++ 010i a <-，试证11/a 的充要条件是011(1)ni i i a =−∑。

证：由101(mod 11)10(1)(mod 11)i i ≡−⇒≡−10(1)(mod 11)10(1)(mod 11)nni iii i i i i i i a a a a ==⇒≡−⇒≡−∑∑01110(1)nnii i i i i a a ==⇒−−∑∑于是11a 011(1)ni i i a =⇔−∑3． 找出整数能被37，101整除的判别条件来。

01 由10001(mod 37)≡ 及1010001000n n a a a a =+++ ，01000i a <-，由上面证明之方法得3737ni i a a =⇔∑02 由1001(mod 101)≡− 及10100100n n a a a a =+++ 0100i a <- 由上面证明之方法可得：101101(1)ni i i a a =⇔−∑4． 证明3264121+证：由7640251(mod 641)=×≡− 及4456252(mod 641)−=−≡3272577252122252(25)∴+≡×−×=−742173212(525)2(5)(521)≡−×−≡×−×+32173(521)(25)1≡×+≡×= 3(1)10(mod 641)≡−+≡3264121∴+5． 若a 是任一单数，则221(mod 2)nn a +≡(1)n . 证明：当n =1时，322/1a − 2(21)14(1)k k k +−=+∵ 假定2221nn a +−，则有1222222211()1(1)(1)n nn n na a a a a +⋅−=−=−=−+由2221nn a +−，221na +（∵a 是单数，∴21na +是双数）∴1321n n a a ++−，即1221(mod 2)n n a ++≡6． 应用检查因数的方法求出下列各数的标准分解式（i ）1535625 （ii ）1158066 解：（i ）由215356252561425252457=×=×由3245718+++=，324573819391=×=× 由91713=×43153562553713∴=⋅⋅⋅（ii ）由311586627+++++=，11580663386022=×33862221++++=，3860223128674=×由7128674546−+=，128674718382=×718382364−+=，1838272626=×262621313213101=×=×× 22115806637131012∴=⋅⋅⋅⋅§2习题（P57）1． 证明s t x u p v −=+，u =0，1，…，1s t p −−，v =0，1，…，1t p −，t s -，是模s p 的一个 完全剩余系。