MathDB

6

Part of 2011 Korea Junior Math Olympiad

Problems(1)

f(n) is the sum of \phi (a)\phi (b) for all (a, b) \in S_n

Source: KJMO 2011 p6

5/4/2019
For a positive integer nn, define the set SnS_n as Sn={(a,b)∣a,b∈N,lcm[a,b]=n}S_n =\{(a, b)|a, b \in N, lcm[a, b] = n\} . Let f(n)f(n) be the sum of ϕ(a)ϕ(b)\phi (a)\phi (b) for all (a,b)∈Sn(a, b) \in S_n. If a prime pp relatively prime to nn is a divisor of f(n)f(n), prove that there exists a prime q∣nq|n such that p∣q2−1p|q^2 - 1.
number theoryEuler s totient functionrelatively primecoprimedivisor