One more of those

Compute

d 2015 ! μ ( d ) ϕ ( d ) . \large \sum_{d|2015!}\mu(d)\phi(d).

Notations:


The answer is 0.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Otto Bretscher
Dec 22, 2015

A compressed solution for those who are in a hurry:

We note that f ( n ) = d n μ ( d ) ϕ ( d ) f(n)=\sum_{d|n}\mu(d)\phi(d) is a multiplicative function. For a prime power p m p^m we have f ( p m ) = μ ( 1 ) ϕ ( 1 ) + μ ( p ) ϕ ( p ) + 0 = 2 p f(p^m)=\mu(1)\phi(1)+\mu(p)\phi(p)+0=2-p since μ ( p k ) = 0 \mu(p^k)=0 for k > 1 k>1 . Thus f ( n ) = p n ( 2 p ) f(n)=\prod_{p|n}(2-p) and f ( n ) = 0 f(n)=0 for even n n . In particular, S = f ( 2015 ! ) = 0 S=f(2015!)=\boxed{0}

Awesome! Once I saw that it was the product of (2-p), I thought I would need a computational device to compute. When it gave me 0, I looked back in shame, but I almost couldn't believe that this would be 0 for any even!

Andre Bourque - 2 years, 10 months ago
Aareyan Manzoor
Dec 21, 2015

Note that this function is a multiplicative function .

