Phân hoạch \(100\) số tự nhiên đầu tiên thành các tập hợp sau:
\(A_1=\left\{1\right\}\)
\(A_2=\left\{2;4;6;8;...;100\right\}\)
\(A_3=\left\{3;9;15;...;99\right\}\)
\(A_5=\left\{5;25;35;55;...;95\right\}\)
Nghĩa là \(A_i\) với \(i\) nguyên tố chứa các bội của \(i\) mà không chia hết cho số nào nhỏ hơn \(i\) trừ số \(1\).
Giả sử có 27 số mà trong chúng không có ước chung lớn nhất khác 1.
Với mọi \(i\), trong mỗi \(A_i\) ta chỉ chọn được tối đa một số, vì nếu chọn 2 số thì chúng có ước chung là \(i\).
Có 25 số nguyên tố nhỏ hơn 100, tương ứng trong 25 \(A_i\) chỉ chọn được 25 số là tối đa.
Chọn thêm số 1 thì tối đa chọn được 26 số sao cho không có ước chung lớn nhất khác 1.
Nên nếu chọn 27 số thì trong chúng có ước chung lớn nhất khác 1.
