Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1972 USAMO Problems/Problem 1"

(→‎Solutions)
m (→‎Solutions: typo fix)
 
(10 intermediate revisions by 6 users not shown)
Line 6: Line 6:
  
 
===Solution 1===
 
===Solution 1===
−
 
−
As all of the values in the given equation are positive, we can invert it to get an equivalent equation:
 
−
<center><math>\frac{[a,b][b,c][c,a]}{[a,b,c]^2}=\frac{(a,b)(b,c)(c,a)}{(a,b,c)^2}</math>.</center>
 
−
We will now prove that both sides are equal, and that they are integers.
 
−
 
 
Consider an arbitrary prime <math>p</math>. Let <math>p^\alpha</math>, <math>p^\beta</math>, and <math>p^\gamma</math> be the greatest powers of <math>p</math> that divide <math>a</math>, <math>b</math>, and <math>c</math>.  
 
Consider an arbitrary prime <math>p</math>. Let <math>p^\alpha</math>, <math>p^\beta</math>, and <math>p^\gamma</math> be the greatest powers of <math>p</math> that divide <math>a</math>, <math>b</math>, and <math>c</math>.  
 
WLOG let <math>\alpha \leq \beta \leq \gamma</math>.
 
WLOG let <math>\alpha \leq \beta \leq \gamma</math>.
  
−
We can now, for each of the expressions in our equation, easily determine the largest power of <math>p</math> that divides it. In this way we will find that the largest power of <math>p</math> that divides the left hand side is <math>\beta+\gamma+\gamma-2\gamma = \beta</math>, and the largest power of <math>p</math> that divides the right hand side is <math>\alpha + \beta + \alpha - 2\alpha = \beta</math>. <math>\blacksquare</math>
+
Examining each factor in the equation, we see that the largest power of <math>p</math> that divides the left hand side is <math>2\gamma -(\beta+\gamma+\gamma) = -\beta</math>, and the largest power of <math>p</math> that divides the right hand side is 2\alpha -(<math>\alpha + \beta + \alpha) = -\beta</math>. Since every prime has the same power in both expressions, the expressions are equal. <math>\blacksquare</math>
  
 
===Solution 2===
 
===Solution 2===
Line 26: Line 21:
 
Note: This solution is more of a "bashy" solution, and is easier to think of than the first 2 solutions.
 
Note: This solution is more of a "bashy" solution, and is easier to think of than the first 2 solutions.
  
−
Dividing both sides of the equation by <math>(a,b,c)^2</math>, and then multiplying both sides by <math>[a,b][b,c][c,a]</math> gives us <cmath>(\frac{[a,b,c]}{(a,b,c)})^2 = \frac{[a,b][b,c][c,a]}{(a,b)(b,c)(c,a)}.</cmath>
+
Dividing both sides of the equation by <math>(a,b,c)^2</math>, and then multiplying both sides by <math>[a,b][b,c][c,a]</math> gives us <cmath>\left(\frac{[a,b,c]}{(a,b,c)}\right)^2 = \frac{[a,b][b,c][c,a]}{(a,b)(b,c)(c,a)}.</cmath>
 
Now, we look at the prime factorisations of <math>a,b,c</math>. Let  
 
Now, we look at the prime factorisations of <math>a,b,c</math>. Let  
 
<cmath>a=2^{x_1}\cdot 3^{x_2}\cdot 5^{x_3}\cdots,</cmath>
 
<cmath>a=2^{x_1}\cdot 3^{x_2}\cdot 5^{x_3}\cdots,</cmath>
Line 34: Line 29:
 
Thus, we have <cmath>[a,b,c]=2^{\max(x_1,y_1,z_1)} \cdot 3^{\max(x_2,y_2,z_2)} \cdot 5^{\max(x_3,y_3,z_3)} \cdots</cmath>
 
Thus, we have <cmath>[a,b,c]=2^{\max(x_1,y_1,z_1)} \cdot 3^{\max(x_2,y_2,z_2)} \cdot 5^{\max(x_3,y_3,z_3)} \cdots</cmath>
 
and <cmath>(a,b,c)=2^{\min(x_1,y_1,z_1)} \cdot 3^{\min(x_2,y_2,z_2)} \cdot 5^{\min(x_3,y_3,z_3)} \cdots.</cmath>
 
