Difference between revisions of "1972 USAMO Problems/Problem 1"
m (→Solution 3 (very long, but detailed)) |
(→Solution 3 (very long, but detailed)) |
||
Line 34: | Line 34: | ||
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. |
Revision as of 23:33, 27 November 2016
Contents
Problem
The symbols and
denote the greatest common divisor and least common multiple, respectively, of the positive integers
. For example,
and
. Prove that
![$\frac{[a,b,c]^2}{[a,b][b,c][c,a]}=\frac{(a,b,c)^2}{(a,b)(b,c)(c,a)}$](http://latex.artofproblemsolving.com/a/3/7/a3797d87dfc7855e74fd6a01e4f48819256cecb4.png)
Solutions
Solution 1
As all of the values in the given equation are positive, we can invert it to get an equivalent equation:
![$\frac{[a,b][b,c][c,a]}{[a,b,c]^2}=\frac{(a,b)(b,c)(c,a)}{(a,b,c)^2}$](http://latex.artofproblemsolving.com/e/c/d/ecd36e521e220cc8d42f8555801b6efbfad9c570.png)
We will now prove that both sides are equal, and that they are integers.
Consider an arbitrary prime . Let
,
, and
be the greatest powers of
that divide
,
, and
.
WLOG let
.
We can now, for each of the expressions in our equation, easily determine the largest power of that divides it. In this way we will find that the largest power of
that divides the left hand side is
, and the largest power of
that divides the right hand side is
.
Solution 2
Let ,
,
, and
. Then it follows that
are pairwise coprime and
,
, and
, with
pairwise coprime as well. Then, we wish to show
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 , and then multiplying both sides by
gives us
Now, we look at the prime factorisations of
. Let
where all of the
are nonnegative integers (they could be 0).
Thus, we have
and
Now, we see that
Squaring the LHS will just double all the exponents on the RHS.
Also, we have . We can also build similar equations for
, using 2 of
and either the minimum of the exponents or the maximum.
We see that when we multiply
,
, and
together, the exponents of the prime factorization will be
, where
is chosen for the
'th prime.
When we multiply
,
, and
together, the exponents of the prime factorization will be
, where
is chosen for the
'th prime.
Thus, when we divide the former by the latter, we have . We wish to prove that this is equal to the exponents we got from
.
In other words, this problem is now down to proving that for any nonnegative integers
. WLOG, let
. Thus, computing maximums and minimums, this equation turns into
Finally, canceling out the 's and collecting like terms, we see the RHS is
, which is equal to the LHS. Thus, this equation is true, and we are done.
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.