## Euler totient and Mobius function

Primes, divisors, arithmetic, number properties, ...
Alhazen
Posts: 94
Joined: Sun Feb 20, 2011 9:55 pm

### Euler totient and Mobius function

Hi,

Here is an identity to prove :
rightformula.GIF (3.55 KiB) Viewed 7996 times
Is there a way to express mu(n) as function of phi(n)?

Thank you for any clue

Ps : I'm sorry I corrected the mistake.
Last edited by Alhazen on Fri Apr 06, 2012 8:35 pm, edited 1 time in total.
Alhazen
Posts: 94
Joined: Sun Feb 20, 2011 9:55 pm

### Re: Euler totient and Mobius function

Is it a new result or is it yet known?
Thank you for any clue.
thundre
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

### Re: Euler totient and Mobius function

1: 1 0
2: 3 1
3: 6 1

I don't see them ever being equal. Why even sum the right side to n? floor(n/(n+1)) = 0 for all positive n, so any expression multiplied by that will be 0.
Alhazen
Posts: 94
Joined: Sun Feb 20, 2011 9:55 pm

### Re: Euler totient and Mobius function

thundre wrote:1: 1 0
2: 3 1
3: 6 1

I don't see them ever being equal. Why even sum the right side to n? floor(n/(n+1)) = 0 for all positive n, so any expression multiplied by that will be 0.
You are right I did a big mistake.
It is k not k+1

Sorry sorry sorry.
thundre
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

### Re: Euler totient and Mobius function

Alhazen wrote:It is k not k+1
The updated formula checks out.

a(n) seems to approach n2 * .60792 for large n.

I have no idea how to prove the right and left sides are always equal.
Alhazen
Posts: 94
Joined: Sun Feb 20, 2011 9:55 pm

### Re: Euler totient and Mobius function

Thank you very much and once again sorry my mistake.
kevinsogo
Posts: 1204
Joined: Thu Sep 16, 2010 4:39 am
Location: Manila, Philippines

### Re: Euler totient and Mobius function

ceil(n/k) is just floor(n/k) + 1 unless k divides n, so the right hand side is equal to:

$$\sum_{k=1}^n \mu\left(k\right) \left\lfloor \frac{n}{k} \right\rfloor \left(\left\lfloor \frac{n}{k} \right\rfloor + 1\right) - \sum_{k|n} \mu\left(k\right) \left\lfloor \frac{n}{k} \right\rfloor$$
$$= \sum_{k=1}^n \mu\left(k\right) \left\lfloor \frac{n}{k} \right\rfloor^2 + \sum_{k=1}^n \mu\left(k\right) \left\lfloor \frac{n}{k} \right\rfloor - \sum_{k|n} \mu\left(k\right) \left(\frac{n}{k}\right)$$
$$= S_1 + S_2 - S_3$$

Now, we can prove the following:
S1 = 2 [sum]1[le]k[le]n &phi;(k) - 1
S2 = 1
S3 = &phi;(n)
Thus it is equal to your left hand side.

The proofs of these are relatively simple so you may try proving them yourself.

Hints:
The proof for S1 and S2 uses concepts from Problem 351 (View Problem).
The proof for S3 uses the substitution l = n/k and Möbius inversion.
Last edited by kevinsogo on Thu Apr 12, 2012 1:09 am, edited 1 time in total.
Alhazen
Posts: 94
Joined: Sun Feb 20, 2011 9:55 pm

### Re: Euler totient and Mobius function

Thank you for the proof.
No one found it in another forum.
Someone had found part of it.
Alhazen
Posts: 94
Joined: Sun Feb 20, 2011 9:55 pm

### Re: Euler totient and Mobius function

thundre wrote:
Alhazen wrote:It is k not k+1
The updated formula checks out.

a(n) seems to approach n2 * .60792 for large n.

I have no idea how to prove the right and left sides are always equal.
And 0.60792 = 6/(π^2)
Alhazen
Posts: 94
Joined: Sun Feb 20, 2011 9:55 pm

### Re: Euler totient and Mobius function

6/(π^2) is the density of squarefree numbers.
What can we do with that?
Lord_Farin
Posts: 239
Joined: Wed Jul 01, 2009 10:43 am
Location: Netherlands

### Re: Euler totient and Mobius function

Alhazen wrote:6/(π^2) is the density of squarefree numbers.
What can we do with that?
The squarefree numbers are the ones for which the Möbius function is nonzero.
Alhazen
Posts: 94
Joined: Sun Feb 20, 2011 9:55 pm

### Re: Euler totient and Mobius function

Lord_Farin wrote:
Alhazen wrote:6/(π^2) is the density of squarefree numbers.
What can we do with that?
The squarefree numbers are the ones for which the Möbius function is nonzero.

Yes! You are right.
Did someone said otherwise?
There are some links to exploit.
Did you take a look to my new formulation of the Mertens function ?
Ethan1024
Posts: 2
Joined: Wed Sep 11, 2013 7:09 am

### Re: Euler totient and Mobius function

From the Dirichlet convolution representation of the totient function
k3.PNG (1.14 KiB) Viewed 6645 times
Though it still sort of feels like I am cheating since I am still using lower order values of the mobius function,
and because it requires knowing all the divisors of n.