Skip to main content
OlympiadHQ

Browse · MathNet

Print

China National Team Selection Test

China number theory

Problem

Given any () coprime positive integers , denote . Let (the greatest common divisor), . Let be the greatest common divisor of , . Find the minimum of . (posed by Zhang Sihui)
Solution
Consider Let . Then . Thus, . Consequently, Since are coprime, we have . Note that and . We have . So . Similarly, we have . Hence, Considering and by ① and ②, we see that On the other hand, if , Summing up, the minimum of is .
Final answer
(n-1)^n

Techniques

Greatest common divisors (gcd)QM-AM-GM-HM / Power Mean