Cho số nguyên dương $n$ và tập hợp $A$ gồm $60n+1$ số nguyên dương không vượt quá $210n$ và nguyên tố cùng nhau với 14. Chứng minh rằng trong $A$ luôn tồn tại hai số mà một số chia hết cho ba lần số còn lại.

Nhận xét: Với mọi $x\in {\mathbb{N}}^{\ast }$, ta luôn viết được dưới dạng $x=3^k\cdot m$ (trong đó $k\in \mathbb{N}$, $m\in {\mathbb{N}}^{\ast }$ và $\gcd (m,3)=1$).

Ta gọi nhóm các số có cùng giá trị $m$: $\{m,3m,9m,27m,\dots \}$ là một chuỗi.

Dễ dàng thấy rằng với 2 số bất kỳ trong cùng một chuỗi thì luôn có 1 số chia hết cho 3 lần số còn lại.

Số lượng chuỗi chính là số lượng các số đại diện $m\le 210n$ thỏa mãn:

$$\{\begin{array}{l}\gcd (m,14)=1\\ \gcd (m,3)=1\end{array}⟹\gcd (m,42)=1$$

Áp dụng công thức phi hàm Euler, số lượng các số $m$ thỏa mãn trên đoạn $[1,210n]$ là:

$$210n\cdot \left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\left(1-\frac{1}{7}\right)=210n\cdot \frac{1}{2}\cdot \frac{2}{3}\cdot \frac{6}{7}=60n$$

Vậy có tất cả $60n$ chuỗi. Mà tập hợp $A$ gồm có $60n+1$ phần tử.

Theo nguyên lý Dirichlet, tồn tại ít nhất 1 chuỗi chứa từ 2 phần tử trở lên thuộc tập $A$.

Từ đó, ta có điều phải chứng minh (đpcm).