Problem

Source: 2020 China North Mathematical Olympiad Basic level P5

Tags: number theory, relatively prime, combinatorics, Sets



It is known that subsets $A_1,A_2, \cdots , A_n$ of set $I=\{1,2,\cdots ,101\}$ satisfy the following condition $$\text{For any } i,j \text{ } (1 \leq i < j \leq n) \text{, there exists } a,b \in A_i \cap A_j \text{ so that } (a,b)=1$$Determine the maximum positive integer $n$. *$(a,b)$ means $\gcd (a,b)$