Home > Algebra, IMO, Number theory, Olympiad, Problem Solving > Traian Lalescu Student contest 2011 Problem 2

Traian Lalescu Student contest 2011 Problem 2


Let n \geq 2 be a square-free positive integer, and denote by D_n the set of its divisors. Consider D \subset D_n, a set with the following properties:

  • 1 \in D;
  • x \in D \Rightarrow n/x \in D;
  • x,y \in D \Rightarrow \gcd(x,y) \in D.

Show that there exists a positive integer k such that |D|=2^k.

Traian Lalescu student contest 2011

Idea: Since n is square-free, any of its divisors can be identified with a subset of the set of the prime divisors of n, denoted P. The set D is identified with a set of parts of P with the following properties:

  • \emptyset \in D;
  • A \in D \Rightarrow P\setminus A \in D;
  • A,B \in D \Rightarrow A \cap B \in D;

We can prove that D is stable under union also. (try)

If D=\{\emptyset, P\}, then we are done. Else there exists \emptyset \neq A \neq P such that between \emptyset and A there are no other sets (the order is inclusion). Consider all such sets A_1,...,A_k which can be proved to be disjoint, and their union is P. Then the sets in D are all unions of A_i,\ i=1..k, and this can be done in 2^k ways.

The argument works just as smoothly if we consider the divisors of n ordered by the division operation.

Advertisements
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: