Sixfold fun in 2015, Part 37

S = d 12090 1 ϕ ( d ) S=\sum_{d|12090}\frac{1}{\phi(d)}

Find the smallest positive integer a a such that a × S a\times S is an integer.

Clarifications

  • The sum S S is taken over all 32 positive integer divisors d d of 12090 = 6 × 2015 12090=6\times 2015

  • ϕ ( d ) \phi(d) denotes the Euler's totient function .


The answer is 96.

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

Tran Hieu
Dec 20, 2015

First, we have ϕ ( m ) \phi(m) * ϕ ( n ) \phi(n) = ϕ ( m n ) \phi(m*n) if m and n are coprime

Second, we have 12090 = 2 x 3 x 5 x 13 x 31, mean that with every positive interger divisors d d of 12090, we have d d and 12090 / d 12090/d are coprime, in other word ϕ ( d ) \phi(d) * ϕ ( 12090 / d ) \phi(12090/d) = ϕ ( 12090 ) \phi(12090)

Then we have S = d 12090 1 ϕ ( d ) = d 12090 ϕ ( d ) ϕ ( 12090 ) = d 12090 ϕ ( d ) ϕ ( 12090 ) S=\sum_{d|12090}\frac{1}{\phi(d)}=\sum_{d|12090}\frac{\phi(d)}{\phi(12090)}=\frac{\sum_{d|12090}\phi(d)}{\phi(12090)}

We can easily see that d 12090 ϕ ( d ) = ( ϕ ( 2 ) + 1 ) ( ϕ ( 3 ) + 1 ) ( ϕ ( 5 ) + 1 ) ( ϕ ( 13 ) + 1 ) ( ϕ ( 31 ) + 1 ) \sum_{d|12090}\phi(d) = (\phi(2)+1)*(\phi(3)+1)*(\phi(5)+1)*(\phi(13)+1)*(\phi(31)+1)

Because RHS when expand will have 32 parts, each part will have a form of ϕ ( i ) ϕ ( j ) ϕ ( k ) . . . \phi(i)*\phi(j)*\phi(k)... , in which i,j,k... are in the set of (2,3,5,13,31), which equal to ϕ ( d ) , d 12090 \phi(d), d|12090 , equal to LHS.

If d is a prime then ϕ ( d ) = d 1 \phi(d) = d-1 , So S = ( ϕ ( 2 ) + 1 ) ( ϕ ( 3 ) + 1 ) ( ϕ ( 5 ) + 1 ) ( ϕ ( 13 ) + 1 ) ( ϕ ( 31 ) + 1 ) ϕ ( 2 ) ϕ ( 3 ) ϕ ( 5 ) ϕ ( 13 ) ϕ ( 31 ) = 2 3 5 13 31 1 2 4 12 30 = 403 96 S=\frac{(\phi(2)+1)*(\phi(3)+1)*(\phi(5)+1)*(\phi(13)+1)*(\phi(31)+1)}{\phi(2)*\phi(3)*\phi(5)*\phi(13)*\phi(31)}=\frac{2*3*5*13*31}{1*2*4*12*30}=\frac{403}{96}

Yes, exactly! Very nice, Comrade! Does this formula d n 1 ϕ ( d ) = n ϕ ( n ) \sum_{d|n}\frac{1}{\phi(d)}=\frac{n}{\phi(n)} work for all positive integers n n ?

Otto Bretscher - 5 years, 5 months ago

Log in to reply

Of course not, it only work if and only if the prime factorization of n does not have any prime factor with exponent larger than 1

Tran Hieu - 5 years, 5 months ago

nice! i used multiplicity again... up voted.

Aareyan Manzoor - 5 years, 5 months ago
Otto Bretscher
Dec 21, 2015

f ( n ) = d n 1 ϕ ( d ) f(n)=\sum_{d|n}\frac{1}{\phi(d)} is a multiplicative function, with f ( p ) = 1 ϕ ( 1 ) + 1 ϕ ( p ) = p p 1 f(p)=\frac{1}{\phi(1)}+\frac{1}{\phi(p)}=\frac{p}{p-1} for primes.

Thus S = f ( 12090 ) = f ( 2 3 5 13 31 ) = 2 × 3 × 5 × 13 × 31 1 × 2 × 4 × 12 × 30 = 403 96 S=f(12090)=f(2*3*5*13*31)=\frac{2\times 3\times 5\times 13\times 31}{1\times 2\times 4\times 12\times 30}=\frac{403}{96} , so that a = 96 a=\boxed{96}

Very nice problem. Thank you Comrade Otto

Pi Han Goh - 5 years, 5 months ago

Very correct Otto sir ... I also had the similar approach ... In your method +1 ;)

A Former Brilliant Member - 5 years, 5 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...