and <cmath>(a,b,c)=2^{\min(x_1,y_1,z_1)} \cdot 3^{\min(x_2,y_2,z_2)} \cdot 5^{\min(x_3,y_3,z_3)} \cdots.</cmath>
−
Now, we see that <math>(\frac{[a,b,c]}{(a,b,c)}) = 2^{\max(x_1,y_1,z_1) - \min(x_1,y_1,z_1)} \cdot 3^{\max(x_2,y_2,z_2) - \min(x_2,y_2,z_2)} \cdot 5^{\max(x_3,y_3,z_3) - \min(x_3,y_3,z_3)} \cdots.</math> Squaring the LHS will just double all the exponents on the RHS.
+
Now, we see that <math>\left(\frac{[a,b,c]}{(a,b,c)}\right) = 2^{\max(x_1,y_1,z_1) - \min(x_1,y_1,z_1)} \cdot 3^{\max(x_2,y_2,z_2) - \min(x_2,y_2,z_2)} \cdot 5^{\max(x_3,y_3,z_3) - \min(x_3,y_3,z_3)} \cdots.</math> Squaring the LHS will just double all the exponents on the RHS.
  
  
Line 46: Line 41:
  
 
Finally, canceling out the <math>y_i</math>'s and collecting like terms, we see the RHS is <math>2z_i - 2x_i</math>, which is equal to the LHS. Thus, this equation is true, and we are done. <math>\square</math>
 
Finally, canceling out the <math>y_i</math>'s and collecting like terms, we see the RHS is <math>2z_i - 2x_i</math>, which is equal to the LHS. Thus, this equation is true, and we are done. <math>\square</math>
 +
 +
===Solution 4===
 +
Let
 +
<cmath>a=dzxA</cmath><cmath>b=dxyB</cmath><cmath>c=dyzC</cmath>where <math>\gcd(A,B,C)=\gcd(x,y,z)=1</math>. (Existence proof missing.) Then, <math>\operatorname{lcm}(a,b,c)^2=(dxyzABC)^2</math> and <math>\operatorname{lcm}(a,b)=dxyzAB</math>. Using this cyclically, we have
 +
<cmath>\text{LHS}=\frac{d^2x^2y^2z^2A^2B^2C^2}{(dxyzAB)(dxyzBC)(dxyzCA)}=\frac{1}{dxyz}.</cmath>Now, note that <math>\gcd(a,b,c)^2=d^2</math> and <math>\gcd(a,b)=dx</math>. Using this cyclically, we have
 +
<cmath>\text{RHS}=\frac{d^2}{(dx)(dy)(dz)}=\frac{1}{dxyz}.</cmath>
 +
-brainiacmaniac31
 +
  
 
{{alternate solutions}}
 
{{alternate solutions}}

Latest revision as of 10:14, 6 October 2023

Problem

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)}$.

Solutions

Solution 1

Consider an arbitrary prime $p$. Let $p^\alpha$, $p^\beta$, and $p^\gamma$ be the greatest powers of $p$ that divide $a$, $b$, and $c$. WLOG let $\alpha \leq \beta \leq \gamma$.

Examining each factor in the equation, we see that the largest power of $p$ that divides the left hand side is $2\gamma -(\beta+\gamma+\gamma) = -\beta$, and the largest power of $p$ that divides the right hand side is 2\alpha -($\alpha + \beta + \alpha) = -\beta$. Since every prime has the same power in both expressions, the expressions are equal. $\blacksquare$

Solution 2

