Browse · MathNet
PrintChina 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