Problem: 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 $\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 that $|S|$ must be a power of $2$ (including $1$),
or $|S| = 0$ (a trivial case we do not discuss further).

\paragraph{Construction.}
For any nonnegative integer $k$, a construction for $|S| = 2^k$ is given by
\[ S = \left\{
    (p_1 \text{ or } q_1)
    \times
    (p_2 \text{ or } q_2)
    \times
    \dots
    \times
    (p_k \text{ or } q_k)
  \right\}
\]
for $2k$ distinct primes $p_1$, \dots, $p_k$, $q_1$, \dots, $q_k$.

\paragraph{Converse.}
The main claim is as follows.
\begin{claim*}
  In any valid set $S$, for any prime $p$ and $x \in S$, $\nu_p(x) \le 1$.
\end{claim*}
\begin{proof}
  Assume for contradiction $e = \nu_p(x) \ge 2$.
  \begin{itemize}
    \ii On the one hand, let $s = x$ in the statement.
    Vary $t \in S$ across all the elements in $S$ to get each divisor of $x$ once.
    Since $\frac{e}{e+1}$ of the divisors of $x$ are divisible by $p$,
    it thus follows that $\frac{e}{e+1}$ of the elements are divisible by $p$.

    \ii On the other hand, consider a $y \in S$ such that $\nu_p(y)=1$,
    which must exist (say if $\gcd(x,y) = p$).
    Taking $s = y$ in the statement and repeating the same argument,
    we see $\half$ of the elements of $S$ are divisible by $p$.
  \end{itemize}
  So $e=1$, contradiction.
\end{proof}
Now since $|S|$ equals the number of divisors of any element of $S$, we are done.