Sum of all greatest values
Compute
g cd ( 1 , 1 5 5 ) + g cd ( 2 , 1 5 5 ) + g cd ( 3 , 1 5 5 ) + ⋯ + g cd ( 1 5 5 , 1 5 5 ) .
Notation : g cd ( m , n ) denote the Greatest Common Divisor of integers m and n .
The answer is 549.
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.
3 solutions
The function f ( n ) = ∑ k = 1 n g cd ( k , n ) is multiplicative, so f ( 1 5 5 ) = f ( 5 ) f ( 3 1 ) = ( 4 + 5 ) ( 3 0 + 3 1 ) = 5 4 9
Do you know the demonstration of that?
Log in to reply
The gcd sum is the Dirichlet convolution of the identity with Euler's totient function.
Log in to reply
I think you should still add one line of explanation for why
i = 1 ∑ n g cd ( i , n ) = d ∣ n ∑ d × ϕ ( d n )
Log in to reply
@Calvin Lin – For a given divisor d of n , we need to count the i with 1 ≤ i ≤ n such that g cd ( i , n ) = d . By definition of gcd, those are of the form i = k d where 1 ≤ k ≤ n / d and g cd ( k , n / d ) = 1 . There are ϕ ( n / d ) such k 's; thus the term d × ϕ ( n / d ) in our sum.
Factors of 155 are 1,5,31,155. Now there are 30 numbers within 1 to155 which are divisible by 5. Now they have gcd 5 with 155. Similarly there are 4 numbers divisible by 31 and having gcd 31 with155 within the limit. Rest numbers 120 are coprime with 155. 155 has155 as gcd with 155. So summing we get 549.
155 = 5*31
gcd(x,155)=1 unless x is a multiple of 5 and/or 31.
There are 4 x-values that are only multiples of 31, and 30 x-values that are only multiples of 5. 155 is a multiple of both. There are (155-35)=120 x-values remaining; for these, the GCD will be 1.
4(31) + 30(5) + 1(155) + 120(1) = 549.