##
USAMO 1972 #1 *July 18, 2009*

*Posted by lumixedia in Problem-solving.*

Tags: contest math, number theory, olympiad math, USAMO, USAMO 1972

trackback

Tags: contest math, number theory, olympiad math, USAMO, USAMO 1972

trackback

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.

The point of the “look at everything mod a prime” strategy when it comes to gcd and lcm problems is that the poset under division is a product of a countable number of chains, one for each prime. So there are two symmetries in the problem. The first symmetry is that each of these chains is interchangeable, and the second symmetry is that each of the variables is interchangeable. Taking advantage of both symmetries is what makes the second solution shorter.

Interesting. I’m pretty unfamiliar with some language everyone else here takes for granted, so could you clarify these parts of your comment?

~Poset N under division–this means that one element is considered “greater than” another if the second divides the first?

~Chains–is a chain like p, p^2, p^3, etc.?

~Product of said chains–assuming I understood the previous two phrases correctly, this basically makes sense, but how does the formal definition go?

~By symmetry, do you just mean something like that all primes behave the same in this context?

1. Yep. Another way to think about it is that the (ordered) monoid under multiplication is a direct sum of countable copies of the monoid under addition, and it inherits the order.

2. Yep. A chain is a totally ordered poset, and is a chain under divisibility for every prime.

3. The product of two posets consists of the Cartesian product with the ordering if and only if . This is exactly the condition that an integer divides another integer if and only if they divide each other “locally,” i.e. the exponent of a given prime in the prime factorization of the former is always less than or equal to that of the latter.

4. I mean exactly that. When you’re only dealing with multiplicative properties of the integers and you can ignore the additive structure, the primes all behave the same way. It’s a good thing to look for in a number theory problem, since most of what makes number theory hard is the presence of both additive and multiplicative structure (for example, in Diophantine equations).

I should also mention that the gcd and lcm operations have names in this more general setup: they’re called meet and join respectively, and they turn into a lattice. You might know meet and join under the more familiar names intersection and union, or equivalently AND and OR; these terms occur in studying Boolean lattices, where the underlying poset is that of the subsets of a set under inclusion.

Ultimately, the point of all this jargon is to highlight structural similarities between different lattices. Boolean lattices and, say, the lattice of divisors of a given integer share the property that they are both products of chains; it’s just that in the Boolean case each of these chains has length 2. So one can gain some useful intuition about how gcd and lcm work by using intuition from the Boolean case.

This is an interesting way to think of . Is it possible to shorten and/or generalize number-theoretic results using this more abstract approach?

The biggest thing looking at poset structure does is clarify the notion of arithmetic function, particularly the central role played by the Mobius function. It turns out that

everyposet has an associated Mobius function, and the construction of the Mobius function of a Boolean lattice is none other than by inclusion-exclusion. This should make sense if you’ve ever computed the totient function by inclusion-exclusion; the same argument carries through in a very general setting. (Mobius functions are multiplicative under product, so once you’ve computed the Mobius function of a chain you get the Boolean case and the divisibility case with one stone.)So what is the appropriate generalization of an arithmetic function? It turns out that what you want to look at is (a certain subalgebra of) the incidence algebra of a locally finite poset. The incidence algebra has a distinguished function called the zeta function (which, for , is – surprise – the Riemann zeta function), and its inverse, if it exists, is the Mobius function of the poset.

Gian-Carlo Rota popularized the idea that the different types of generating functions that appear in combinatorics are really (reduced) incidence algebras over different posets. For example, ordinary generating functions exist in the incidence algebra of the non-negative integers under the order inherited from , and exponential generating functions exist in the incidence algebra of the poset of finite sets under inclusion.

This is some deep stuff. It even turns out that the Mobius function of a poset is related to the Euler characteristic of a certain simplicial complex associated to the poset – in two ways! I don’t understand this connection very well, but it’s fascinating to think about.

This is very interesting indeed. I was aware that there was a generalization of the Mobius formula of some sort, in a combinatorial way (e.g. the paper I needed to read actually used it, though only in a minor way).

I should probably learn more about combinatorics and abstract analytic number theory to become more familiar with tools such as incidence algebras and (this type of) zeta functions.

Wow, thanks for all the information. I need to learn some non-high-school math sometime…I really do.

[…] the representations of . The other half seem to be puzzles and Olympiad problems; for example, this post starts out by talking about the first US Olympiad problem ever, and moves to discussion of lattices […]