Dtjytyk

An adverb for when you're not exaggerating

Why weren't discrete x86 CPUs ever used in game hardware?

How do I find out the mythology and history of my Fortress?

How much damage would a cupful of neutron star matter do to the Earth?

Would it be easier to apply for a UK visa if there is a host family to sponsor for you in going there?

How to compare two different files line by line in unix?

Lagrange four-squares theorem --- deterministic complexity

AppleTVs create a chatty alternate WiFi network

How would a mousetrap for use in space work?

Central Vacuuming: Is it worth it, and how does it compare to normal vacuuming?

The Nth Gryphon Number

Misunderstanding of Sylow theory

What is the chair depicted in Cesare Maccari's 1889 painting "Cicerone denuncia Catilina"?

Has negative voting ever been officially implemented in elections, or seriously proposed, or even studied?

If the probability of a dog barking one or more times in a given hour is 84%, then what is the probability of a dog barking in 30 minutes?

How does light 'choose' between wave and particle behaviour?

I can't produce songs

Trademark violation for app?

Random body shuffle every night—can we still function?

Amount of permutations on an NxNxN Rubik's Cube

Do I really need to have a message in a novel to appeal to readers?

How can I set the aperture on my DSLR when it's attached to a telescope instead of a lens?

Why does it sometimes sound good to play a grace note as a lead in to a note in a melody?

Is there hard evidence that the grant peer review system performs significantly better than random?

$sum_{d|n, d>0} (sigma(d)/d)mu(n/d))=1/n$

2

$begingroup$

We want to show
begin{align}
sum_{d|n, d>0}(sigma(d)/d)cdot mu(n/d) =1/n ,
end{align}
where $sigma(m)$ denotes the sum of all positive divisors of $m$ and where $mu$ is the Möbius function.

The hint is that we can use the formula $sigma(n)/n=sum_{d|n, d>0} 1/d$.

I tried to pull out (1/d) from the sum and then convoluted the function to get
begin{align}
sum_{d|n, d>0}(sigma(d)/d)cdot mu(n/d)
=sigma(n)/nsum_{d|n, d>0} (sigma(n/d))cdotmu(d)
end{align}
and then tried to get
$$sum_{d|n, d>0} (sigma(n/d))cdotmu(d)=1/sigma(n)$$

But I can't figure out how to get there. Can anybody give me a hint?

number-theory arithmetic-functions mobius-function

share|cite|improve this question

edited Mar 25 at 20:28

darij grinberg

11.5k33168

asked Mar 25 at 18:22

user657740

$endgroup$

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  Do you know the Möbius inversion formula? It's all you need.
  $endgroup$
  – FredH
  Mar 25 at 18:33
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I know the formula but I don't get what to do with that
  $endgroup$
  – user657740
  Mar 25 at 19:46
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  If $g(n) = sum_{dmid n} f(d)$, then $f(n) = sum_{dmid n} g(d)mu(n/d)$. Let $f(n) = 1/n$.
  $endgroup$
  – FredH
  Mar 25 at 20:02
  

  
  
  
  

add a comment | 

2

$begingroup$

We want to show
begin{align}
sum_{d|n, d>0}(sigma(d)/d)cdot mu(n/d) =1/n ,
end{align}
where $sigma(m)$ denotes the sum of all positive divisors of $m$ and where $mu$ is the Möbius function.

The hint is that we can use the formula $sigma(n)/n=sum_{d|n, d>0} 1/d$.

I tried to pull out (1/d) from the sum and then convoluted the function to get
begin{align}
sum_{d|n, d>0}(sigma(d)/d)cdot mu(n/d)
=sigma(n)/nsum_{d|n, d>0} (sigma(n/d))cdotmu(d)
end{align}
and then tried to get
$$sum_{d|n, d>0} (sigma(n/d))cdotmu(d)=1/sigma(n)$$

But I can't figure out how to get there. Can anybody give me a hint?

number-theory arithmetic-functions mobius-function

share|cite|improve this question

edited Mar 25 at 20:28

darij grinberg

11.5k33168

asked Mar 25 at 18:22

user657740

