A = d ∣ 1 7 2 9 ! ∑ ϕ ( d ) μ 2 ( d ) , B = ϕ ( 1 7 2 9 ! ) 1 7 2 9 !
Find the relationship between A and B .
Notations
μ ( d ) denotes the Möbius function .
ϕ ( d ) denotes the Euler's totient function .
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.
Very nice, as usual! (+1) I guess this topic is getting a little old... I will have to find a new theme for the problems I pose. If I'm ever stranded on a remote island, I will do a lot of these sums to keep myself entertained ;)
Here is a "compressed" version of Aareyan's fine solution:
a ( n ) = ∑ d ∣ n ϕ ( d ) μ 2 ( d ) and b ( n ) = ϕ ( n ) n are both multiplicative functions. For a prime power n = p m we have a ( p m ) = ϕ ( 1 ) μ 2 ( 1 ) + ϕ ( p ) μ 2 ( p ) = p − 1 p = p m − p m − 1 p m = ϕ ( p m ) p m = b ( p m ) Thus a ( n ) = b ( n ) for all n , and for n = 1 7 2 9 ! we have A = B .
Good approach for expressing these multiplicative functions.
Problem Loading...
Note Loading...
Set Loading...
let P be the set of prime factors of 1729!.then: B = ϕ ( 1 7 2 9 ! ) 1 7 2 9 ! = 1 7 2 9 ! ∏ p ∈ P ( 1 − p 1 ) 1 7 2 9 ! = p ∈ P ∏ p − 1 p this was easily done by just the definition of the phi function.the other function given is multiplicative.proof: f ( d ) = ϕ ( d ) μ 2 ( d ) we see f(1)=1, and f(ab) for coprime a,b: f ( a b ) = ϕ ( a b ) μ 2 ( a b ) = ϕ ( a ) μ 2 ( a ) ϕ ( b ) μ 2 ( b ) = f ( a ) f ( b ) so it is multiplicative. the summation at 1 is 1, so it is multiplicative as well. recall that μ ( p k ) = 0 for k>1. we can split the summation by the prime factors of 1729!(set P), or in product notation A = p ∈ P ∏ d ∣ p ∑ ( ϕ ( d ) μ 2 ( d ) ) why only one power of p?, because starting from 2nd power, the mobius function will return 0, so that part has no value. we can write this as A = p ∈ P ∏ ( 1 μ 2 ( 1 ) + ϕ ( p ) μ 2 ( p ) ) = p ∈ P ∏ ( 1 + p − 1 1 ) = p ∈ P ∏ ( p − 1 p ) this is equal to B, and hence A=B.