MathDB

4

Part of 2010 Balkan MO

Problems(1)

f(n+p) != f(n) for any n and prime p

Source: Balkan MO 2010, Problem 4

5/4/2010
For each integer nn (n≥2n \ge 2), let f(n)f(n) denote the sum of all positive integers that are at most nn and not relatively prime to nn. Prove that f(n+p)≠f(n)f(n+p) \neq f(n) for each such nn and every prime pp.
functionnumber theorygreatest common divisorrelatively primetotient functionnumber theory proposed