$endgroup$

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  Do you know the Möbius inversion formula? It's all you need.
  $endgroup$
  – FredH
  Mar 25 at 18:33
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I know the formula but I don't get what to do with that
  $endgroup$
  – user657740
  Mar 25 at 19:46
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  If $g(n) = sum_{dmid n} f(d)$, then $f(n) = sum_{dmid n} g(d)mu(n/d)$. Let $f(n) = 1/n$.
  $endgroup$
  – FredH
  Mar 25 at 20:02
  

  
  
  
  

add a comment | 

$begingroup$

We want to show
begin{align}
sum_{d|n, d>0}(sigma(d)/d)cdot mu(n/d) =1/n ,
end{align}
where $sigma(m)$ denotes the sum of all positive divisors of $m$ and where $mu$ is the Möbius function.

The hint is that we can use the formula $sigma(n)/n=sum_{d|n, d>0} 1/d$.

I tried to pull out (1/d) from the sum and then convoluted the function to get
begin{align}
sum_{d|n, d>0}(sigma(d)/d)cdot mu(n/d)
=sigma(n)/nsum_{d|n, d>0} (sigma(n/d))cdotmu(d)
end{align}
and then tried to get
$$sum_{d|n, d>0} (sigma(n/d))cdotmu(d)=1/sigma(n)$$

But I can't figure out how to get there. Can anybody give me a hint?

number-theory arithmetic-functions mobius-function

share|cite|improve this question

edited Mar 25 at 20:28

darij grinberg

11.5k33168

asked Mar 25 at 18:22

user657740

$endgroup$

share|cite|improve this question

edited Mar 25 at 20:28

darij grinberg

11.5k33168

asked Mar 25 at 18:22

user657740

share|cite|improve this question

edited Mar 25 at 20:28

darij grinberg

11.5k33168

asked Mar 25 at 18:22

user657740

edited Mar 25 at 20:28

darij grinberg

11.5k33168

edited Mar 25 at 20:28

darij grinberg

11.5k33168

1 Answer
1

active

oldest

votes

1

$begingroup$

Hello and welcome to MSE.

Write $ frac{σ(n)}{n} = (U*f)(n)$ , where $f(n)=frac{1}{n}$, and $U(n)=1$ for all n.

You are then asked to find $((U*f) * (μ))$.
Dirichlet convolution is associative and commutative, therefore, $(U*f) * (μ)= f*(U*μ)$, and $U* mu$ is the identity of the Dirichlet convolution, therefore overall we get $f(n)$, as required.

