MathDB
Subset of Some Integers

Source: China TST 2004 Quiz

February 1, 2009
number theory unsolvednumber theory

Problem Statement

S S is a non-empty subset of the set {1,2,⋯ ,108} \{ 1, 2, \cdots, 108 \}, satisfying: (1) For any two numbers a,b∈S a,b \in S ( may not distinct), there exists c∈S c \in S, such that \gcd(a,c)\equal{}\gcd(b,c)\equal{}1. (2) For any two numbers a,b∈S a,b \in S ( may not distinct), there exists c′∈S c' \in S, c′≠a c' \neq a, c′≠b c' \neq b, such that gcd⁡(a,c′)>1 \gcd(a, c') > 1, gcd⁡(b,c′)>1 \gcd(b,c') >1. Find the largest possible value of ∣S∣ |S|.
Back to ProblemsView on AoPS