JEEAdvanced
Compute the value of the sum S = sum_{k=1}^{100} k · gcd(k, 100).
Question
Compute the value of the sum S = sum_{k=1}^{100} k · gcd(k, 100).
✓ Verified answer: 31000checked by our engine — not a guess
Step-by-step solution
Group by d = gcd(k,100), where d ranges over divisors of 100.
For a fixed divisor d, the k in [1,100] with gcd(k,100)=d are k = d·j where gcd(j,100/d)=1 and 1≤j≤100/d.
Their contribution is sum k·d = d^2 · (sum of those j).
The sum of integers j in [1,m] coprime to m (m=100/d, m>1) is m·phi(m)/2; for m=1 the single j=1 gives sum 1.
Carrying out d over {1,2,4,5,10,20,25,50,100} and summing gives S = 31000.
(Direct computation confirms.)
Final answer31000
Stuck on a problem like this?
Paste any JEE or NEET question — verified working, a confidence %, and an honest “not sure” instead of a bluff.
Solve my doubt →More Number Theory solutions
Find the remainder when the power tower 7^(7^7) is divided by 1000.…JEE · MathHow many trailing zeros does 2026! have when it is written in base…JEE · MathA positive integer is called 'rough' if it is divisible by the square…JEE · MathLet D be the set of all positive divisors of 2025. Compute the sum of…JEE · MathFind the number of ordered pairs of positive integers (a, b) such…JEE · MathConsider repdigit numbers made entirely of the digit 8, i.e. 8, 88,…JEE · MathLet sigma(n) denote the sum of all positive divisors of n. Count the…JEE · MathFind the number of integers x with 0 ≤ x < 18000 satisfying x^2 ≡ 1…JEE · Math