Browse · MathNet
PrintMMO2025 Round 4
Mongolia 2025 number theory
Problem
Let denote the number of positive integers less than or equal to a given integer that are relatively prime to . For example, and . Let be nonnegative integers such that . If then show that (1) and, (2) .
Solution
Consider the prime factorization , where are the exponents. Then It is clear that since . (i) The case is clear. So assume that . Then . (ii) By the given condition we get that , hence .
Techniques
φ (Euler's totient)Prime numbersFactorization techniques