S = d ∣ 1 2 0 9 0 ∑ ϕ ( d ) 1
Find the smallest positive integer a such that a × S is an integer.
Clarifications
The sum S is taken over all 32 positive integer divisors d of 1 2 0 9 0 = 6 × 2 0 1 5
ϕ ( 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.
Yes, exactly! Very nice, Comrade! Does this formula d ∣ n ∑ ϕ ( d ) 1 = ϕ ( n ) n work for all positive integers n ?
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
nice! i used multiplicity again... up voted.
f ( n ) = ∑ d ∣ n ϕ ( d ) 1 is a multiplicative function, with f ( p ) = ϕ ( 1 ) 1 + ϕ ( p ) 1 = p − 1 p for primes.
Thus S = f ( 1 2 0 9 0 ) = f ( 2 ∗ 3 ∗ 5 ∗ 1 3 ∗ 3 1 ) = 1 × 2 × 4 × 1 2 × 3 0 2 × 3 × 5 × 1 3 × 3 1 = 9 6 4 0 3 , so that a = 9 6
Very nice problem. Thank you Comrade Otto
Very correct Otto sir ... I also had the similar approach ... In your method +1 ;)
Problem Loading...
Note Loading...
Set Loading...
First, we have ϕ ( m ) * ϕ ( n ) = ϕ ( 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 of 12090, we have d and 1 2 0 9 0 / d are coprime, in other word ϕ ( d ) * ϕ ( 1 2 0 9 0 / d ) = ϕ ( 1 2 0 9 0 )
Then we have S = d ∣ 1 2 0 9 0 ∑ ϕ ( d ) 1 = d ∣ 1 2 0 9 0 ∑ ϕ ( 1 2 0 9 0 ) ϕ ( d ) = ϕ ( 1 2 0 9 0 ) ∑ d ∣ 1 2 0 9 0 ϕ ( d )
We can easily see that d ∣ 1 2 0 9 0 ∑ ϕ ( d ) = ( ϕ ( 2 ) + 1 ) ∗ ( ϕ ( 3 ) + 1 ) ∗ ( ϕ ( 5 ) + 1 ) ∗ ( ϕ ( 1 3 ) + 1 ) ∗ ( ϕ ( 3 1 ) + 1 )
Because RHS when expand will have 32 parts, each part will have a form of ϕ ( i ) ∗ ϕ ( j ) ∗ ϕ ( k ) . . . , in which i,j,k... are in the set of (2,3,5,13,31), which equal to ϕ ( d ) , d ∣ 1 2 0 9 0 , equal to LHS.
If d is a prime then ϕ ( d ) = d − 1 , So S = ϕ ( 2 ) ∗ ϕ ( 3 ) ∗ ϕ ( 5 ) ∗ ϕ ( 1 3 ) ∗ ϕ ( 3 1 ) ( ϕ ( 2 ) + 1 ) ∗ ( ϕ ( 3 ) + 1 ) ∗ ( ϕ ( 5 ) + 1 ) ∗ ( ϕ ( 1 3 ) + 1 ) ∗ ( ϕ ( 3 1 ) + 1 ) = 1 ∗ 2 ∗ 4 ∗ 1 2 ∗ 3 0 2 ∗ 3 ∗ 5 ∗ 1 3 ∗ 3 1 = 9 6 4 0 3