2021 USAJMO Problems/Problem 5

A finite set $S$ of positive integers has the property that, for each $s \in S,$ and each positive integer divisor $d$ of $s$, there exists a unique element $t \in S$ satisfying $\text{gcd}(s, t) = d$. (The elements $s$ and $t$ could be equal.)

Given this information, find all possible values for the number of elements of $S$.

Solution

The answer is $0$ (left out by problem author) or $2^n$ for any non-negative integer $n$.

To construct $|S|=2^n$, take $2n$ distinct primes $p_1, q_1, p_2, q_2, \dots p_n, q_n$ and construct $2^n$ elements for $S$ by taking the product over all $n$ indices $i$ of either $p_i$ or $q_i$ for every $i$.

Note that (from the problem statement) each element of $S$ has $|S|$ divisors.

Now it suffices to show that there is no element $x \in S$ such that $x$ is divisible by more than one power of any prime.

Suppose there does exist an element $x$ and a prime $p$ such that $p^2 \mid x$.

This implies that there exists an element $c \in S$ that is divisible by $p$ but not $p^2$ by $\gcd (x,c)=p$.

Exactly half of $c$'s divisors are not divisible by $p$, so it follows that exactly half of the elements in $S$ are not divisible by $p$.

However, if $p^0 , p^1 , \dots p^k$ are the powers of $p$ dividing $x$ for some $k \ge 2$, only $\frac{1}{k+1}$ of the divisors of $x$ are not divisible by $p$.

But this means that $\frac{1}{k+1}$ of the elements of $S$ are not divisible by $p$, contradiction.

Therefore, $|S|$ must be some power of $2$.

See Also

2021 USAJMO (ProblemsResources)
Preceded by
Problem 4
Followed by
Problem 6
1 2 3 4 5 6
All USAJMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png