Bài toán [Hệ đồng dư, số square-free]

Bài toán : Một số nguyên được gọi là số $square-free$ nếu nó là tích của các số nguyên tố phân biệt. Chứng minh rằng với mọi số nguyên dương $k$, luôn tồn tại $k$ số nguyên liên tiếp mà không có số nào là số $quare-free$.

Lời giải :

Ta xét hệ đồng dư tuyến tính :

$$\{\begin{array}{c}x=-1(mod{p}_1^2)\\ x\equiv -2(mod{p}_2^2)\\ x\equiv -3(mod{p}_3^2)\\ ...\\ x\equiv -k(mod{p}_k^2)\end{array}$$

Với $p_i\in \mathbb{P}\forall i=\overline{1,k}$

Theo định lí thặng dư Trung Hoa, thì hệ này luôn có nghiệm.

Gọi $x_0$ là một nghiệm của hệ, khi đó ta có :

$p_1^2|x_0+1\Rightarrow x_0+1$ không là số $square-free$

$p_2^2|x_0+2\Rightarrow x_0+2$ không là số $square-free$

…

$p_k^2|x_0+k\Rightarrow x_0+k$ không là số $quare-free$

Khi đó $k$ số nguyên liên tiếp $x_0+1,x_0+2,...,x_0+k$ thỏa mãn không có số nào là số $square-free$ (điều phải chứng minh)