Browse · MathNet
PrintVMO
Vietnam number theory
Problem
For every pair of positive integers with , denote as the number of positive integers in the range that are coprime with . Find all positive integers such that satisfies these conditions
i) for all . ii) is divisible by .
i) for all . ii) is divisible by .
Solution
Firstly, we prove that if satisfies the first condition, then has only one prime divisor. Assume that has at least 2 prime divisors, let be the smallest prime divisor of and be the remaining prime divisors of . We have Hence, by choosing in i), one can get which is a contradiction. Therefore, must be a power of a prime. Let , note that thus and . If , using LTE, we have From this, we conclude that and . Similarly, for , applying LTE, we also have so and . Therefore, are all desired numbers.
Final answer
7, 17, 289
Techniques
φ (Euler's totient)Fermat / Euler / Wilson theoremsPrime numbers