Let $p = (a, b, c)$, $pq = (a, b)$, $pr = (b, c)$, and $ps = (c, a)$. Then it follows that $q, r, s$ are pairwise coprime and $a = pqsa'$, $b = pqrb'$, and $c = prsc'$, with $a', b', c'$ pairwise coprime as well. Then, we wish to show \[\frac{(pqrsa'b'c')^2}{(pqrsa'b')(pqrsb'c')(pqrsc'a')} = \frac{p^2}{(pq)(pr)(ps)},\] which can be checked fairly easily.

Solution 3 (very long, but detailed)

Note: This solution is more of a "bashy" solution, and is easier to think of than the first 2 solutions.

Dividing both sides of the equation by $(a,b,c)^2$, and then multiplying both sides by $[a,b][b,c][c,a]$ gives us \[\left(\frac{[a,b,c]}{(a,b,c)}\right)^2 = \frac{[a,b][b,c][c,a]}{(a,b)(b,c)(c,a)}.\] Now, we look at the prime factorisations of $a,b,c$. Let \[a=2^{x_1}\cdot 3^{x_2}\cdot 5^{x_3}\cdots,\] \[b=2^{y_1}\cdot 3^{y_2}\cdot 5^{y_3}\cdots,\] \[c=2^{z_1}\cdot 3^{z_2}\cdot 5^{z_3}\cdots,\] where all of the $x_1, y_1, z_1$ are nonnegative integers (they could be 0). Thus, we have \[[a,b,c]=2^{\max(x_1,y_1,z_1)} \cdot 3^{\max(x_2,y_2,z_2)} \cdot 5^{\max(x_3,y_3,z_3)} \cdots\] and \[(a,b,c)=2^{\min(x_1,y_1,z_1)} \cdot 3^{\min(x_2,y_2,z_2)} \cdot 5^{\min(x_3,y_3,z_3)} \cdots.\] Now, we see that $\left(\frac{[a,b,c]}{(a,b,c)}\right) = 2^{\max(x_1,y_1,z_1) - \min(x_1,y_1,z_1)} \cdot 3^{\max(x_2,y_2,z_2) - \min(x_2,y_2,z_2)} \cdot 5^{\max(x_3,y_3,z_3) - \min(x_3,y_3,z_3)} \cdots.$ Squaring the LHS will just double all the exponents on the RHS.


Also, we have $[a,b]=2^{\max(x_1,y_1)} \cdot 3^{\max(x_2,y_2)} \cdot 5^{\max(x_3,y_3)} \cdots$. We can also build similar equations for $[b,c],[c,a],(a,b),(b,c)(c,a)$, using 2 of $x,y,z$ and either the minimum of the exponents or the maximum. We see that when we multiply $[a,b]$, $[b,c]$, and $[a,c]$ together, the exponents of the prime factorization will be $\max(x_i,y_i)+ \max(y_i,z_i)+ \max(z_i,x_1)$, where $i$ is chosen for the $i$'th prime. When we multiply $(a,b)$, $(b,c)$, and $(a,c)$ together, the exponents of the prime factorization will be $\min(x_i,y_i)+ \min(y_i,z_i)+ \min(z_i,x_1)$, where $i$ is chosen for the $i$'th prime.

Thus, when we divide the former by the latter, we have $\max(x_i,y_i)+ \max(y_i,z_i)+ \max(x_i,z_i) - (\min(x_i,y_i)+ \min(y_i,z_i)+ \min(x_i,z_i))$. We wish to prove that this is equal to the exponents we got from $([a,b,c]/(a,b,c))^2$.

In other words, this problem is now down to proving that \[2(\max(x_i,y_i,z_i) - \min(x_i,y_i,z_i)) = \max(x_i,y_i)+ \max(y_i,z_i)+ \max(x_i,z_i) - (\min(x_i,y_i)+ \min(y_i,z_i)+ \min(x_i,z_i))\] for any nonnegative integers $x_i, y_i, z_i$. WLOG, let $x_i \le y_i \le z_i$. Thus, computing maximums and minimums, this equation turns into \[2(z_i - x_i) = y_i + z_i + z_i - x_i - y_i - x_i.\]

Finally, canceling out the $y_i$'s and collecting like terms, we see the RHS is $2z_i - 2x_i$, which is equal to the LHS. Thus, this equation is true, and we are done. $\square$

Solution 4

Let \[a=dzxA\]\[b=dxyB\]\[c=dyzC\]where $\gcd(A,B,C)=\gcd(x,y,z)=1$. (Existence proof missing.) Then, $\operatorname{lcm}(a,b,c)^2=(dxyzABC)^2$ and $\operatorname{lcm}(a,b)=dxyzAB$. Using this cyclically, we have \[\text{LHS}=\frac{d^2x^2y^2z^2A^2B^2C^2}{(dxyzAB)(dxyzBC)(dxyzCA)}=\frac{1}{dxyz}.\]Now, note that $\gcd(a,b,c)^2=d^2$ and $\gcd(a,b)=dx$. Using this cyclically, we have \[\text{RHS}=\frac{d^2}{(dx)(dy)(dz)}=\frac{1}{dxyz}.\] -brainiacmaniac31


Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

See Also

1972 USAMO (Problems • Resources)
Preceded by
First Question 		Followed by
Problem 2
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1972_USAMO_Problems/Problem_1&oldid=199199"