Category Archives: Định lí phần dư Trung Hoa và ứng dụng

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

By

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 :

\left\{\begin{matrix} 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{matrix}\right.

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)