Number theoryDifficulty 9.1Prove itChina National Team Selection Test · China
Given any n (>1) coprime positive integers a1,a2,…,an, denote A=a1+a2+⋯+an. Let di=(A,ai) (the greatest common divisor), i=1,2,…,n. Let Di be the greatest common divisor of {a1,a2,…,an}∖{ai}, i=1,2,…,n. Find the minimum of ∏i=1ndiDiA−ai. (posed by Zhang Sihui)
This one wants a proof. Work it on paper, read the official solution, then mark
yourself honestly — the ladder only means something if the record is true.
Official solution
Consider D1=(a2,a3,…,an) and d2=(a2,A)=(a2,a1+a2+⋯+an). Let (D1,d2)=d. Then d∣a2,d∣a3,…,d∣an,d∣a1+a2+⋯+an. Thus, d∣a1. Consequently, d∣(a1,a2,…,an). Since a1,a2,…,an are coprime, we have d=1. Note that D1∣a2,D2∣a2 and (D1,D2)=1. We have D1d2∣a2. So D1d2≤a2. Similarly, we have D2d3≤a3,…,Dnd1≤a1. Hence, i=1∏ndiDi=(D1d2)⋅(D2d3)⋅⋯⋅(Dnd1)≤a2a3…ana1=i=1∏nai.1◯ Considering i=1∏n(A−ai)=i=1∏nj=i∑aj≥i=1∏n(n−1)j=i∏ajn−11=(n−1)n⋅i=1∏nai2◯ and by ① and ②, we see that i=1∏ndiDiA−ai≥(n−1)n. On the other hand, if a1=a2=⋯=an=1, i=1∏ndiDiA−ai=(n−1)n. Summing up, the minimum of ∏i=1ndiDiA−ai is (n−1)n.
Source: MathNet,
licensed CC-BY-4.0.
Statement and solution reproduced as published; topic, difficulty and ordering added
by this site.