Note that each prime factor 1007 \le 1007 is being repeated at least twice, and so is 2. For example, the power of 2 in 2015! is 2005, so we can write the summation as: d 2 2005 2015 ! 2 2005 μ ( d ) ϕ ( d ) = ( d 2 2005 μ ( d ) ϕ ( d ) ) ( d 2015 ! 2 2005 μ ( d ) ϕ ( d ) ) . \sum_{d|\color{#3D99F6}{2^{2005}}\cdot \color{#20A900}{\frac{2015!}{2^{2005}}}}\mu(d)\phi(d)=\color{#3D99F6}{\left(\sum_{d|2^{2005}} \mu(d)\phi(d)\right)}\color{#20A900}{\left(\sum_{d\mid\frac{2015!}{2^{2005}}} \mu(d)\phi(d)\right)}.

The stuff in blue becomes ( d 2 2005 μ ( d ) ϕ ( d ) ) = μ ( 1 ) ϕ ( 1 ) + μ ( 2 ) ϕ ( 2 ) + μ ( 2 2 ) ϕ ( 2 2 ) + . . . + μ ( 2 2005 ) ϕ ( 2 2005 ) \color{#3D99F6}{\left(\sum_{d|2^{2005}} \mu(d)\phi(d)\right)}=\mu(1)\phi(1)+\mu(2)\phi(2)+\mu(2^2)\phi(2^2)+...+\mu(2^{2005})\phi(2^{2005})

Then, we recall how the mobius function behaves over prime powers: μ ( p k ) = { = 1 , k = 0 = 1 , k = 1 = 0 , k > 1 \mu(p^k)=\begin{cases}=&1&,&k=0\\=&-1&,&k=1\\=&0&,&k>1\end{cases} so, using this: μ ( 1 ) ϕ ( 1 ) + μ ( 2 ) ϕ ( 2 ) + μ ( 2 2 ) ϕ ( 2 2 ) + . . . + μ ( 2 2005 ) ϕ ( 2 2005 ) = ( 1 ) ( 1 ) + ( 1 ) ( 1 ) + 0 + 0 + 0 + . . . + 0 = 0. \mu(1)\phi(1)+\mu(2)\phi(2)+\mu(2^2)\phi(2^2)+...+\mu(2^{2005})\phi(2^{2005})=(1)(1)+(-1)(1)+0+0+0+...+0=0. By the zero product property , one part of the product is zero, so the product is 0 \boxed{0} .

Nice! (+1) You really figured out how to do these!

Otto Bretscher - 5 years, 5 months ago

Log in to reply

Question: If we were to write up a wiki on Möbius function, what important points should we include inside that page? (Preparing pen and paper)

Pi Han Goh - 5 years, 5 months ago

Log in to reply

I would emphasize that the Möbius function is the Dirichlet inverse of the constant function 1... that's really it's "raison d'etre". I just wrote a solution a few minutes ago where I made that point.

Otto Bretscher - 5 years, 5 months ago

Log in to reply

@Otto Bretscher .

Dirichlet inverse

Is there a simpler way to introduce this technique?

Pi Han Goh - 5 years, 5 months ago

Log in to reply

@Pi Han Goh People should know the Dirichlet product; it's a central tool in number theory. Then the idea of an inverse ("division") is pretty natural" " μ = e I " \mu=\frac{e}{I}" . The nonzero multiplicative functions form a nice Abelian group.

Otto Bretscher - 5 years, 5 months ago

Log in to reply

@Otto Bretscher So, the prerequisite for Möbius function is Dirichlet convolution ? There's no other way around? I thought it's as simple as teaching Euler's totient function.

if there's no other way around, then if we were to write up a wiki on Dirichlet convolution, what important points should we include inside that page?

(I haven't learn what Abelian groups are.)

Pi Han Goh - 5 years, 5 months ago

Log in to reply

@Pi Han Goh Take a look here . When I learned about Dirichlet convolution (or just call it "product", less convoluted), I was fascinated by the fact that it relates many interesting functions in unexpected ways: Euler's totient function, the gdc sum, divisor sums, number of divisors etc... give lots of examples! A discussion of multiplication leads naturally to division... and the Möbius function arises naturally in that context.

Otto Bretscher - 5 years, 5 months ago

Log in to reply

@Otto Bretscher i just read the wiki, and unfortunately didn't understand much....

Aareyan Manzoor - 5 years, 5 months ago

Log in to reply

@Aareyan Manzoor You can't understand something like this in a few minutes, nobody does unless they know the stuff already... you have to meditate over it, work out examples etc.

Otto Bretscher - 5 years, 5 months ago

Log in to reply

@Otto Bretscher Can you list some EASY functions to be listed in this page ?

Please don't link to wikipedia again, it's hard to understand most of what they're saying.

Pi Han Goh - 5 years, 5 months ago

Log in to reply

@Pi Han Goh I would start with a discussion of multiplicative functions, namely functions f f on N \mathbb{N} such that f ( m n ) = f ( m ) f ( n ) f(mn) = f(m)f(n) whenever m , n m,n are coprime. Examples of these are legion! The identity function, the number of divisors function, the sum of divisors function, the Euler totient function, the Mobius function, the many functions that lurk in Brilliant Number Theory problems...

Then introduce the Dirichlet convolution \star , with the observation that \star is commutative and associative, and the result that the convolution of two multiplicative functions is multiplicative. Since μ 1 \mu \star 1 is multiplicative, it is easy to show that it is equal to δ \delta , where δ ( n ) = { 1 n = 1 0 n 2 , \delta(n) \; = \; \left\{ \begin{array}{lll} 1 & \qquad & n = 1 \\ 0 & \qquad & n \ge 2 \;, \end{array} \right. is the multiplicative identity for the Dirichlet convolution. This is enough to show that if f = g 1 f = g\star 1 , then g = f μ g = f \star \mu , which is the Dirichlet inverse result.

At this point easy counting of HCFs shows that ϕ 1 = i d \phi \star 1 = \mathrm{id} , which gives us ϕ = μ i d \phi = \mu \star \mathrm{id} , and we are away...

Don't introduce the Dirichlet convolution out of nowhere; put it in the context of multiplicative functions, with the convolution as a useful device for creating new multiplicative functions from old, and the reason for its existence/usefulness is more obvious.

Mark Hennings - 5 years, 4 months ago

Log in to reply

@Mark Hennings Woah that's super detailed! Let me see if there's a way to improve that wiki page (as it is already written up).

Please tell me you've published books/autobiography before, I want to read everything a god (you) has to say!

Pi Han Goh - 5 years, 4 months ago

@Otto Bretscher .

Dirichlet inverse

Is there a simpler way to introduce this technique? This concept seem to advanced, I thought since you're a professor, you have a simpler way to teach this concept.

Pi Han Goh - 5 years, 5 months ago

Log in to reply

@Pi Han Goh hmm.. i have to do researc on "Dirichlet inverse". the defination i know is the sum of all the primitive nth roots of unity is= μ ( n ) \mu(n) .

Aareyan Manzoor - 5 years, 5 months ago
Tran Hieu
Dec 21, 2015

Lets call d 1 d_1 is the divisors of 2015! which is square free. By definition of μ ( d ) \mu(d) we could easily see that S = d 2015 ! μ ( d ) ϕ ( d ) = d 1 2015 ! μ ( d 1 ) ϕ ( d 1 ) S=\sum_{d|2015!}\mu(d)\phi(d) =\sum_{d_1|2015!}\mu(d_1)\phi(d_1) d 1 d_1 could only take the form of 1 , p 1 , p 2 , . . . , p k , p 1 p 2 , p 1 p 3 , . . . , p k 1 p k , p 1 p 2 p 3 , . . . , p 1 p 2 . . . p k 1, p_1,p_2,...,p_k, p_1*p_2,p_1*p_3,...,p_{k-1}*p_k, p_1*p_2*p_3,..., p_1*p_2*...*p_k , in which p k p_k are the prime numbers less than 2015

So our sum will become 1 ( ϕ ( p 1 ) + ϕ ( p 2 ) + . . . + ϕ ( p k ) ) + ( ϕ ( p 1 p 2 ) + ϕ ( p 1 p 3 ) + . . . + ϕ ( p k 1 p k ) ) ( ϕ ( p 1 p 2 p 3 ) + . . . ) + . . . . . . 1 - (\phi(p_1)+\phi(p_2)+...+\phi(p_k)) +(\phi(p_1*p_2)+\phi(p_1*p_3)+...+\phi(p_{k-1}*p_k)) - (\phi(p_1*p_2*p_3)+...) +... -... This could be easily compact to ( 1 ϕ ( p 1 ) ) ( 1 ϕ ( p 2 ) ) . . . ( 1 ϕ ( p k ) ) (1-\phi(p_1))(1-\phi(p_2))...(1-\phi(p_k))

And note that p 1 = 2 p_1=2 , so 1 ϕ ( p 1 ) = 0 1-\phi(p_1)=\boxed{0}

Interesting solution without explicitly using multiplicative functions (+1)

Otto Bretscher - 5 years, 5 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...