The symbols $ (a,b,\ldots,g)$ and $ [a,b,\ldots,g]$ denote the greatest common divisor and least common multiple, respectively, of the positive integers $ a,b,\ldots,g$. For example, $ (3,6,18)=3$ and $ [6,15]=30$. Prove that \[ \frac{[a,b,c]^2}{[a,b][b,c][c,a]}=\frac{(a,b,c)^2}{(a,b)(b,c)(c,a)}.\]
Problem
Source: 1972 USAMO Problem 1
Tags: number theory, least common multiple, greatest common divisor, AMC, USA(J)MO, USAMO
06.03.2010 05:56
Denote $ (a,b,c)=d$ $ (a,b)=de$ $ (b,c)=df$ $ (a,c)=dg$ Thus, $ a=degk$ $ b=defl$ $ c=dfgm$ $ [a,b]=defgkl$ $ [b,c]=dfeglm$ $ [a,c]=defgkm$ $ [a,b,c]=defgklm$ $ \frac{[a,b,c]^2}{[a,b].[b,c].[a,c]}=\frac{1}{defg}$ $ \frac{(a,b,c)^2}{(a,b).(b,c).(a,c)}=\frac{1}{defg}$ Thus, $ \frac{(a,b,c)^2}{(a,b).(b,c).(a,c)}=\frac{[a,b,c]^2}{[a,b].[b,c].[a,c]}$
06.03.2010 06:35
08.03.2010 02:12
Similar to the above but worded differently.
21.07.2010 02:14
Let the prime factorization of $n$ be equal to $n=\prod_{i=1}^{k} p_{i}^{e_i}$. Now rewrite this as \[n=\prod_{i=1}^{k} p_{i(1)}p_{i(2)} \dots p_{i(e_i)}\] Where $p_{n(m)}$ is considered a distinct element for each distinct $m$ although they are equal. Now define the prime set of $n$ to be equal to $X=(p_{n(m)} : 1 \le n \le k; 1 \le m \le e_n)$. Define $F(X)$ to be the product of the elements of $X$. Now we can establish several properties of $F(X)$. $(1)$ $F(A-B)=F(A)/F(B)$ $(2)$ $F(\sum A_i)=\prod F(A_i)$ $(3)$ $F(A_1 \cap A_2 \cap \dots \cap A_n)=\gcd (F(A_1), F(A_2), \dots, F(A_n))$ $(4)$ $F(A_1 \cup A_2 \cup \dots \cup A_n)= lcm{(F(A_1), F(A_2), \dots, F(A_n))}$ Let $A$, $B$ and $C$ be the prime sets of $a$, $b$ and $c$ respectively. By the principle of inclusion-exclusion we have that, \[P= A \cup B \cup C = A+B+C - A \cap B - B \cap C - A \cap C + A \cap B \cap C\] Now consider $F(P)$. \[F(P)=F(A \cup B \cup C)=F(A+B+C - A \cap B - B \cap C - A \cap C + A \cap B \cap C)\] \[F(P)=\frac{F(A)F(B)F(C)F(A \cap B \cap C)}{F(A \cap B)F(B \cap C)F(A \cap C)}\] Using the properties of $F(X)$, this simplifies to \[lcm(a,b,c)=\frac{abc \cdot \gcd(a,b,c)}{\gcd(a,b) \gcd(b,c) \gcd(a,c)}\] Squaring and division yields the desired result.
21.07.2010 10:52
We'll use $[a,b](a,b)=ab$, which is proven easily if we put $a=dp, b=dq$ where $p,q$ are coprime. Then $(a,b)=d$ and $[a,b]=dpq$, hence $[a,b](a,b)=d^2pq=(dp)(dq)=ab$ How do we construct the LCM for three numbers? By the Inclusion-Exclusion Principle, we start from the product $abc$; then we must cut out all the pairwise common divisors for the pairs $(a,b),(b,c),(c,a)$; but then we must take back the general common divisor for the triplet $(a,b,c)$. Hence $[a,b,c]={abc\over (a,b)(b,c)(c,a)}\cdot(a,b,c)$ Thus $[a,b,c]^2={(a,b,c)^2\over{{(a,b)^2\over ab}\cdot{(b,c)^2\over bc}\cdot{(c,a)^2\over ca}}}$ Now by the preliminary identity, ${(a,b)^2\over ab}={(a,b)^2\over(a,b)[a,b]}={(a,b)\over [a,b]}$, hence $[a,b,c]^2={(a,b,c)^2\over (a,b)(b,c)(c,a)}\cdot[a,b][b,c][c,a]$ and the result follows.
16.06.2013 13:39
sorry for reviving this post, but is the proof true when we let $a = da', b = db', c = dc'$ with $\GCD(a',b',c') = 1$ ?
16.06.2013 13:46
This is USAMO 1972.
16.06.2013 14:15
Could you see my question, sir?
20.03.2019 16:14
We know that Lcm(p,q,r) HCF (p,q)HCF(q,r)HCF(p,r) = pqr ×hcf (p,q,r). From this theorem the above result is very direct
15.04.2021 18:51
We let $p$ be some prime. We let $a, b, c$ have $A, B, C$ factors of $p$, respectively. We can then figure out that the number of factors of $p$ in the LHS is $2\max(A, B, C)-\max(A, B)-\max(B, C)-\max(C, A)$. We can also figure out that the number of factors of $p$ in the RHS is $2\min(A, B, C)-\min(A, B)-\min(B, C)-\min(C, A)$. We notice that both expressions are symmetric. We can now assume $A>B>C$ WLOG. We can simplify the first expression to get $2\max(A, B, C)-\max(A, B)-\max(B, C)-\max(C, A)=2A-A-B-A=-B$. We can also simplify the second expression to get $2\min(A, B, C)-\min(A, B)-\min(B, C)-\min(C, A)=2C-B-C-C=-B$. We know that even if our original assumption that $A>B>C$ was wrong, both expressions are still equal by our observation that both expressions are symmetric. We have proven that for any prime $p$ that there are the same number of factors of $p$ in the LHS as in the RHS. Therefore, $\frac{[a,b,c]^2}{[a,b][b,c][c,a]} = \frac{(a,b,c)^2}{(a,b)(b,c)(c,a)}$ for all positive integers $a, b, c$.
01.09.2021 19:27
15.07.2022 22:53
let us consider a certain prime $p$. WLOG assume that a has the greatest power of p in its factorization, and c has the least (thus b has the middle). now call the maximum power of p in each of a, b, and c be x, y, and . Then the result follows using properties of the $v_{p}$ function.
13.04.2023 03:51
I think the key here is just to let (a,b), (a,c), (b,c) and (a,b,c,) all be variables, express a,b, and c in terms of them, then substitute and solve.
20.07.2023 19:49
Let $p$ be any prime Let $d,e,f=v_p(a), v_p(b), v_p(c)$ $v_p([a,b])=max(d,e)$ $v_p([b,c])=max(e,f)$ $v_p([a,c])=max(d,f)$ $v_p((a,b))=min(d,e)$ $v_p((b,c))=min(e,f)$ $v_p((a,c))=min(d,f)$ So $v_p([a,b][b,c][a,c])=max(d,e)+max(e,f)+max(d,f)$ and $v_p((a,b)(b,c)(a,c))=min(d,e)+min(e,f)+min(d,f)$ WLOG $d \le e \le f$ Then $v_p([a,b][b,c][a,c])=e+2f$ and $v_p((a,b)(b,c)(a,c))=2d+e$ Also, $v_p(abc)=v_p(a)+v_p(b)+v_p(c)=d+e+f$ $v_p((a,b,c))=d$ $v_p([a,b,c])=f$ So $v_p(\frac{(a,b,c)^2}{(a,b)(b,c)(a,c)})=d+d-(2d+e)=-e=f+f-(e+2f)=v_p(\frac{[a,b,c]^2}{[a,b][b,c][a,c]})$ Because this is true for all primes, $\frac{(a,b,c)^2}{(a,b)(b,c)(a,c)} = \frac{[a,b,c]^2}{[a,b][b,c][a,c]}$
21.07.2023 18:39
Lemma: $2\cdot max(a,b,c)-max(a,b)-max(b,c)-max(c,a)=2\cdot min(a,b,c)-min(a,b)-min(b,c)-min(c,a)$ Proof: WLOG $a\geq b\geq c$ $LHS=2a-a-b-a=-b$ $RHS=2c-b-c-c=-b$ $\implies LHS=RHS$ qed. Let the prime factors of $[a,b,c]$ be $p_1, p_2, \cdots, p_k$ Let $a=\prod_{i=1}^k p_i^{\alpha_i}$ Let $b=\prod_{i=1}^k p_i^{\beta_i}$ Let $c=\prod_{i=1}^k p_i^{\gamma_i}$ $LHS=\frac{[a,b,c]^2}{[a,b][b,c][c,a]}=\frac{(\prod_{i=1}^k p_i^{max(\alpha_i, \beta_i, \gamma_i)})^2}{\prod_{i=1}^k p_i^{max(\alpha_i, \beta_i)}\prod_{i=1}^k p_i^{max(\beta_i, \gamma_i)}\prod_{i=1}^k p_i^{max(\gamma_i, \alpha_i)}}=\prod_{i=1}^k p_i^{2\cdot max(\alpha_i,\beta_i,\gamma_i)-max(\alpha_i,\beta_i)-max(\beta_i,\gamma_i)-max(\gamma_i,\alpha_i)}=$ Now we apply the Lemma $=\prod_{i=1}^k p_i^{2\cdot min(\alpha_i,\beta_i,\gamma_i)-min(\alpha_i,\beta_i)-min(\beta_i,\gamma_i)-min(\gamma_i,\alpha_i)}=\frac{(\prod_{i=1}^k p_i^{min(\alpha_i, \beta_i, \gamma_i)})^2}{\prod_{i=1}^k p_i^{min(\alpha_i, \beta_i)}\prod_{i=1}^k p_i^{min(\beta_i, \gamma_i)}\prod_{i=1}^k p_i^{min(\gamma_i, \alpha_i)}}=\frac{(a,b,c)}{(a,b)(b,c)(c,a)}=RHS$ And we are done
28.07.2023 12:58
The Proof is obvious by the theorem that $gcd(a,b,c)=\frac{abc\times lcm(a,b,c)}{lcm(a,b)lcm(b,c)lcm(c,a)}$ $\text{or we can Prove this result by taking an arbitrary variable } p_{1},p_{2},...,p_{n}$ $\text{and then putting them in form of }a=p_{1}^{x_{1}}\times p_{2}^{x_{2}}\times ...\times p_{n}^{x_{n}}$ and then we can take b,c symmetrically and after this we can show the statement that RHS=LHS by assuming $\text{WLOG } x_{1}\leq x_{2}\leq ...\leq x_{n}$ and further taking assumption WLOG that the powers of a is less than powers of b which is less than the powers of c and further we can Prove the above statement
28.11.2024 21:16
For any prime $p$, we have $$\frac{[a,b,c]^2}{[a,b][b,c][c,a]}=\frac{(a,b,c)^2}{(a,b)(b,c)(c,a)} \Leftrightarrow$$$$\frac{(\min(\nu_p(a), \nu_p(b), \nu_p(c))^2}{\min(\nu_p(a), \nu_p(b)) \cdot \min(\nu_p(b), \nu_p(c)) \cdot \min(\nu_p(a), \nu_p(c))} = \frac{(\max(\nu_p(a), \nu_p(b), \nu_p(c))^2}{\max(\nu_p(a), \nu_p(b)) \cdot \max(\nu_p(b), \nu_p(c)) \cdot \max(\nu_p(a), \nu_p(c))}$$ WLOG, let $\nu_p(a) \ge \nu_p(b) \ge \nu_p(c)$: $$\frac{(\min(\nu_p(a), \nu_p(b), \nu_p(c))^2}{\min(\nu_p(a), \nu_p(b)) \cdot \min(\nu_p(b), \nu_p(c)) \cdot \min(\nu_p(a), \nu_p(c))} = \frac{(\max(\nu_p(a), \nu_p(b), \nu_p(c))^2}{\max(\nu_p(a), \nu_p(b)) \cdot \max(\nu_p(b), \nu_p(c)) \cdot \max(\nu_p(a), \nu_p(c))} \Leftrightarrow$$$$\frac{(\nu_p(c))^2}{\nu_p(b) \cdot (\nu_p(c))^2} = \frac{(\nu_p(a))^2}{\nu_p(b) \cdot (\nu_p(a))^2} \Leftrightarrow$$$$\frac{1}{\nu_p(b)} = \frac{1}{\nu_p(b)}$$ So we are done. $\blacksquare$