Let $a_{i}$, $i = 1,2, \dots ,n$, $n \geq 3$, be positive integers, having the greatest common divisor 1, such that \[a_{j}\textrm{ divide }\sum_{i = 1}^{n}a_{i}\] for all $j = 1,2, \dots ,n$. Prove that \[\prod_{i = 1}^{n}a_{i}\textrm{ divides }\Big{(}\sum_{i = 1}^{n}a_{i}\Big{)}^{n-2}.\]
Problem
Source: Romanian TST 3 2007, Problem 3
Tags: greatest common divisor, number theory proposed, number theory
23.05.2007 22:35
Let $p$ be a prime that divides some of the $a_{i}$'s. Now, can all the $a_{i}$'s be multiples of p? Obviously not, because they are coprime. Can all the $a_{i}$'s but one be multiples of p? Not, because is so, their sum would not be multiple of p, which is impossible. So, if k is the maximum exponent of p that divides some of the $a_{i}$'s, we have $p^{k}\mid a_{1}+a_{2}+\ldots+a_{n}$, and $p^{(n-2)k}\mid (a_{1}+a_{2}+\ldots+a_{n})^{n-2}$. But the maximum exponent of p that divides $a_{1}a_{2}\cdots a_{n}$ is $\le (n-2)k$, because at least two of the $a_{i}$'s are coprime to p, and the others have exponent $\le k$. If we to this reasoning for all the primes that divide some of the $a_{i}$'s, we get the result.
24.05.2007 00:37
My solution is the same of yours, edriv! Too easy for a romanian tst, no?
02.08.2024 18:43
It suffices to show that $$\nu_p(a_1\cdots a_n) \leq \nu_p((a_1+\cdots+a_n)^{n-2})$$for every prime $p$. If $p \nmid a_i$, then $\nu_p(a_1\cdots a_n) = 0 \leq \nu_p(a_1+a_2+\cdots+a_n)^{n-2}$. Thus, suppose $p$ is a prime dividing at least $1$ of the $a_i$. WLOG, suppose that $$\nu_p(a_n) \geq \nu_p(a_{n-1}) \geq \cdots \geq \nu_p(a_2) \geq \nu_p(a_1).$$The given conditions are equivalent to $$\begin{cases} \nu_p(a_1) = 0 \\ \nu_p(a_n) \leq \nu_p(a_1 + \cdots + a_n). \end{cases}$$Claim. $\nu_p(a_2) = 0$. Proof. For the sake of contradiction, suppose $\nu_p(a_2) \geq 1$. Then, it must be the case that $$\nu_p(a_1 + \cdots + a_n) = \mathrm{min}\{\nu_p(a_1), \nu_p(a_2), \cdots, \nu_p(a_n)\} = 0 \geq \nu_p(a_n),$$so $\nu_p(a_i) = 0$ for all $i \in \{1,2,\cdots,n\}$, a contradiction since $p$ divides at least one of the $a_i$. $\blacksquare$ It follows that \begin{align*} \nu_p(a_1\cdots a_n) &= \nu_p(a_1) + \nu_p(a_2) + \cdots + \nu_p(a_n) \\ &= \nu_p(a_3) + \nu_p(a_4) + \cdots + \nu_p(a_n) \, \, \, \text{(since $\nu_p(a_1) = \nu_p(a_2) = 0$)} \\ &\leq (n-2)\nu_p(a_n) \\ &\leq (n-2)\nu_p(a_1+\cdots+a_n) \\ &= \nu_p((a_1+\cdots+a_n)^{n-2}) \end{align*}for every prime $p$, and we are done. $\blacksquare$
02.08.2024 19:56
Sol:- $a_j |\sum_{i=1}^{n} a_i \forall j \in \{1,2,\cdots,n\} \implies LCM(a_1, \cdots , a_n)|\sum_{i=1}^{n} a_i $ . Let $p$ be any prime dividing $a_r$ for any $r \in \{1,2,\cdots,n\}$. Clearly it can't divide all of them since $GCD(a_1, \cdots , a_n)=1$ . If it divides all but one then $p \nmid \sum_{i=1}^{n} a_i$ but $p| a_r| \sum_{i=1}^{n}a_i $ gives contradiction. Thus there are atleast $2$ numbers in the sequence not divisible by $p$. Thus $v_p(\prod_{i=1}^{n}a_i)=\sum_{i=1}^{n}v_p(a_i) \leq (n-2) max (v_p(a_1), \cdots v_p(a_n))=v_p(LCM(a_1, \cdots , a_n)^{n-2}) \leq v_p(\sum_{i=1}^{n} a_i )^{n-2} \implies \prod_{i=1}^{n}a_i| (\sum_{i=1}^{n} a_i )^{n-2}$.