China Mathematical Olympiad

The maximum number of elements is $72$.

A positive integer not greater than $100$ can be written as $$n=2^{a_1}\cdot 3^{a_2}\cdot 5^{a_3}\cdot 7^{a_4}\cdot 11^{a_5}\cdot q,$$ where $q$ is a positive integer and not divisible by $2$, $3$, $5$, $7$ and $11$, and $a_1,a_2,a_3,a_4$ and $a_5$ are nonnegative integers.

We pick out those positive integers $n$ with just one or two nonzero among $a_1,a_2,a_3,a_4$ and $a_5$ to form set $S$. In this case, $S$ contains $50$ even numbers ($2,4,\dots ,98$ and $100$) except the following seven: $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$ and $2\times 3\times 11$; $17$ odd numbers that are multiples of three (i.e. $3\times 1,3\times 3,\dots ,3\times 33$), $7$ odd numbers with the least prime divisor $5$ (i.e. $5\times 1,5\times 5,5\times 7,5\times 11,5\times 13,5\times 17$ and $5\times 19$), $4$ odd numbers with the least prime divisor $7$ (i.e. $7\times 1,7\times 7,7\times 11$ and $7\times 13$), and the prime number $11$.

Consequently, $S$ contains $(50-7)+17+7+4+1=72$ numbers totally.

In what follows, we will prove that $S$ constructed above satisfies the given condition.

Obviously, it satisfies condition (1).

For condition (2), we note that, at most, four prime divisors among $2,3,5,7$ and $11$ will occur in $[a,b]$. We write the prime which does not occur as $p$. Obviously, $p\in S$ and $$\begin{gathered} (p,a)\le (p,[a,b])=1, \\ (p,b)\le (p,[a,b])=1. \end{gathered}$$ Hence, we take $c=p$.

For condition (3), we take the least prime divisor of $a$ as $p$ and the one of $b$ as $q$ when $(a,b)=1$. It is easy to see that $p\ne q$ and $p,q\in \{2,3,5,7,11\}$. Hence $pq\in S$, and $$(pq,a)\ge p>1\text{ and }(pq,b)\ge q>1.$$ Being coprime to each other for $a$ and $b$ ensures that $pq$ is different from $a$ and $b$. Thus we take $d=pq$.

When $(a,b)=e>1$, we take $p$ as the least prime divisor of $e$, and $q$ as the smallest prime number satisfying $q\nmid [a,b]$. It is easy to see that $p\ne q$, and $p$ and $q\in \{2,3,5,7,11\}$. Hence $pq\in S$, and $$\begin{gathered} (pq,a)\ge (p,a)=p>1, \\ (pq,b)\ge (p,b)=p>1. \end{gathered}$$ $q\nmid [a,b]$ ensures that $pq$ is different from $a$ and $b$. Thus, we take $d=pq$.

In what follows, we prove that the number of elements in $S$, which satisfies the conditions described in the problem, will not be greater than $72$.

Obviously, $1\notin S$. For arbitrary two prime numbers $p$ and $q$ which are both greater than $10$, since the least number which is not prime to neither $p$ nor $q$ is $pq$, it must be greater than $100$. So we know, according to condition (3), that there is at most one among $21$ prime numbers between $10$ and $100$ ($11,13,\dots ,89,97$), occurring in $S$. We write the set consisting of all natural numbers not greater than $100$ except $1$ and the above-mentioned $21$ prime numbers as $T$, and there are $78$ numbers in the set. We can conclude that there are at least $7$ numbers in $T$ are not in $S$. Thus $S$ contains at most $78-7+1=72$ elements.

i. When a prime number $p$ is greater than $10$ and belongs to $S$,

every number in $S$ can only have $2,3,5,7$ and $p$ as its least prime divisor. By condition (2), we have the following conclusions.

① If $7p\in S$, because $\{2\times 3\times 5,2^2\times 3\times 5,2\times 3^2\times 5,7p\}$ contains all the least prime divisors, we know from condition (2) that $2\times 3\times 5,2^2\times 3\times 5$ and $2\times 3^2\times 5$ do not belong to $S$. If $7p\notin S$, noting $2\times 7p>100$, but $p\in S$, so from condition (2) we know that $7\times 1,7\times 7,7\times 11$ and $7\times 13$ do not belong to $S$.

② If $5p\in S$, then $2\times 3\times 7$ and $2^2\times 3\times 7$ do not belong to $S$. If $5p\notin S$, then $5\times 1$ and $5\times 5$ do not belong to $S$.

③ $2\times 5\times 7$ and $3p$ do not belong to $S$ at the same time.

④ $2\times 3p$ and $5\times 7$ do not belong to $S$ at the same time.

⑤ If $5p,7p\notin S$, then $5\times 7\notin S$.

When $p=11$ or $13$, from ①, ②, ③ and ④, we can get at least $3,2,1$ and $1$ numbers in $T$ respectively which do not belong to $S$, and in total $7$ numbers. When $p=17$ or $19$, from ①, ② and ③, we can get at least $4,2$ and $1$ numbers in $T$ respectively, which do not belong to $S$ and in total $7$ numbers. When $p>20$, from ①, ② and ③, there are at least $4,2$ and $1$ numbers in $T$ respectively, which do not belong to $S$ and in total $7$ numbers also.

ii. If there is no prime number greater than $10$ belonging to $S$, then the least prime numbers in $S$ can only be $2,3,5$ and $7$. Hence, each of the following $7$ pairs of numbers can not belong to $S$ at the same time: $$(3,2\times 5\times 7),(5,2\times 3\times 7),(7,2\times 3\times 5),(2\times 3,5\times 7),(2\times 5,3\times 7),(2\times 7,3\times 5),(2^2\times 7,3^2\times 5).$$ Thus, there are at least $7$ numbers in $T$ that are not in $S$.

Consequently, the answer for this problem is $72$.