(here * means dirichlet convolution (https://en.wikipedia.org/wiki/Dirichlet_convolution))

share|cite|improve this answer

edited Mar 25 at 20:31

darij grinberg

11.5k33168

answered Mar 25 at 19:10

AlexandrosAlexandros

1,0951413

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Why can you say $sigma(n)/n=(1/n)*(1)?$ I'm not seeing the connection
  $endgroup$
  – user657740
  Mar 25 at 19:44
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  That's because of the hint given to you, ie $frac{sigma(n)}{n}= sum_{d|n}frac{1}{d}$ which is equal to $ U * f$ using the convolution notation.
  $endgroup$
  – Alexandros
  Mar 25 at 20:07
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @mupin By definition $sigma(n) = sum_{d | n} d = sum_{d | n} n/d$ so $sigma(n)/n = sum_{d | n} 1/d= 1 ast (1/n)$. Then $(sigma(n)/n) ast mu =sum_{l | n} mu(n/l)sum_{d | l} 1/d = sum_{d | n} 1/d sum_{l | n, d | l} mu(n/l)$ with $k = n/l$ it is $= sum_{d | n} frac1d sum_{k | n, k | n/d} mu(k)= sum_{d | n} frac1d 1_{n/d= 1} = 1/n$
  $endgroup$
  – reuns
  Mar 25 at 21:58
  
  
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3162151%2fsum-dn-d0-sigmad-d-mun-d-1-n%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

1

$begingroup$

Hello and welcome to MSE.

Write $ frac{σ(n)}{n} = (U*f)(n)$ , where $f(n)=frac{1}{n}$, and $U(n)=1$ for all n.

You are then asked to find $((U*f) * (μ))$.
Dirichlet convolution is associative and commutative, therefore, $(U*f) * (μ)= f*(U*μ)$, and $U* mu$ is the identity of the Dirichlet convolution, therefore overall we get $f(n)$, as required.

(here * means dirichlet convolution (https://en.wikipedia.org/wiki/Dirichlet_convolution))

share|cite|improve this answer

edited Mar 25 at 20:31

darij grinberg

11.5k33168

answered Mar 25 at 19:10

AlexandrosAlexandros

1,0951413

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Why can you say $sigma(n)/n=(1/n)*(1)?$ I'm not seeing the connection
  $endgroup$
  – user657740
  Mar 25 at 19:44
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  That's because of the hint given to you, ie $frac{sigma(n)}{n}= sum_{d|n}frac{1}{d}$ which is equal to $ U * f$ using the convolution notation.
  $endgroup$
  – Alexandros
  Mar 25 at 20:07
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @mupin By definition $sigma(n) = sum_{d | n} d = sum_{d | n} n/d$ so $sigma(n)/n = sum_{d | n} 1/d= 1 ast (1/n)$. Then $(sigma(n)/n) ast mu =sum_{l | n} mu(n/l)sum_{d | l} 1/d = sum_{d | n} 1/d sum_{l | n, d | l} mu(n/l)$ with $k = n/l$ it is $= sum_{d | n} frac1d sum_{k | n, k | n/d} mu(k)= sum_{d | n} frac1d 1_{n/d= 1} = 1/n$
  $endgroup$
  – reuns
  Mar 25 at 21:58
  
  
  

  
  
  
  

add a comment | 

1

$begingroup$

Hello and welcome to MSE.

Write $ frac{σ(n)}{n} = (U*f)(n)$ , where $f(n)=frac{1}{n}$, and $U(n)=1$ for all n.

You are then asked to find $((U*f) * (μ))$.
Dirichlet convolution is associative and commutative, therefore, $(U*f) * (μ)= f*(U*μ)$, and $U* mu$ is the identity of the Dirichlet convolution, therefore overall we get $f(n)$, as required.

(here * means dirichlet convolution (https://en.wikipedia.org/wiki/Dirichlet_convolution))

share|cite|improve this answer

edited Mar 25 at 20:31

darij grinberg

11.5k33168

answered Mar 25 at 19:10

AlexandrosAlexandros

1,0951413

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Why can you say $sigma(n)/n=(1/n)*(1)?$ I'm not seeing the connection
  $endgroup$
  – user657740
  Mar 25 at 19:44
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  That's because of the hint given to you, ie $frac{sigma(n)}{n}= sum_{d|n}frac{1}{d}$ which is equal to $ U * f$ using the convolution notation.
  $endgroup$
  – Alexandros
  Mar 25 at 20:07
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @mupin By definition $sigma(n) = sum_{d | n} d = sum_{d | n} n/d$ so $sigma(n)/n = sum_{d | n} 1/d= 1 ast (1/n)$. Then $(sigma(n)/n) ast mu =sum_{l | n} mu(n/l)sum_{d | l} 1/d = sum_{d | n} 1/d sum_{l | n, d | l} mu(n/l)$ with $k = n/l$ it is $= sum_{d | n} frac1d sum_{k | n, k | n/d} mu(k)= sum_{d | n} frac1d 1_{n/d= 1} = 1/n$
  $endgroup$
  – reuns
  Mar 25 at 21:58
  
  
  

  
  
  
  

add a comment | 

$begingroup$

Hello and welcome to MSE.

Write $ frac{σ(n)}{n} = (U*f)(n)$ , where $f(n)=frac{1}{n}$, and $U(n)=1$ for all n.

You are then asked to find $((U*f) * (μ))$.
Dirichlet convolution is associative and commutative, therefore, $(U*f) * (μ)= f*(U*μ)$, and $U* mu$ is the identity of the Dirichlet convolution, therefore overall we get $f(n)$, as required.

(here * means dirichlet convolution (https://en.wikipedia.org/wiki/Dirichlet_convolution))

share|cite|improve this answer

edited Mar 25 at 20:31

darij grinberg

11.5k33168

answered Mar 25 at 19:10

AlexandrosAlexandros

1,0951413

$endgroup$

share|cite|improve this answer

edited Mar 25 at 20:31

darij grinberg

11.5k33168

answered Mar 25 at 19:10

AlexandrosAlexandros

1,0951413

edited Mar 25 at 20:31

darij grinberg

11.5k33168

edited Mar 25 at 20:31

darij grinberg

11.5k33168

answered Mar 25 at 19:10

AlexandrosAlexandros

1,0951413

answered Mar 25 at 19:10

AlexandrosAlexandros

1,0951413