This article is translated by AI.
Prove: When ω ( n ) > 1 ω(n)>1 ω ( n ) > 1 , ∑ d ∣ n μ ( d ) log d = 0 \sum_{d \mid n} μ(d) \log d=0 ∑ d ∣ n μ ( d ) log d = 0 ; generally if m ⩾ 1 m \geqslant 1 m ⩾ 1 and ω ( n ) > m ω(n)>m ω ( n ) > m , then ∑ d ∣ n μ ( d ) log m d = 0 \sum_{d \mid n} μ(d) \log ^m d=0 ∑ d ∣ n μ ( d ) log m d = 0 .
Proof: Since if d d d has a square factor, then μ ( d ) = 0 μ(d)=0 μ ( d ) = 0 , we can assume without loss of generality
n = p 1 p 2 ⋯ p k n=p_1p_2\cdots p_k n = p 1 p 2 ⋯ p k
where p i , p j ( i ≠ j ) p_i,p_j(i\neq j) p i , p j ( i = j ) are distinct prime factors.
When ω ( n ) > 1 ω(n)>1 ω ( n ) > 1 , ∑ d ∣ n μ ( d ) log d = 0 \sum\limits_{d|n}μ(d)\log d=0 d ∣ n ∑ μ ( d ) log d = 0 .
k = ω ( n ) > 1 ⟹ k > 1 k=ω(n)>1\implies k>1 k = ω ( n ) > 1 ⟹ k > 1
∑ d ∣ n μ ( d ) log d = ∑ S ⊆ { p 1 , p 2 , ⋯ , p k } μ ( ∏ p ∈ S p ) log ( ∏ p ∈ S p ) = ∑ S ⊆ { p 1 , p 2 , ⋯ , p k } ( − 1 ) ∣ S ∣ ∑ p ∈ S log p \begin{align} \sum\limits_{d|n}μ(d)\log d&=\sum\limits_{S\subseteq\{p_1,p_2,\cdots,p_k\}}μ(\prod\limits_{p\in S}p)\log(\prod\limits_{p\in S}p)\\ &=\sum\limits_{S\subseteq\{p_1,p_2,\cdots,p_k\}}(-1)^{|S|}\sum\limits_{p\in S}\log p \end{align} d ∣ n ∑ μ ( d ) log d = S ⊆ { p 1 , p 2 , ⋯ , p k } ∑ μ ( p ∈ S ∏ p ) log ( p ∈ S ∏ p ) = S ⊆ { p 1 , p 2 , ⋯ , p k } ∑ ( − 1 ) ∣ S ∣ p ∈ S ∑ log p
Exchanging the order of summation, we have:
∑ d ∣ n μ ( d ) log d = ∑ p ∣ n log p ∑ d ∣ n p ∣ d μ ( d ) \sum\limits_{d|n}μ(d)\log d=\sum\limits_{p|n}\log p\sum\limits_{\substack{d \mid n \\ p|d}}μ(d) d ∣ n ∑ μ ( d ) log d = p ∣ n ∑ log p d ∣ n p ∣ d ∑ μ ( d )
Fix p p p , then
∑ d ∣ n p ∣ d μ ( d ) = ( − 1 ) [ ( − 1 ) 0 ( k − 1 0 ) + ( − 1 ) 1 ( k − 1 1 ) + ⋯ + ( − 1 ) k − 1 ( k − 1 k − 1 ) ] = ( − 1 ) ( − 1 + 1 ) k − 1 = 0 \begin{align} \sum\limits_{\substack{d \mid n\\ p \mid d}}μ(d)&=(-1)\left[(-1)^0\binom{k-1}{0}+(-1)^1\binom{k-1}{1}+\cdots+(-1)^{k-1}\binom{k-1}{k-1}\right]\\ &=(-1)(-1+1)^{k-1}\\ &=0 \end{align} d ∣ n p ∣ d ∑ μ ( d ) = ( − 1 ) [ ( − 1 ) 0 ( 0 k − 1 ) + ( − 1 ) 1 ( 1 k − 1 ) + ⋯ + ( − 1 ) k − 1 ( k − 1 k − 1 ) ] = ( − 1 ) ( − 1 + 1 ) k − 1 = 0
Therefore,
∑ d ∣ n μ ( d ) log d = 0 \sum\limits_{d|n}μ(d)\log d=0 d ∣ n ∑ μ ( d ) log d = 0
If m ≥ 1 m \geq 1 m ≥ 1 , and ω ( n ) > m ω(n)>m ω ( n ) > m , then ∑ d ∣ n μ ( d ) log m d = 0 \sum\limits_{d|n}μ(d)\log^m d=0 d ∣ n ∑ μ ( d ) log m d = 0 .
k = ω ( n ) > m ≥ 1 ⟹ k > 1 k=ω(n)>m\geq 1\implies k>1 k = ω ( n ) > m ≥ 1 ⟹ k > 1
∑ d ∣ n μ ( d ) log m d = ∑ d ∣ n μ ( d ) ∑ p 1 ∣ d , ⋯ , p m ∣ d p i ∣ n log p 1 ⋯ log p m \sum\limits_{d|n}μ(d)\log^m d=\sum\limits_{d|n}μ(d)\sum\limits_{\substack{p_1|d,\cdots,p_m|d \\ p_{i} \mid n}}\log p_1\cdots\log p_m d ∣ n ∑ μ ( d ) log m d = d ∣ n ∑ μ ( d ) p 1 ∣ d , ⋯ , p m ∣ d p i ∣ n ∑ log p 1 ⋯ log p m
Exchanging the order of summation, we have:
∑ d ∣ n μ ( d ) log m d = ∑ p 1 ∣ n ⋯ ∑ p m ∣ n log p 1 ⋯ log p m ∑ d ∣ n p 1 ∣ d , ⋯ , p m ∣ d μ ( d ) \sum\limits_{d|n}μ(d)\log^m d=\sum\limits_{p_1|n}\cdots\sum\limits_{p_m|n}\log p_1\cdots\log p_m\sum\limits_{\substack{d \mid n\\ p_1|d,\cdots,p_m|d} }μ(d) d ∣ n ∑ μ ( d ) log m d = p 1 ∣ n ∑ ⋯ p m ∣ n ∑ log p 1 ⋯ log p m d ∣ n p 1 ∣ d , ⋯ , p m ∣ d ∑ μ ( d )
Fix p 1 , p 2 , ⋯ , p m p_1,p_2,\cdots,p_m p 1 , p 2 , ⋯ , p m , let S = { s : s = p i , i = 1 , 2 , ⋯ , m } S=\{s:s=p_i,i=1,2,\cdots,m\} S = { s : s = p i , i = 1 , 2 , ⋯ , m } be the set of distinct prime factors among them; let r = ∣ S ∣ r=|S| r = ∣ S ∣ , then r ≤ m < k r\leq m<k r ≤ m < k .
Then:
∑ d ∣ n p 1 ∣ d , ⋯ , p m ∣ d μ ( d ) = ( − 1 ) r [ ( − 1 ) 0 ( k − r 0 ) + ( − 1 ) 1 ( k − r 1 ) + ⋯ + ( − 1 ) k − r ( k − r k − r ) ] = ( − 1 ) r ( − 1 + 1 ) k − r = 0 \begin{align} &\sum\limits_{\substack{d \mid n \\p_1|d,\cdots,p_m|d}}μ(d)\\ &=(-1)^r\left[(-1)^0\binom{k-r}{0}+(-1)^1\binom{k-r}{1}+\cdots+(-1)^{k-r}\binom{k-r}{k-r}\right]\\ &=(-1)^r(-1+1)^{k-r}\\ &=0 \end{align} d ∣ n p 1 ∣ d , ⋯ , p m ∣ d ∑ μ ( d ) = ( − 1 ) r [ ( − 1 ) 0 ( 0 k − r ) + ( − 1 ) 1 ( 1 k − r ) + ⋯ + ( − 1 ) k − r ( k − r k − r ) ] = ( − 1 ) r ( − 1 + 1 ) k − r = 0
Therefore,
∑ d ∣ n μ ( d ) log m d = 0 \sum\limits_{d|n}μ(d)\log^m d=0 d ∣ n ∑ μ ( d ) log m d = 0
Find the value of ∑ n = 1 ∞ μ ( n ! ) \sum_{n=1}^{\infty} μ(n!) ∑ n = 1 ∞ μ ( n !) .
Solution: For n ≥ 4 n\geq 4 n ≥ 4 , we have 2 2 = 4 ∣ n 2^2=4|n 2 2 = 4∣ n , so μ ( n ) = 0 μ(n)=0 μ ( n ) = 0 .
Then:
∑ n = 1 ∞ μ ( n ! ) = μ ( 1 ) + μ ( 2 ) + μ ( 6 ) = 1 + ( − 1 ) + ( − 1 ) 2 = 1 \sum\limits_{n=1}^\infty μ(n!)=μ(1)+μ(2)+μ(6)=1+(-1)+(-1)^2=1 n = 1 ∑ ∞ μ ( n !) = μ ( 1 ) + μ ( 2 ) + μ ( 6 ) = 1 + ( − 1 ) + ( − 1 ) 2 = 1
Prove: ∑ d ∣ n μ 2 ( d ) = 2 ω ( n ) \sum_{d \mid n} μ^2(d)=2^{ω(n)} ∑ d ∣ n μ 2 ( d ) = 2 ω ( n ) and ∑ t ∣ n μ ( t ) d ( t ) = ( − 1 ) ω ( n ) \sum_{t \mid n} μ(t) d(t)=(-1)^{ω(n)} ∑ t ∣ n μ ( t ) d ( t ) = ( − 1 ) ω ( n ) .
Proof:
Let f = μ 2 ∗ u f=μ^2 * u f = μ 2 ∗ u , then f f f is a multiplicative function, and f ( n ) = ∑ d ∣ n μ 2 ( d ) f(n)=\sum\limits_{d|n}μ^2(d) f ( n ) = d ∣ n ∑ μ 2 ( d ) .
Let n = p α n=p^α n = p α , then we have:
f ( p α ) = { 1 , α = 0 2 , α ≥ 1 f(p^α)=\begin{cases} 1, & α=0\\ 2, & α\geq 1 \end{cases} f ( p α ) = { 1 , 2 , α = 0 α ≥ 1
If m = p 1 α 1 p 2 α 2 ⋯ p s α s m=p_1^{α_1}p_2^{α_2}\cdots p_s^{α_s} m = p 1 α 1 p 2 α 2 ⋯ p s α s , then
f ( m ) = f ( p 1 α 1 ) f ( p 2 α 2 ) ⋯ f ( p s α s ) = 2 ω ( m ) f(m)=f(p_1^{α_1})f(p_2^{α_2})\cdots f(p_s^{α_s})=2^{ω(m)} f ( m ) = f ( p 1 α 1 ) f ( p 2 α 2 ) ⋯ f ( p s α s ) = 2 ω ( m )
That is
∑ d ∣ n μ 2 ( d ) = 2 ω ( n ) \sum\limits_{d|n}μ^2(d)=2^{ω(n)} d ∣ n ∑ μ 2 ( d ) = 2 ω ( n )
Let g = μ d ∗ u g=μ d * u g = μ d ∗ u , then g g g is a multiplicative function, and g ( n ) = ∑ t ∣ n μ ( t ) d ( t ) g(n)=\sum\limits_{t|n}μ(t)d(t) g ( n ) = t ∣ n ∑ μ ( t ) d ( t ) .
Let n = p α n=p^α n = p α , then we have:
g ( p α ) = { 1 , α = 0 − 1 , α ≥ 1 g(p^α)=\begin{cases} 1, & α=0\\ -1, & α\geq 1 \end{cases} g ( p α ) = { 1 , − 1 , α = 0 α ≥ 1
If m = p 1 α 1 p 2 α 2 ⋯ p s α s m=p_1^{α_1}p_2^{α_2}\cdots p_s^{α_s} m = p 1 α 1 p 2 α 2 ⋯ p s α s , then
g ( m ) = g ( p 1 α 1 ) g ( p 2 α 2 ) ⋯ g ( p s α s ) = ( − 1 ) ω ( m ) g(m)=g(p_1^{α_1})g(p_2^{α_2})\cdots g(p_s^{α_s})=(-1)^{ω(m)} g ( m ) = g ( p 1 α 1 ) g ( p 2 α 2 ) ⋯ g ( p s α s ) = ( − 1 ) ω ( m )
That is
∑ t ∣ n μ ( t ) d ( t ) = ( − 1 ) ω ( n ) \sum\limits_{t|n}μ(t)d(t)=(-1)^{ω(n)} t ∣ n ∑ μ ( t ) d ( t ) = ( − 1 ) ω ( n )
Prove: ∑ d ∣ n μ ( d ) σ ( d ) = ( − 1 ) ω ( n ) ∏ p ∣ n p \sum_{d \mid n} μ(d) σ(d)=(-1)^{ω(n)} \prod_{p \mid n} p ∑ d ∣ n μ ( d ) σ ( d ) = ( − 1 ) ω ( n ) ∏ p ∣ n p and ∑ d ∣ n μ ( d ) φ ( d ) = ( − 1 ) ω ( n ) ∏ p ∣ n ( p − 2 ) \sum_{d \mid n} μ(d) φ(d)=(-1)^{ω(n)} \prod_{p \mid n}(p-2) ∑ d ∣ n μ ( d ) φ ( d ) = ( − 1 ) ω ( n ) ∏ p ∣ n ( p − 2 ) .
Proof:
∑ d ∣ n μ ( d ) σ ( d ) = ( − 1 ) ω ( n ) ∏ p ∣ n p \sum\limits_{d|n}μ(d)σ(d)=(-1)^{ω(n)}\prod\limits_{p|n}p d ∣ n ∑ μ ( d ) σ ( d ) = ( − 1 ) ω ( n ) p ∣ n ∏ p .
Let f = μ ∗ σ f=μ*σ f = μ ∗ σ , then f f f is a multiplicative function, and f ( n ) = ∑ d ∣ n μ ( d ) σ ( d ) f(n)=\sum\limits_{d|n}μ(d)σ(d) f ( n ) = d ∣ n ∑ μ ( d ) σ ( d ) .
Let n = p α n=p^α n = p α , then we have:
f ( p α ) = { 1 , α = 0 − p , α ≥ 1 f(p^α)=\begin{cases} 1, & α=0\\ -p, & α\geq 1 \end{cases} f ( p α ) = { 1 , − p , α = 0 α ≥ 1
If m = p 1 α 1 p 2 α 2 ⋯ p s α s m=p_1^{α_1}p_2^{α_2}\cdots p_s^{α_s} m = p 1 α 1 p 2 α 2 ⋯ p s α s , then
f ( m ) = f ( p 1 α 1 ) f ( p 2 α 2 ) ⋯ f ( p s α s ) = ( − 1 ) ω ( m ) ∏ p ∣ m p f(m)=f(p_1^{α_1})f(p_2^{α_2})\cdots f(p_s^{α_s})=(-1)^{ω(m)}\prod\limits_{p|m}p f ( m ) = f ( p 1 α 1 ) f ( p 2 α 2 ) ⋯ f ( p s α s ) = ( − 1 ) ω ( m ) p ∣ m ∏ p
That is
∑ d ∣ n μ ( d ) σ ( d ) = ( − 1 ) ω ( n ) ∏ p ∣ n p \sum\limits_{d|n}μ(d)σ(d)=(-1)^{ω(n)}\prod\limits_{p|n}p d ∣ n ∑ μ ( d ) σ ( d ) = ( − 1 ) ω ( n ) p ∣ n ∏ p
∑ d ∣ n μ ( d ) φ ( d ) = ( − 1 ) ω ( n ) ∏ p ∣ n ( p − 2 ) \sum\limits_{d|n}μ(d)φ(d)=(-1)^{ω(n)}\prod\limits_{p|n}(p-2) d ∣ n ∑ μ ( d ) φ ( d ) = ( − 1 ) ω ( n ) p ∣ n ∏ ( p − 2 ) .
Let g = μ ∗ φ g=μ*φ g = μ ∗ φ , then g g g is a multiplicative function, and g ( n ) = ∑ d ∣ n μ ( d ) φ ( d ) g(n)=\sum\limits_{d|n}μ(d)φ(d) g ( n ) = d ∣ n ∑ μ ( d ) φ ( d ) .
Let n = p α n=p^α n = p α , then we have:
g ( p α ) = { 1 , α = 0 2 − p , α ≥ 1 g(p^α)=\begin{cases} 1, & α=0\\ 2-p, & α\geq 1 \end{cases} g ( p α ) = { 1 , 2 − p , α = 0 α ≥ 1
If m = p 1 α 1 p 2 α 2 ⋯ p s α s m=p_1^{α_1}p_2^{α_2}\cdots p_s^{α_s} m = p 1 α 1 p 2 α 2 ⋯ p s α s , then
g ( m ) = g ( p 1 α 1 ) g ( p 2 α 2 ) ⋯ g ( p s α s ) = ( − 1 ) ω ( m ) ∏ p ∣ m ( p − 2 ) g(m)=g(p_1^{α_1})g(p_2^{α_2})\cdots g(p_s^{α_s})=(-1)^{ω(m)}\prod\limits_{p|m}(p-2) g ( m ) = g ( p 1 α 1 ) g ( p 2 α 2 ) ⋯ g ( p s α s ) = ( − 1 ) ω ( m ) p ∣ m ∏ ( p − 2 )
That is
∑ d ∣ n μ ( d ) φ ( d ) = ( − 1 ) ω ( n ) ∏ p ∣ n ( p − 2 ) \sum\limits_{d|n}μ(d)φ(d)=(-1)^{ω(n)}\prod\limits_{p|n}(p-2) d ∣ n ∑ μ ( d ) φ ( d ) = ( − 1 ) ω ( n ) p ∣ n ∏ ( p − 2 )
(1) Let n > 1 n>1 n > 1 , prove: ∑ 1 ⩽ d ⩽ n ( n , d ) = 1 d = 1 2 n φ ( n ) \sum_{\substack{1 \leqslant d \leqslant n \\(n, d)=1}} d=\frac{1}{2} n φ(n) ∑ 1 ⩽ d ⩽ n ( n , d ) = 1 d = 2 1 n φ ( n ) ;
(2) Let n n n be an odd number, prove: ∑ 1 ⩽ d ⩽ n 2 ( d , n ) = 1 d = 1 8 n φ ( n ) − 1 8 ∏ p ∣ n ( 1 − p ) \sum_{\substack{1 \leqslant d \leqslant \frac{n}{2} \\(d, n)=1}} d=\frac{1}{8} n φ(n)-\frac{1}{8} \prod_{p \mid n}(1-p) ∑ 1 ⩽ d ⩽ 2 n ( d , n ) = 1 d = 8 1 n φ ( n ) − 8 1 ∏ p ∣ n ( 1 − p ) .
Proof:
If n > 1 n>1 n > 1 , then
∑ 1 ≤ d ≤ n ( n , d ) = 1 d = 1 2 ∑ 1 ≤ d ≤ n ( n , d ) = 1 d + 1 2 ∑ 1 ≤ d ≤ n ( n , d ) = 1 ( n − d ) \sum\limits_{\substack{1\leq d\leq n\\(n,d)=1}}d=\frac{1}{2}\sum\limits_{\substack{1\leq d\leq n\\(n,d)=1}}d+\frac{1}{2}\sum\limits_{\substack{1\leq d\leq n\\(n,d)=1}}(n-d) 1 ≤ d ≤ n ( n , d ) = 1 ∑ d = 2 1 1 ≤ d ≤ n ( n , d ) = 1 ∑ d + 2 1 1 ≤ d ≤ n ( n , d ) = 1 ∑ ( n − d )
= 1 2 ∑ 1 ≤ d ≤ n ( n , d ) = 1 n =\frac{1}{2}\sum\limits_{\substack{1\leq d\leq n\\(n,d)=1}}n = 2 1 1 ≤ d ≤ n ( n , d ) = 1 ∑ n
= 1 2 n φ ( n ) =\frac{1}{2}nφ(n) = 2 1 n φ ( n )
Let S = ∑ 1 ≤ d ≤ n 2 ( d , n ) = 1 d S=\sum\limits_{\substack{1\leq d\leq \frac{n}{2}\\(d,n)=1}}d S = 1 ≤ d ≤ 2 n ( d , n ) = 1 ∑ d , then we have
S = ∑ d = 1 ⌊ n 2 ⌋ d ⋅ I ( ( d , n ) ) S=\sum\limits_{d=1}^{\lfloor \frac{n}{2} \rfloor}d\cdot I((d,n)) S = d = 1 ∑ ⌊ 2 n ⌋ d ⋅ I (( d , n ))
Where I = μ ∗ u I=μ*u I = μ ∗ u , so
I ( ( d , n ) ) = ∑ k ∣ ( d , n ) μ ( k ) I((d,n))=\sum\limits_{k|(d,n)}μ(k) I (( d , n )) = k ∣ ( d , n ) ∑ μ ( k )
Thus,
S = ∑ d = 1 ⌊ n 2 ⌋ d ∑ k ∣ ( d , n ) μ ( k ) S=\sum\limits_{d=1}^{\lfloor \frac{n}{2} \rfloor}d\sum\limits_{k|(d,n)}μ(k) S = d = 1 ∑ ⌊ 2 n ⌋ d k ∣ ( d , n ) ∑ μ ( k )
Exchanging the order of summation, we have
S = ∑ k ∣ n μ ( k ) ∑ 1 ≤ d ≤ ⌊ n 2 ⌋ k ∣ d d S=\sum\limits_{k|n}μ(k)\sum\limits_{\substack{1\leq d\leq \lfloor \frac{n}{2} \rfloor\\k|d}}d S = k ∣ n ∑ μ ( k ) 1 ≤ d ≤ ⌊ 2 n ⌋ k ∣ d ∑ d
Fix k k k , let d = k m d=km d = km , then
∑ 1 ≤ d ≤ ⌊ n 2 ⌋ k ∣ d d = k ∑ m = 1 ⌊ n 2 k ⌋ m = k ⋅ M ( M + 1 ) 2 \sum\limits_{\substack{1\leq d\leq \lfloor \frac{n}{2} \rfloor\\k|d}}d=k\sum\limits_{m=1}^{\lfloor\frac{n}{2k}\rfloor}m=k\cdot\frac{M(M+1)}{2} 1 ≤ d ≤ ⌊ 2 n ⌋ k ∣ d ∑ d = k m = 1 ∑ ⌊ 2 k n ⌋ m = k ⋅ 2 M ( M + 1 )
Where M = ⌊ n 2 k ⌋ M=\lfloor\frac{n}{2k}\rfloor M = ⌊ 2 k n ⌋ .
And
⌊ n 2 k ⌋ = ⌊ n k 2 ⌋ = n k − 1 2 \lfloor\frac{n}{2k}\rfloor=\lfloor\frac{\frac{n}{k}}{2}\rfloor=\frac{\frac{n}{k}-1}{2} ⌊ 2 k n ⌋ = ⌊ 2 k n ⌋ = 2 k n − 1
Therefore,
∑ 1 ≤ d ≤ ⌊ n 2 ⌋ k ∣ d d = k ⋅ n k − 1 2 ( n k − 1 2 + 1 ) 2 \sum\limits_{\substack{1\leq d\leq \lfloor \frac{n}{2} \rfloor\\k|d}}d=k\cdot\frac{\frac{\frac{n}{k}-1}{2}(\frac{\frac{n}{k}-1}{2}+1)}{2} 1 ≤ d ≤ ⌊ 2 n ⌋ k ∣ d ∑ d = k ⋅ 2 2 k n − 1 ( 2 k n − 1 + 1 )
= n 2 − k 2 8 k =\frac{n^2-k^2}{8k} = 8 k n 2 − k 2
Then
S = ∑ k ∣ n μ ( k ) ⋅ n 2 − k 2 8 k S=\sum\limits_{k|n}μ(k)\cdot\frac{n^2-k^2}{8k} S = k ∣ n ∑ μ ( k ) ⋅ 8 k n 2 − k 2
= 1 8 ( n 2 ∑ k ∣ n μ ( k ) k − ∑ k ∣ n μ ( k ) k ) =\frac{1}{8}\left(n^2\sum\limits_{k|n}\frac{μ(k)}{k}-\sum\limits_{k|n}μ(k)k\right) = 8 1 n 2 k ∣ n ∑ k μ ( k ) − k ∣ n ∑ μ ( k ) k
Where,
∑ k ∣ n μ ( k ) k = φ ( n ) n \sum\limits_{k|n}\frac{μ(k)}{k}=\frac{φ(n)}{n} k ∣ n ∑ k μ ( k ) = n φ ( n )
∑ k ∣ n μ ( k ) k = ∏ p ∣ n ( 1 − p ) \sum\limits_{k|n}μ(k)k=\prod\limits_{p|n}(1-p) k ∣ n ∑ μ ( k ) k = p ∣ n ∏ ( 1 − p )
Thus,
S = 1 8 ( n 2 ⋅ φ ( n ) n − ∏ p ∣ n ( 1 − p ) ) S=\frac{1}{8}\left(n^2\cdot\frac{φ(n)}{n}-\prod\limits_{p|n}(1-p)\right) S = 8 1 n 2 ⋅ n φ ( n ) − p ∣ n ∏ ( 1 − p )
= 1 8 n φ ( n ) − 1 8 ∏ p ∣ n ( 1 − p ) =\frac{1}{8}nφ(n)-\frac{1}{8}\prod\limits_{p|n}(1-p) = 8 1 n φ ( n ) − 8 1 p ∣ n ∏ ( 1 − p )
Find all natural numbers n n n such that φ ( n ) = 24 φ(n)=24 φ ( n ) = 24 .
Solution: For n ∈ N + n\in\mathbb{N}^+ n ∈ N + , make the following prime factorization
n = p 1 α 1 p 2 α 2 ⋯ p k α k n=p_1^{α_1}p_2^{α_2}\cdots p_k^{α_k} n = p 1 α 1 p 2 α 2 ⋯ p k α k
Then
φ ( n ) = n ∏ p ∣ n ( 1 − 1 p ) φ(n)=n\prod\limits_{p|n}(1-\frac{1}{p}) φ ( n ) = n p ∣ n ∏ ( 1 − p 1 )
= p 1 α 1 − 1 ( p 1 − 1 ) p 2 α 2 − 1 ( p 2 − 1 ) ⋯ p k α k − 1 ( p k − 1 ) =p_1^{α_1-1}(p_1-1)p_2^{α_2-1}(p_2-1)\cdots p_k^{α_k-1}(p_k-1) = p 1 α 1 − 1 ( p 1 − 1 ) p 2 α 2 − 1 ( p 2 − 1 ) ⋯ p k α k − 1 ( p k − 1 )
Note that: 24 = 2 3 × 3 24=2^3\times 3 24 = 2 3 × 3
n = p k n=p^k n = p k
That is
p k − 1 ( p − 1 ) = 2 3 × 3 p^{k-1}(p-1)=2^3\times 3 p k − 1 ( p − 1 ) = 2 3 × 3
No solution.
n = p a q b n=p^aq^b n = p a q b
That is
p a − 1 ( p − 1 ) q b − 1 ( q − 1 ) = 2 3 × 3 p^{a-1}(p-1)q^{b-1}(q-1)=2^3\times 3 p a − 1 ( p − 1 ) q b − 1 ( q − 1 ) = 2 3 × 3
a = 1 a=1 a = 1 , b = 1 b=1 b = 1 , then ( p − 1 ) ( q − 1 ) = 24 (p-1)(q-1)=24 ( p − 1 ) ( q − 1 ) = 24 And 24 = 1 × 24 = 2 × 12 = 3 × 8 = 4 × 6 24=1\times 24=2\times 12=3\times 8=4\times 6 24 = 1 × 24 = 2 × 12 = 3 × 8 = 4 × 6 Also p , q p,q p , q are prime numbers, so ( p , q ) = ( 3 , 13 ) , ( 5 , 7 ) (p,q)=(3,13),(5,7) ( p , q ) = ( 3 , 13 ) , ( 5 , 7 ) Thus n = p q = 39 , 35 n=pq=39,35 n = pq = 39 , 35
a = 2 a=2 a = 2 , b = 1 b=1 b = 1 , then p ( p − 1 ) ( q − 1 ) = 24 p(p-1)(q-1)=24 p ( p − 1 ) ( q − 1 ) = 24 So ( p , q ) = ( 2 , 13 ) , ( 3 , 5 ) (p,q)=(2,13),(3,5) ( p , q ) = ( 2 , 13 ) , ( 3 , 5 ) Thus n = p 2 q = 52 , 45 n=p^2q=52,45 n = p 2 q = 52 , 45
a = 3 a=3 a = 3 , b = 1 b=1 b = 1 , then p 2 ( p − 1 ) ( q − 1 ) = 24 p^2(p-1)(q-1)=24 p 2 ( p − 1 ) ( q − 1 ) = 24 So ( p , q ) = ( 2 , 7 ) (p,q)=(2,7) ( p , q ) = ( 2 , 7 ) Thus n = p 3 q = 56 n=p^3q=56 n = p 3 q = 56
a = 3 a=3 a = 3 , b = 2 b=2 b = 2 , then p 2 ( p − 1 ) q ( q − 1 ) = 24 p^2(p-1)q(q-1)=24 p 2 ( p − 1 ) q ( q − 1 ) = 24 So ( p , q ) = ( 2 , 3 ) (p,q)=(2,3) ( p , q ) = ( 2 , 3 ) Thus n = p 3 q 2 = 72 n=p^3q^2=72 n = p 3 q 2 = 72
Other cases, no solution.
n = p a q b r c n=p^aq^br^c n = p a q b r c
That is
p a − 1 ( p − 1 ) q b − 1 ( q − 1 ) r c − 1 ( r − 1 ) = 24 p^{a-1}(p-1)q^{b-1}(q-1)r^{c-1}(r-1)=24 p a − 1 ( p − 1 ) q b − 1 ( q − 1 ) r c − 1 ( r − 1 ) = 24
a = b = c = 1 a=b=c=1 a = b = c = 1 , then ( p − 1 ) ( q − 1 ) ( r − 1 ) = 24 (p-1)(q-1)(r-1)=24 ( p − 1 ) ( q − 1 ) ( r − 1 ) = 24 And 24 = 1 × 2 × 12 = 1 × 3 × 8 = 1 × 4 × 6 = 2 × 3 × 4 24=1\times 2\times 12=1\times 3\times 8=1\times 4\times 6=2\times 3\times 4 24 = 1 × 2 × 12 = 1 × 3 × 8 = 1 × 4 × 6 = 2 × 3 × 4 So ( p , q , r ) = ( 2 , 3 , 13 ) , ( 2 , 5 , 7 ) (p,q,r)=(2,3,13),(2,5,7) ( p , q , r ) = ( 2 , 3 , 13 ) , ( 2 , 5 , 7 ) Thus n = p q r = 78 , 70 n=pqr=78,70 n = pq r = 78 , 70
a = 2 a=2 a = 2 , b = c = 1 b=c=1 b = c = 1 , then p ( p − 1 ) ( q − 1 ) ( r − 1 ) = 24 p(p-1)(q-1)(r-1)=24 p ( p − 1 ) ( q − 1 ) ( r − 1 ) = 24 So ( p , q , r ) = ( 2 , 3 , 7 ) , ( 3 , 2 , 5 ) (p,q,r)=(2,3,7),(3,2,5) ( p , q , r ) = ( 2 , 3 , 7 ) , ( 3 , 2 , 5 ) Thus n = p 2 q r = 84 , 90 n=p^2qr=84,90 n = p 2 q r = 84 , 90
a = b = 2 a=b=2 a = b = 2 , c = 1 c=1 c = 1 or other cases, no solution.
n = p a q b r c s t n=p^aq^br^cs^t n = p a q b r c s t
Because if n = 2 × 3 × 5 × 7 = 210 n=2\times 3\times 5\times 7=210 n = 2 × 3 × 5 × 7 = 210 , then φ ( n ) = 48 > 24 φ(n)=48>24 φ ( n ) = 48 > 24 , so no solution.
In summary, all possible values of n n n are
39 , 35 , 52 , 45 , 56 , 72 , 78 , 70 , 84 , 90 39,35,52,45,56,72,78,70,84,90 39 , 35 , 52 , 45 , 56 , 72 , 78 , 70 , 84 , 90
A total of 10 kinds.
Find all natural numbers n n n such that 4 ∤ φ ( n ) 4 \nmid φ(n) 4 ∤ φ ( n ) .
Solution: For n ∈ N + n\in\mathbb{N}^+ n ∈ N + , make the following prime factorization
n = p 1 k 1 p 2 k 2 ⋯ p m k m n=p_1^{k_1}p_2^{k_2}\cdots p_m^{k_m} n = p 1 k 1 p 2 k 2 ⋯ p m k m
Then
φ ( n ) = p 1 k 1 − 1 ( p 1 − 1 ) p 2 k 2 − 1 ( p 2 − 1 ) ⋯ p m k m − 1 ( p m − 1 ) φ(n)=p_1^{k_1-1}(p_1-1)p_2^{k_2-1}(p_2-1)\cdots p_m^{k_m-1}(p_m-1) φ ( n ) = p 1 k 1 − 1 ( p 1 − 1 ) p 2 k 2 − 1 ( p 2 − 1 ) ⋯ p m k m − 1 ( p m − 1 )
Let n = 2 a ⋅ m n=2^a\cdot m n = 2 a ⋅ m , where 2 a ∣ n 2^a \mid n 2 a ∣ n and 2 a + 1 ∤ m 2^{a+1} \nmid m 2 a + 1 ∤ m .
Since φ ( n ) φ(n) φ ( n ) is a multiplicative function, then
φ ( n ) = φ ( 2 a ) ⋅ φ ( m ) φ(n)=φ(2^a)\cdot φ(m) φ ( n ) = φ ( 2 a ) ⋅ φ ( m )
a = 0 a=0 a = 0 , then n n n is an odd number.
For m m m , make prime factorization m = p 1 b 1 p 2 b 2 ⋯ p t b t m=p_1^{b_1}p_2^{b_2}\cdots p_t^{b_t} m = p 1 b 1 p 2 b 2 ⋯ p t b t , where p i p_i p i is an odd prime number.
If p i ≡ 1 ( m o d 4 ) p_i\equiv 1\pmod{4} p i ≡ 1 ( mod 4 ) , then p i − 1 ≡ 0 ( m o d 4 ) p_i-1\equiv 0\pmod{4} p i − 1 ≡ 0 ( mod 4 ) , then 4 ∣ φ ( m ) 4|φ(m) 4∣ φ ( m ) If p i ≡ 3 ( m o d 4 ) p_i\equiv 3\pmod{4} p i ≡ 3 ( mod 4 ) , then φ ( p i b i ) = p i b i − 1 ( p i − 1 ) ≡ 2 ( m o d 4 ) φ(p_i^{b_i})=p_i^{b_i-1}(p_i-1)\equiv 2\pmod{4} φ ( p i b i ) = p i b i − 1 ( p i − 1 ) ≡ 2 ( mod 4 ) If t ≤ 2 t \leq 2 t ≤ 2 , then there exist i , j i,j i , j such that 4 ∣ ( p i − 1 ) ( p j − 1 ) 4|(p_i-1)(p_j-1) 4∣ ( p i − 1 ) ( p j − 1 ) , so 4 ∣ φ ( n ) 4|φ(n) 4∣ φ ( n ) . If t = 0 t=0 t = 0 , then n = 1 n=1 n = 1 , φ ( 1 ) = 1 φ(1)=1 φ ( 1 ) = 1 , we have 4 ∤ φ ( 1 ) 4\nmid φ(1) 4 ∤ φ ( 1 ) . If t = 1 t=1 t = 1 , then n = p b n=p^b n = p b , where p ≡ 3 ( m o d 4 ) p\equiv 3\pmod{4} p ≡ 3 ( mod 4 ) , so φ ( p b ) ≡ 2 ( m o d 4 ) φ(p^b)\equiv 2\pmod{4} φ ( p b ) ≡ 2 ( mod 4 ) .
a = 1 a=1 a = 1 , then φ ( n ) = φ ( 2 ⋅ m ) = φ ( 2 ) φ ( m ) = φ ( m ) φ(n)=φ(2\cdot m)=φ(2)φ(m)=φ(m) φ ( n ) = φ ( 2 ⋅ m ) = φ ( 2 ) φ ( m ) = φ ( m )
Similar to the previous case, so 4 ∤ φ ( n ) ⟺ n = 2 4\nmid φ(n)\Longleftrightarrow n=2 4 ∤ φ ( n ) ⟺ n = 2 or n = 2 ⋅ p k n=2\cdot p^k n = 2 ⋅ p k , where p ≡ 3 ( m o d 4 ) p\equiv 3\pmod{4} p ≡ 3 ( mod 4 ) , k ≥ 1 k\geq 1 k ≥ 1 .
a = 2 a=2 a = 2 , then φ ( n ) = φ ( 4 ⋅ m ) = φ ( 4 ) φ ( m ) = 2 φ ( m ) φ(n)=φ(4\cdot m)=φ(4)φ(m)=2φ(m) φ ( n ) = φ ( 4 ⋅ m ) = φ ( 4 ) φ ( m ) = 2 φ ( m )
By comparison, 4 ∤ φ ( m ) ⟺ m = 1 ⟺ n = 4 4\nmid φ(m)\Longleftrightarrow m=1\Longleftrightarrow n=4 4 ∤ φ ( m ) ⟺ m = 1 ⟺ n = 4 .
a ≥ 3 a\geq 3 a ≥ 3 , then 4 ∣ φ ( n ) 4|φ(n) 4∣ φ ( n ) , no solution.
In summary, all possible values of n n n are
1 , 2 , 4 , p k , 2 ⋅ p k 1,2,4,p^k,2\cdot p^k 1 , 2 , 4 , p k , 2 ⋅ p k
Where p p p is a prime number and p ≡ 3 ( m o d 4 ) p\equiv 3\pmod{4} p ≡ 3 ( mod 4 ) , k ≥ 1 k\geq 1 k ≥ 1 .
Let Λ ( n ) Λ(n) Λ ( n ) be the Mangoldt function, and ψ ( x ) = ∑ n ≤ x Λ ( n ) ψ(x) = \sum_{n\leq x} Λ(n) ψ ( x ) = ∑ n ≤ x Λ ( n ) , then
∑ n ≤ x ψ ( x n ) = ∑ n ≤ x Λ ( n ) [ x n ] = ∑ n ≤ x log n \sum_{n\leq x}ψ\left(\frac{x}{n}\right) = \sum_{n\leq x}Λ(n)\left[\frac{x}{n}\right] = \sum_{n\leq x}\log n n ≤ x ∑ ψ ( n x ) = n ≤ x ∑ Λ ( n ) [ n x ] = n ≤ x ∑ log n
Proof:
∑ n ≤ x ψ ( x n ) = ∑ n ≤ x ∑ m ≤ x n Λ ( m ) = ∑ m ≤ x Λ ( m ) ∑ n ≤ x m 1 = ∑ m ≤ x Λ ( m ) [ x m ] \begin{align} \sum\limits_{n\leq x}ψ\left(\frac{x}{n}\right) &= \sum\limits_{n\leq x}\sum\limits_{m\leq \frac{x}{n}}Λ(m)\\ &= \sum\limits_{m\leq x}Λ(m)\sum\limits_{n\leq \frac{x}{m}}1\\ &= \sum\limits_{m\leq x}Λ(m)\left[\frac{x}{m}\right] \end{align} n ≤ x ∑ ψ ( n x ) = n ≤ x ∑ m ≤ n x ∑ Λ ( m ) = m ≤ x ∑ Λ ( m ) n ≤ m x ∑ 1 = m ≤ x ∑ Λ ( m ) [ m x ]
∑ n ≤ x log n = ∑ n ≤ x ∑ d ∣ n Λ ( d ) = ∑ d ≤ x Λ ( d ) ∑ k ≤ x d 1 = ∑ d ≤ x Λ ( d ) [ x d ] \begin{align} \sum\limits_{n\leq x}\log n &= \sum\limits_{n\leq x}\sum\limits_{d|n}Λ(d)\\ &= \sum\limits_{d\leq x}Λ(d)\sum\limits_{k\leq \frac{x}{d}}1\\ &= \sum\limits_{d\leq x}Λ(d)\left[\frac{x}{d}\right] \end{align} n ≤ x ∑ log n = n ≤ x ∑ d ∣ n ∑ Λ ( d ) = d ≤ x ∑ Λ ( d ) k ≤ d x ∑ 1 = d ≤ x ∑ Λ ( d ) [ d x ]
Let σ ( n ) σ(n) σ ( n ) be the divisor sum function, prove: (1) The necessary and sufficient condition for σ ( n ) = n + 1 σ(n)=n+1 σ ( n ) = n + 1 is that n n n is a prime number; (2) If n n n is a perfect number, i.e., σ ( n ) = 2 n σ(n)=2n σ ( n ) = 2 n , then
∑ d ∣ n 1 d = 2 \sum_{d \mid n} \frac{1}{d}=2 d ∣ n ∑ d 1 = 2
Proof:
Necessity is obvious.
Sufficiency: If n = 1 n=1 n = 1 , then σ ( 1 ) = 1 σ(1)=1 σ ( 1 ) = 1 , and 1 + n = 2 1+n=2 1 + n = 2 , so it is not satisfied. If n n n is a composite number, then there exists d d d (d ≠ 1 d\neq 1 d = 1 and d ≠ n d\neq n d = n ) s.t. d ∣ n d|n d ∣ n .
And
σ ( n ) ≥ 1 + d + n > 1 + n σ(n)\geq 1+d+n>1+n σ ( n ) ≥ 1 + d + n > 1 + n
So σ ( n ) ≠ 1 + n σ(n)\neq 1+n σ ( n ) = 1 + n , contradiction. Therefore, n n n is a prime number.
∑ d ∣ n 1 d = 1 n ∑ d ∣ n n d = 1 n ∑ d ∣ n d = σ ( n ) n = 2 n n = 2 \sum\limits_{d|n}\frac{1}{d}=\frac{1}{n}\sum\limits_{d|n}\frac{n}{d}=\frac{1}{n}\sum\limits_{d|n}d=\frac{σ(n)}{n}=\frac{2n}{n}=2 d ∣ n ∑ d 1 = n 1 d ∣ n ∑ d n = n 1 d ∣ n ∑ d = n σ ( n ) = n 2 n = 2
https://zhuanlan.zhihu.com/p/543010816
https://zhuanlan.zhihu.com/p/544792225
https://zhuanlan.zhihu.com/p/545595129
https://zhuanlan.zhihu.com/p/546385318
https://zhuanlan.zhihu.com/p/547333984
https://zhuanlan.zhihu.com/p/548061254