USAMO 1972 #1 July 18, 2009Posted by lumixedia in Problem-solving.
Tags: contest math, number theory, olympiad math, USAMO, USAMO 1972
My first post was going to be an introduction to combinatorial game theory, but putting that together would have been rather more complicated than grabbing some USAMO problem and putting up my solution, so of course I chose the path of less resistance. The intro to game theory will come eventually, but in the meantime, here’s the first USAMO problem ever:
USAMO 1972 # 1. The symbols and denote the greatest common divisor and the least common multiple, respectively, of the positive integers . For example, and . Prove that
Here is, based on my first instinct when seeing this problem…
My solution. Let , , , and where are integers. We have that are relatively prime since otherwise some factor greater than would divide both and and therefore divide all of , a contradiction. Then we have ; since is certainly a multiple of we can write where is an integer. Similarly, we conclude that are pairwise relatively prime and that and where are integers.
We have that are pairwise relatively prime since otherwise some factor greater than would divide (WLOG) both and and therefore divide both and , a contradiction. We also have since otherwise we would again have a factor greater than dividing all of .
Now we can write , since, as we just showed, . Similarly, and . We claim that . Clearly is a multiple of ; if it were not , there would be some so that
are all integers. But since no divides any two of or any two of , so that in order to divide all of , we must have divide (WLOG) all of , which is impossible since . We conclude that . Now we have a little quick algebra…
And here is the unsurprisingly quicker, cleverer, and possibly more convincing…
Official solution. For an arbitrary prime , suppose the exponent on in the prime factorization of is and define similarly. Assume WLOG . Take the reciprocal of both sides of the desired equation; then the exponent on in the prime factorization of the LHS is
while the exponent on in the prime factorization of the RHS is
so the two sides have the same prime factorization and are therefore equal.
Hmm yeah, modern USAMOs are probably more interesting than the old ones, but consequently posts about them would take longer to write, so whatever.