Problem 1650

5. The maximum possible number of elements in $S$ is 76. Let $|S| \geqslant 3, p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} p_{3}^{\alpha_{3}} \in S, p_{1}, p_{2}, p_{3}$ be three different primes, $p_{1}1, (c_{3}, c_{2})>1$. From $(c_{1}, c_{2})=1$ we know the product of the smallest prime factors of $c_{1}$ and $c_{2}$ is $\leqslant c_{3} \leqslant 108$. Thus, $q \mid c_{1}$. From $(c_{2}, c_{1})=1, (c_{2}, p_{1}^{q_{1}} p_{2}^{\sigma_{2}} p_{3}^{\sigma_{3}})=1, \{p_{1}, p_{2}, p_{3}, q\}=\{2,3,5,7\}, c_{2} \leqslant 108$ we know $c_{2}$ is a prime greater than 10. From $(c_{3}, c_{2})>1$ we know $c_{2} \mid c_{3}$. Also, $11, (c_{5}, c_{4})>1$. So $c_{2} \mid c_{5}, c_{4} \mid c_{5}$. From $c_{2} \mid c_{3}, (c_{4}, c_{3})=1$ we know $(c_{2}, c_{4})=1$. Thus, $c_{2} c_{4} \mid c_{5}$. But $c_{2} c_{4} \geqslant 11 \times 13 > 108$, a contradiction. Let $S_{1}=\{1,2, \cdots, 108\} \backslash (\{1\}$ and primes greater than 11 $\} \cup \{2 \times 3 \times 11, 2 \times 3 \times 5, 2^{2} \times 3 \times 5, 2 \times 3^{2} \times 5, 2 \times 3 \times 7, 2^{2} \times 3 \times 7, 2 \times 5 \times 7, 3 \times 5 \times 7\})$. Then $|S_{1}|=76$. We now prove that $S_{1}$ satisfies (i) and (ii). If $p_{1}^{a_{1}} p_{2}^{\sigma_{2}} p_{3}^{\sigma_{3}} \in S_{1}, p_{1}1$, $(2 q_{1}, b)>1$; if $b \neq 3 q_{1}$, then $3 q_{1} \in S_{1}, (3 q_{1}, a)>1$, $(3 q_{1}, b)>1$. (2) $a=2 \times 3 \times 17, b \neq a$, then (1) can be proven. (3) $a=b$, since at least one of $5, 7, 11$ does not divide $a$, (i) holds. If $a$ is composite, take the smallest prime factor $p$ of $a$, then $p \in S_{1}, (p, a)>1$; if $a$ is prime, then $a \leqslant 11, 2a \in S_{1}, (2a, a)>1$. (4) $a, b$ are two different numbers in $S_{1}$, $a, b$ each contain at most two different prime factors, $a1, (b, r_{1})>1$; if $r_{1}=r_{2}=a$, then take $u=2$ or 3, such that $b \neq u a$. Then $u a \in S, (u a, a)>1$, $(u a, b)>1$; if $r_{1} r_{2} \neq a, r_{1} r_{2} \neq b$, then $r_{1} r_{2} \in S_{1}, (r_{1} r_{2}, a)>1, (r_{1} r_{2}, b)>1$; if $r_{1} r_{2}=a$, then $r_{1}1, (u r_{2}, b)>1$; if $r_{1} r_{2}=b$, then take $v=2, 3, 5$, such that $a \neq v r_{1}, b \neq v r_{1}$, then $v r_{1} \in S_{1}, (v r_{1}, a)>1, (v r_{1}, b)>1$. We have proven that $S_{i}$ satisfies (i) and (ii). On the other hand, it is clear that $2 \times 3 \times 5$, $2^{2} \times 3 \times 5$, $2 \times 3^{2} \times 5$, $2 \times 3 \times 7$, $2^{2} \times 3 \times 7$, $2 \times 5 \times 7$, $3 \times 5 \times 7$ do not belong to $S$. Now we prove that $2 \times 3 \times 11$, $2 \times 3 \times 13$, $5 \times 7$ do not all belong to $S$. Assume the contrary, that all three numbers belong to $S$. From (i) there exist $d_{1}, d_{2} \in S$ such that $(2 \times 3 \times 11, d_{1})=1, (5 \times 7, d_{1})=1, (2 \times 3 \times 13, d_{2})=1, (5 \times 7, d_{2})=1$. Therefore, $d_{1}, d_{2}$ are both primes greater than 10. From (ii) we know $d_{1}=d_{2} \geqslant 17$. From (ii) there exists $d_{3} \in S$ such that $(7, d_{3})>1, (d_{2}, d_{3})>1$. Therefore, $7 d_{2} \mid d_{3}$. But $7 d_{2} \geqslant 7 \times 17=119$, a contradiction. On the other hand, among the primes greater than 10, at most one belongs to $S$, $1 \notin S$, thus $|S| \leqslant 108-7-1-23-1=76$.