Problem

Source: China TST 2004 Quiz

Tags: number theory unsolved, number theory



$ S$ is a non-empty subset of the set $ \{ 1, 2, \cdots, 108 \}$, satisfying: (1) For any two numbers $ a,b \in S$ ( may not distinct), there exists $ c \in S$, such that $ \gcd(a,c)=\gcd(b,c)=1$. (2) For any two numbers $ a,b \in S$ ( may not distinct), there exists $ c' \in S$, $ c' \neq a$, $ c' \neq b$, such that $ \gcd(a, c') > 1$, $ \gcd(b,c') >1$. Find the largest possible value of $ |S|$.