Skip to main content
OlympiadHQ

Browse · MathNet

Print

VMO

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 .
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