Compute
d ∣ 2 0 1 5 ! ∑ μ ( d ) ϕ ( d ) .
Notations:
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.
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!
Note that this function is a multiplicative function .
Note that each prime factor ≤ 1 0 0 7 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 2 0 0 5 ⋅ 2 2 0 0 5 2 0 1 5 ! ∑ μ ( d ) ϕ ( d ) = ⎝ ⎛ d ∣ 2 2 0 0 5 ∑ μ ( d ) ϕ ( d ) ⎠ ⎞ ⎝ ⎜ ⎛ d ∣ 2 2 0 0 5 2 0 1 5 ! ∑ μ ( d ) ϕ ( d ) ⎠ ⎟ ⎞ .
The stuff in blue becomes ⎝ ⎛ d ∣ 2 2 0 0 5 ∑ μ ( d ) ϕ ( d ) ⎠ ⎞ = μ ( 1 ) ϕ ( 1 ) + μ ( 2 ) ϕ ( 2 ) + μ ( 2 2 ) ϕ ( 2 2 ) + . . . + μ ( 2 2 0 0 5 ) ϕ ( 2 2 0 0 5 )
Then, we recall how the mobius function behaves over prime powers: μ ( p k ) = ⎩ ⎪ ⎨ ⎪ ⎧ = = = 1 − 1 0 , , , k = 0 k = 1 k > 1 so, using this: μ ( 1 ) ϕ ( 1 ) + μ ( 2 ) ϕ ( 2 ) + μ ( 2 2 ) ϕ ( 2 2 ) + . . . + μ ( 2 2 0 0 5 ) ϕ ( 2 2 0 0 5 ) = ( 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 .
Nice! (+1) You really figured out how to do these!
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)
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.
Log in to reply
@Otto Bretscher – .
Dirichlet inverse
Is there a simpler way to introduce this technique?
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" " μ = I e " . The nonzero multiplicative functions form a nice Abelian group.
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.)
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.
Log in to reply
@Otto Bretscher – i just read the wiki, and unfortunately didn't understand much....
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.
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.
Log in to reply
@Pi Han Goh – I would start with a discussion of multiplicative functions, namely functions f on N such that f ( m n ) = f ( m ) f ( n ) whenever 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 ⋆ , with the observation that ⋆ is commutative and associative, and the result that the convolution of two multiplicative functions is multiplicative. Since μ ⋆ 1 is multiplicative, it is easy to show that it is equal to δ , where δ ( n ) = { 1 0 n = 1 n ≥ 2 , is the multiplicative identity for the Dirichlet convolution. This is enough to show that if f = g ⋆ 1 , then g = f ⋆ μ , which is the Dirichlet inverse result.
At this point easy counting of HCFs shows that ϕ ⋆ 1 = i d , which gives us ϕ = μ ⋆ i d , 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.
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!
@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.
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 ) .
Lets call d 1 is the divisors of 2015! which is square free. By definition of μ ( d ) we could easily see that S = d ∣ 2 0 1 5 ! ∑ μ ( d ) ϕ ( d ) = d 1 ∣ 2 0 1 5 ! ∑ μ ( 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 , in which 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 ) + . . . ) + . . . − . . . This could be easily compact to ( 1 − ϕ ( p 1 ) ) ( 1 − ϕ ( p 2 ) ) . . . ( 1 − ϕ ( p k ) )
And note that p 1 = 2 , so 1 − ϕ ( p 1 ) = 0
Interesting solution without explicitly using multiplicative functions (+1)
Problem Loading...
Note Loading...
Set Loading...
A compressed solution for those who are in a hurry:
We note that f ( n ) = ∑ d ∣ n μ ( d ) ϕ ( d ) is a multiplicative function. For a prime power p m we have f ( p m ) = μ ( 1 ) ϕ ( 1 ) + μ ( p ) ϕ ( p ) + 0 = 2 − p since μ ( p k ) = 0 for k > 1 . Thus f ( n ) = ∏ p ∣ n ( 2 − p ) and f ( n ) = 0 for even n . In particular, S = f ( 2 0 1 5 ! ) = 0