Showing $sum_dmid n mu(d)tau(n/d)=1$ and $sum_dmid n mu(d)tau(d)=(-1)^r$ [closed] Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)Prove $sum_kmid nmu(k)d(k)=(-1)^omega(n)$Sum of Positive Divisors: $sum_n mu(n/d)nu(d)=1$ and $sum_n mu(n/d)sigma(d)=n$An application of Mobius Inversion $sum_d mid n mu(fracnd)nu(d) = 1$Number theory Exercise: $sum_d mid n mu(d) d(d) = (-1)^omega(n)$ and $sum_d mid n mu(d) sigma (d)$Prove that $sum_d = 2^omega(n)$Evaluating a sum with Mobius function $sum_ntau(d)mu(d)$Prove $sum_kmid nmu(k)d(k)=(-1)^omega(n)$Norm of Prime IdealDemostrate that: $ tau(n)varphi(n) ≥ n$$tau(n) = 1992$ and $phi(n) mid n$An application of Mobius Inversion $sum_d mid n mu(fracnd)nu(d) = 1$Writing as a Product of $k$ factorsDecomposing Dirichlet charcatersShow the following equality involving $tau$, the number of divisors of the input.Prove that the two sums involving $tau$ are equal.A bound on number of divisors of $n$
What would be Julian Assange's expected punishment, on the current English criminal law?
How do you clear the ApexPages.getMessages() collection in a test?
Is above average number of years spent on PhD considered a red flag in future academia or industry positions?
How does modal jazz use chord progressions?
Slither Like a Snake
Direct Experience of Meditation
Are my PIs rude or am I just being too sensitive?
90's book, teen horror
Area of a 2D convex hull
How to rotate it perfectly?
Stars Make Stars
How to set letter above or below the symbol?
3 doors, three guards, one stone
What do you call the holes in a flute?
Is it possible to ask for a hotel room without minibar/extra services?
How to colour the US map with Yellow, Green, Red and Blue to minimize the number of states with the colour of Green
What's the point in a preamp?
Cold is to Refrigerator as warm is to?
What is the electric potential inside a point charge?
Why does tar appear to skip file contents when output file is /dev/null?
Is there a service that would inform me whenever a new direct route is scheduled from a given airport?
Determine whether or not the following series converge.
What computer would be fastest for Mathematica Home Edition?
Do working physicists consider Newtonian mechanics to be "falsified"?
Showing $sum_dmid n mu(d)tau(n/d)=1$ and $sum_dmid n mu(d)tau(d)=(-1)^r$ [closed]
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)Prove $sum_kmid nmu(k)d(k)=(-1)^omega(n)$Sum of Positive Divisors: $sum_n mu(n/d)nu(d)=1$ and $sum_n mu(n/d)sigma(d)=n$An application of Mobius Inversion $sum_d mid n mu(fracnd)nu(d) = 1$Number theory Exercise: $sum_d mid n mu(d) d(d) = (-1)^omega(n)$ and $sum_d mid n mu(d) sigma (d)$Prove that $sum_d = 2^omega(n)$Evaluating a sum with Mobius function $sum_ntau(d)mu(d)$Prove $sum_kmid nmu(k)d(k)=(-1)^omega(n)$Norm of Prime IdealDemostrate that: $ tau(n)varphi(n) ≥ n$$tau(n) = 1992$ and $phi(n) mid n$An application of Mobius Inversion $sum_d mid n mu(fracnd)nu(d) = 1$Writing as a Product of $k$ factorsDecomposing Dirichlet charcatersShow the following equality involving $tau$, the number of divisors of the input.Prove that the two sums involving $tau$ are equal.A bound on number of divisors of $n$
$begingroup$
Need some help on this question from Victor Shoup
Let $tau(n)$ be the number of positive divisors of $n$. Show that:
$sum_dmid n mu(d)tau(n/d)=1$;
$sum_dmid n mu(d)tau(d)=(-1)^r$, where $n=p_1^e_1cdots p_r^e_r$ is the prime factorization of $n$.
I have tried both of them but cant find any solution!We have to use Mobius Function properties to prove this Question.
number-theory mobius-function multiplicative-function divisor-counting-function mobius-inversion
$endgroup$
closed as off-topic by Saad, Eevee Trainer, Theo Bendit, mrtaurho, Parcly Taxel Mar 28 at 0:47
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Saad, Eevee Trainer, Theo Bendit, mrtaurho, Parcly Taxel
add a comment |
$begingroup$
Need some help on this question from Victor Shoup
Let $tau(n)$ be the number of positive divisors of $n$. Show that:
$sum_dmid n mu(d)tau(n/d)=1$;
$sum_dmid n mu(d)tau(d)=(-1)^r$, where $n=p_1^e_1cdots p_r^e_r$ is the prime factorization of $n$.
I have tried both of them but cant find any solution!We have to use Mobius Function properties to prove this Question.
number-theory mobius-function multiplicative-function divisor-counting-function mobius-inversion
$endgroup$
closed as off-topic by Saad, Eevee Trainer, Theo Bendit, mrtaurho, Parcly Taxel Mar 28 at 0:47
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Saad, Eevee Trainer, Theo Bendit, mrtaurho, Parcly Taxel
3
$begingroup$
Trying to search for the first one, I found these questions: An application of Mobius Inversion $sum_d mid n mu(fracnd)nu(d) = 1$ and Sum of Positive Divisors: $sum_n mu(n/d)nu(d)=1$ and $sum_n mu(n/d)sigma(d)=n$. Perhaps with a bit of searching you can find more copies of that question.
$endgroup$
– Martin Sleziak
Jan 15 '17 at 11:17
3
$begingroup$
Similarly, with a bit of searching, you will probably be able to find several posts about the other one. Like here or here. In fact, you do not need to search at all, just look at the list of related questions in the sidebar on the right to find this one.
$endgroup$
– Martin Sleziak
Jan 15 '17 at 11:22
$begingroup$
The sad thing is, the fact that it's two questions in one makes it difficult to mark it as a duplicate.
$endgroup$
– rabota
Jan 15 '17 at 20:12
$begingroup$
Forgive me this time . Will try to search from the next time , newbie mistake . Also thnx alot for citing the answers . :)
$endgroup$
– da6932
Jan 16 '17 at 19:19
add a comment |
$begingroup$
Need some help on this question from Victor Shoup
Let $tau(n)$ be the number of positive divisors of $n$. Show that:
$sum_dmid n mu(d)tau(n/d)=1$;
$sum_dmid n mu(d)tau(d)=(-1)^r$, where $n=p_1^e_1cdots p_r^e_r$ is the prime factorization of $n$.
I have tried both of them but cant find any solution!We have to use Mobius Function properties to prove this Question.
number-theory mobius-function multiplicative-function divisor-counting-function mobius-inversion
$endgroup$
Need some help on this question from Victor Shoup
Let $tau(n)$ be the number of positive divisors of $n$. Show that:
$sum_dmid n mu(d)tau(n/d)=1$;
$sum_dmid n mu(d)tau(d)=(-1)^r$, where $n=p_1^e_1cdots p_r^e_r$ is the prime factorization of $n$.
I have tried both of them but cant find any solution!We have to use Mobius Function properties to prove this Question.
number-theory mobius-function multiplicative-function divisor-counting-function mobius-inversion
number-theory mobius-function multiplicative-function divisor-counting-function mobius-inversion
edited Mar 27 at 2:41
Saad
20.6k92452
20.6k92452
asked Jan 15 '17 at 10:05
da6932da6932
143
143
closed as off-topic by Saad, Eevee Trainer, Theo Bendit, mrtaurho, Parcly Taxel Mar 28 at 0:47
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Saad, Eevee Trainer, Theo Bendit, mrtaurho, Parcly Taxel
closed as off-topic by Saad, Eevee Trainer, Theo Bendit, mrtaurho, Parcly Taxel Mar 28 at 0:47
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Saad, Eevee Trainer, Theo Bendit, mrtaurho, Parcly Taxel
3
$begingroup$
Trying to search for the first one, I found these questions: An application of Mobius Inversion $sum_d mid n mu(fracnd)nu(d) = 1$ and Sum of Positive Divisors: $sum_n mu(n/d)nu(d)=1$ and $sum_n mu(n/d)sigma(d)=n$. Perhaps with a bit of searching you can find more copies of that question.
$endgroup$
– Martin Sleziak
Jan 15 '17 at 11:17
3
$begingroup$
Similarly, with a bit of searching, you will probably be able to find several posts about the other one. Like here or here. In fact, you do not need to search at all, just look at the list of related questions in the sidebar on the right to find this one.
$endgroup$
– Martin Sleziak
Jan 15 '17 at 11:22
$begingroup$
The sad thing is, the fact that it's two questions in one makes it difficult to mark it as a duplicate.
$endgroup$
– rabota
Jan 15 '17 at 20:12
$begingroup$
Forgive me this time . Will try to search from the next time , newbie mistake . Also thnx alot for citing the answers . :)
$endgroup$
– da6932
Jan 16 '17 at 19:19
add a comment |
3
$begingroup$
Trying to search for the first one, I found these questions: An application of Mobius Inversion $sum_d mid n mu(fracnd)nu(d) = 1$ and Sum of Positive Divisors: $sum_n mu(n/d)nu(d)=1$ and $sum_n mu(n/d)sigma(d)=n$. Perhaps with a bit of searching you can find more copies of that question.
$endgroup$
– Martin Sleziak
Jan 15 '17 at 11:17
3
$begingroup$
Similarly, with a bit of searching, you will probably be able to find several posts about the other one. Like here or here. In fact, you do not need to search at all, just look at the list of related questions in the sidebar on the right to find this one.
$endgroup$
– Martin Sleziak
Jan 15 '17 at 11:22
$begingroup$
The sad thing is, the fact that it's two questions in one makes it difficult to mark it as a duplicate.
$endgroup$
– rabota
Jan 15 '17 at 20:12
$begingroup$
Forgive me this time . Will try to search from the next time , newbie mistake . Also thnx alot for citing the answers . :)
$endgroup$
– da6932
Jan 16 '17 at 19:19
3
3
$begingroup$
Trying to search for the first one, I found these questions: An application of Mobius Inversion $sum_d mid n mu(fracnd)nu(d) = 1$ and Sum of Positive Divisors: $sum_n mu(n/d)nu(d)=1$ and $sum_n mu(n/d)sigma(d)=n$. Perhaps with a bit of searching you can find more copies of that question.
$endgroup$
– Martin Sleziak
Jan 15 '17 at 11:17
$begingroup$
Trying to search for the first one, I found these questions: An application of Mobius Inversion $sum_d mid n mu(fracnd)nu(d) = 1$ and Sum of Positive Divisors: $sum_n mu(n/d)nu(d)=1$ and $sum_n mu(n/d)sigma(d)=n$. Perhaps with a bit of searching you can find more copies of that question.
$endgroup$
– Martin Sleziak
Jan 15 '17 at 11:17
3
3
$begingroup$
Similarly, with a bit of searching, you will probably be able to find several posts about the other one. Like here or here. In fact, you do not need to search at all, just look at the list of related questions in the sidebar on the right to find this one.
$endgroup$
– Martin Sleziak
Jan 15 '17 at 11:22
$begingroup$
Similarly, with a bit of searching, you will probably be able to find several posts about the other one. Like here or here. In fact, you do not need to search at all, just look at the list of related questions in the sidebar on the right to find this one.
$endgroup$
– Martin Sleziak
Jan 15 '17 at 11:22
$begingroup$
The sad thing is, the fact that it's two questions in one makes it difficult to mark it as a duplicate.
$endgroup$
– rabota
Jan 15 '17 at 20:12
$begingroup$
The sad thing is, the fact that it's two questions in one makes it difficult to mark it as a duplicate.
$endgroup$
– rabota
Jan 15 '17 at 20:12
$begingroup$
Forgive me this time . Will try to search from the next time , newbie mistake . Also thnx alot for citing the answers . :)
$endgroup$
– da6932
Jan 16 '17 at 19:19
$begingroup$
Forgive me this time . Will try to search from the next time , newbie mistake . Also thnx alot for citing the answers . :)
$endgroup$
– da6932
Jan 16 '17 at 19:19
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Using the fact that both $mu$ and $tau$ are multiplicative for the first one we get from first principles the value
$$tau(n) prod_q=1^r left(1+(-1)timesfrace_qe_q+1right)$$
which simplifies to
$$tau(n) prod_q=1^r frac1e_q+1 = 1.$$
For the second one we may write
$$prod_q=1^r (1+(-1)times 2) = (-1)^r.$$
Here we have used that for a subset $S$ of the set of prime factors $P$ corresponding to a squarefree divisor $d$ of $n$ we get $mu(d) = (-1)^$ and $tau(n/d) = tau(n) prod_p_qin S frace_qe_q+1.$
$endgroup$
add a comment |
$begingroup$
1) $τ(n)= sum_n 1$ => According to the Moebius Inversion Formula $sum_n μ(d)τ(n/d) = 1$
2) If d has a squared prime factor, then μ(d)=0 => $sum_n μ(d)τ(d) = sum_rad(n) μ(d)τ(d)$.
If the number of prime factors of n is even, then μ(rad(n)/d)= μ(d).
If it is odd, then μ(rad(n)/d)= -μ(d) => $sum_n μ(d)τ(d) = sum_rad(n) μ(d)τ(d) = (-1)^r sum_rad(n) μ(rad(n)/d)τ(d)= (-1)^r sum_rad(n) μ(d)τ(rad(n)/d)=(-1)^r.$
$endgroup$
$begingroup$
Really nice observation for tau(n) , and indeed nice proof for first . Thnx .
$endgroup$
– da6932
Jan 16 '17 at 19:23
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Using the fact that both $mu$ and $tau$ are multiplicative for the first one we get from first principles the value
$$tau(n) prod_q=1^r left(1+(-1)timesfrace_qe_q+1right)$$
which simplifies to
$$tau(n) prod_q=1^r frac1e_q+1 = 1.$$
For the second one we may write
$$prod_q=1^r (1+(-1)times 2) = (-1)^r.$$
Here we have used that for a subset $S$ of the set of prime factors $P$ corresponding to a squarefree divisor $d$ of $n$ we get $mu(d) = (-1)^$ and $tau(n/d) = tau(n) prod_p_qin S frace_qe_q+1.$
$endgroup$
add a comment |
$begingroup$
Using the fact that both $mu$ and $tau$ are multiplicative for the first one we get from first principles the value
$$tau(n) prod_q=1^r left(1+(-1)timesfrace_qe_q+1right)$$
which simplifies to
$$tau(n) prod_q=1^r frac1e_q+1 = 1.$$
For the second one we may write
$$prod_q=1^r (1+(-1)times 2) = (-1)^r.$$
Here we have used that for a subset $S$ of the set of prime factors $P$ corresponding to a squarefree divisor $d$ of $n$ we get $mu(d) = (-1)^$ and $tau(n/d) = tau(n) prod_p_qin S frace_qe_q+1.$
$endgroup$
add a comment |
$begingroup$
Using the fact that both $mu$ and $tau$ are multiplicative for the first one we get from first principles the value
$$tau(n) prod_q=1^r left(1+(-1)timesfrace_qe_q+1right)$$
which simplifies to
$$tau(n) prod_q=1^r frac1e_q+1 = 1.$$
For the second one we may write
$$prod_q=1^r (1+(-1)times 2) = (-1)^r.$$
Here we have used that for a subset $S$ of the set of prime factors $P$ corresponding to a squarefree divisor $d$ of $n$ we get $mu(d) = (-1)^$ and $tau(n/d) = tau(n) prod_p_qin S frace_qe_q+1.$
$endgroup$
Using the fact that both $mu$ and $tau$ are multiplicative for the first one we get from first principles the value
$$tau(n) prod_q=1^r left(1+(-1)timesfrace_qe_q+1right)$$
which simplifies to
$$tau(n) prod_q=1^r frac1e_q+1 = 1.$$
For the second one we may write
$$prod_q=1^r (1+(-1)times 2) = (-1)^r.$$
Here we have used that for a subset $S$ of the set of prime factors $P$ corresponding to a squarefree divisor $d$ of $n$ we get $mu(d) = (-1)^$ and $tau(n/d) = tau(n) prod_p_qin S frace_qe_q+1.$
edited Jan 16 '17 at 21:08
answered Jan 15 '17 at 23:29
Marko RiedelMarko Riedel
41.5k341112
41.5k341112
add a comment |
add a comment |
$begingroup$
1) $τ(n)= sum_n 1$ => According to the Moebius Inversion Formula $sum_n μ(d)τ(n/d) = 1$
2) If d has a squared prime factor, then μ(d)=0 => $sum_n μ(d)τ(d) = sum_rad(n) μ(d)τ(d)$.
If the number of prime factors of n is even, then μ(rad(n)/d)= μ(d).
If it is odd, then μ(rad(n)/d)= -μ(d) => $sum_n μ(d)τ(d) = sum_rad(n) μ(d)τ(d) = (-1)^r sum_rad(n) μ(rad(n)/d)τ(d)= (-1)^r sum_rad(n) μ(d)τ(rad(n)/d)=(-1)^r.$
$endgroup$
$begingroup$
Really nice observation for tau(n) , and indeed nice proof for first . Thnx .
$endgroup$
– da6932
Jan 16 '17 at 19:23
add a comment |
$begingroup$
1) $τ(n)= sum_n 1$ => According to the Moebius Inversion Formula $sum_n μ(d)τ(n/d) = 1$
2) If d has a squared prime factor, then μ(d)=0 => $sum_n μ(d)τ(d) = sum_rad(n) μ(d)τ(d)$.
If the number of prime factors of n is even, then μ(rad(n)/d)= μ(d).
If it is odd, then μ(rad(n)/d)= -μ(d) => $sum_n μ(d)τ(d) = sum_rad(n) μ(d)τ(d) = (-1)^r sum_rad(n) μ(rad(n)/d)τ(d)= (-1)^r sum_rad(n) μ(d)τ(rad(n)/d)=(-1)^r.$
$endgroup$
$begingroup$
Really nice observation for tau(n) , and indeed nice proof for first . Thnx .
$endgroup$
– da6932
Jan 16 '17 at 19:23
add a comment |
$begingroup$
1) $τ(n)= sum_n 1$ => According to the Moebius Inversion Formula $sum_n μ(d)τ(n/d) = 1$
2) If d has a squared prime factor, then μ(d)=0 => $sum_n μ(d)τ(d) = sum_rad(n) μ(d)τ(d)$.
If the number of prime factors of n is even, then μ(rad(n)/d)= μ(d).
If it is odd, then μ(rad(n)/d)= -μ(d) => $sum_n μ(d)τ(d) = sum_rad(n) μ(d)τ(d) = (-1)^r sum_rad(n) μ(rad(n)/d)τ(d)= (-1)^r sum_rad(n) μ(d)τ(rad(n)/d)=(-1)^r.$
$endgroup$
1) $τ(n)= sum_n 1$ => According to the Moebius Inversion Formula $sum_n μ(d)τ(n/d) = 1$
2) If d has a squared prime factor, then μ(d)=0 => $sum_n μ(d)τ(d) = sum_rad(n) μ(d)τ(d)$.
If the number of prime factors of n is even, then μ(rad(n)/d)= μ(d).
If it is odd, then μ(rad(n)/d)= -μ(d) => $sum_n μ(d)τ(d) = sum_rad(n) μ(d)τ(d) = (-1)^r sum_rad(n) μ(rad(n)/d)τ(d)= (-1)^r sum_rad(n) μ(d)τ(rad(n)/d)=(-1)^r.$
edited Jan 15 '17 at 20:05
answered Jan 15 '17 at 17:24
Yanior WegYanior Weg
2,85611547
2,85611547
$begingroup$
Really nice observation for tau(n) , and indeed nice proof for first . Thnx .
$endgroup$
– da6932
Jan 16 '17 at 19:23
add a comment |
$begingroup$
Really nice observation for tau(n) , and indeed nice proof for first . Thnx .
$endgroup$
– da6932
Jan 16 '17 at 19:23
$begingroup$
Really nice observation for tau(n) , and indeed nice proof for first . Thnx .
$endgroup$
– da6932
Jan 16 '17 at 19:23
$begingroup$
Really nice observation for tau(n) , and indeed nice proof for first . Thnx .
$endgroup$
– da6932
Jan 16 '17 at 19:23
add a comment |
3
$begingroup$
Trying to search for the first one, I found these questions: An application of Mobius Inversion $sum_d mid n mu(fracnd)nu(d) = 1$ and Sum of Positive Divisors: $sum_n mu(n/d)nu(d)=1$ and $sum_n mu(n/d)sigma(d)=n$. Perhaps with a bit of searching you can find more copies of that question.
$endgroup$
– Martin Sleziak
Jan 15 '17 at 11:17
3
$begingroup$
Similarly, with a bit of searching, you will probably be able to find several posts about the other one. Like here or here. In fact, you do not need to search at all, just look at the list of related questions in the sidebar on the right to find this one.
$endgroup$
– Martin Sleziak
Jan 15 '17 at 11:22
$begingroup$
The sad thing is, the fact that it's two questions in one makes it difficult to mark it as a duplicate.
$endgroup$
– rabota
Jan 15 '17 at 20:12
$begingroup$
Forgive me this time . Will try to search from the next time , newbie mistake . Also thnx alot for citing the answers . :)
$endgroup$
– da6932
Jan 16 '17 at 19:19