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$ .

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

Page

Toolbox

Search

2021 USAJMO Problems/Problem 5

Solution

See Also