Skip to main content
OlympiadHQ

Browse · MathNet

Print

MMO2025 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