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.