Happy birthday, Ramanujan!

A = d 1729 ! μ 2 ( d ) ϕ ( d ) , B = 1729 ! ϕ ( 1729 ! ) A=\sum_{d|1729!}\frac{\mu^2(d)}{\phi(d)}, \hspace {15 mm} B=\frac{1729!}{\phi(1729!)}

Find the relationship between A A and B B .

Notations

A = B A=B A < B A<B A > B A>B

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.

2 solutions

Aareyan Manzoor
Dec 22, 2015

let P be the set of prime factors of 1729!.then: B = 1729 ! ϕ ( 1729 ! ) = 1729 ! 1729 ! p P ( 1 1 p ) = p P p p 1 B=\dfrac{1729!}{\phi(1729!)}=\dfrac{1729!}{1729!\prod_{p\in P} \left(1-\frac{1}{p}\right)}=\prod_{p\in P}\dfrac{p}{p-1} this was easily done by just the definition of the phi function.the other function given is multiplicative.proof: f ( d ) = μ 2 ( d ) ϕ ( d ) f(d)=\frac{\mu^2(d)}{\phi(d)} we see f(1)=1, and f(ab) for coprime a,b: f ( a b ) = μ 2 ( a b ) ϕ ( a b ) = μ 2 ( a ) ϕ ( a ) μ 2 ( b ) ϕ ( b ) = f ( a ) f ( b ) f(ab)=\frac{\mu^2(ab)}{\phi(ab)}=\frac{\mu^2(a)}{\phi(a)}\frac{\mu^2(b)}{\phi(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 \mu(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 ( μ 2 ( d ) ϕ ( d ) ) A=\prod_{p\in P} \sum_{d|p} \left(\frac{\mu^2(d)}{\phi(d)}\right) 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 ( μ 2 ( 1 ) 1 + μ 2 ( p ) ϕ ( p ) ) = p P ( 1 + 1 p 1 ) = p P ( p p 1 ) A=\prod_{p\in P} \left(\frac{\mu^2(1)}{1}+\dfrac{\mu^2(p)}{\phi(p)}\right)=\prod_{p\in P} \left(1+\dfrac{1}{p-1}\right)=\prod_{p\in P} \left(\dfrac{p}{p-1}\right) this is equal to B, and hence A=B.

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 ;)

Otto Bretscher - 5 years, 5 months ago
Otto Bretscher
Dec 22, 2015

Here is a "compressed" version of Aareyan's fine solution:

a ( n ) = d n μ 2 ( d ) ϕ ( d ) a(n)=\sum_{d|n}\frac{\mu^2(d)}{\phi(d)} and b ( n ) = n ϕ ( n ) b(n)=\frac{n}{\phi(n)} are both multiplicative functions. For a prime power n = p m n=p^m we have a ( p m ) = μ 2 ( 1 ) ϕ ( 1 ) + μ 2 ( p ) ϕ ( p ) = p p 1 = p m p m p m 1 = p m ϕ ( p m ) = b ( p m ) a(p^m)=\frac{\mu^2(1)}{\phi(1)}+\frac{\mu^2(p)}{\phi(p)}=\frac{p}{p-1}=\frac{p^m}{p^m-p^{m-1}}=\frac{p^m}{\phi(p^m)}=b(p^m) Thus a ( n ) = b ( n ) a(n)=b(n) for all n n , and for n = 1729 ! n=1729! we have A = B \boxed{A=B} .

Moderator note:

Good approach for expressing these multiplicative functions.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...