ĐỊNH LÍ PHẦN DƯ TRUNG HOA VÀ NHỮNG ỨNG DỤNG
Phát biểu định lí : Cho $n$ số nguyên dương $m_1,m_2,...,m_n$ đôi một nguyên tố cùng nhau. Khi đó hệ đồng dư tuyến tính $\left\{\begin{matrix} x\equiv a_i\;(mod\;m_i)\\ i=\overline{1,n} \end{matrix}\right.$ có nghiệm duy nhất theo modulo $M=m_1m_2...m_n$
Định lí phần dư Trung Hoa có nhiều ứng dụng trong Lý thuyết số. Trong bài viết này, mình không đề cập đến "chức năng" đếm số nghiệm của phương trình đồng dư hay của một hệ đồng dư của định lí phần dư Trung Hoa.
Bài toán 1 (IMO 1989) : Chứng minh rằng với mọi số nguyên dương $n$ bất kì, luôn tồn tại $n$ số nguyên dương liên tiếp mà trong đó không có số nào là lũy thừa của một số nguyên tố.
Lời giải :
Xét hệ đồng dư tuyến tính :
$\left\{\begin{matrix} x\equiv -1\;(mod\;p_1p_2)\\ x\equiv -2\;(mod\;p_3p_4)\\ x\equiv -3\;(mod\;p_5p_6)\\ ...\\ x\equiv -n\;(mod\;p_{2n-1}p_{2n}) \end{matrix}\right.$
Trong đó $p_{1},p_{2},...,p_{2n}$ là các số nguyên tố phân biệt.
Dễ dàng thấy rằng theo định lí phần dư Trung Hoa, hệ này chắc chắn có nghiệm $x_0$.
Khi đó, ta có $p_1p_2\mid x_{0}+1,p_3p_4\mid x_0+2,...,p_{2n-1}p_{2n}\mid x_0+n$, như vậy dãy $x_{0}+1,x_0+2,..,x_0+n$ gồm $n$ số nguyên dương liên tiếp mà trong đó không có số nào là lũy thừa của một số nguyên tố (điều phải chứng minh)
Bài toán 2 (Đề nghị Olympic 30-4 toán 10 năm 2013 THPT Chuyên Trần Hưng Đạo, Bình Thuận) : Chứng minh rằng với mọi số nguyên dương $n$ tồn tại $n$ số nguyên dương liên tiếp sao cho bất kì số nào trong chúng cũng chia hết cho $n$ số nguyên tố liên tiếp.
Lời giải :
$\left\{\begin{matrix} x\equiv -1\;(mod\;p_1p_2...p_n)\\ x\equiv -2\;(mod\;p_{n+1}p_{n+2}...p_{2n})\\ x\equiv -3\;(mod\;p_{2n+1}p_{2n+2}...p_{3n})\\ ...\\ x\equiv -n\;(mod\;p_{n^2-n+1}p_{n^2-n+2}...p_{n^2}) \end{matrix}\right.$
Trong đó $p_{i}\in \mathbb{P},\forall i=1,2,...,n^2$ với kí hiệu $p_{i},p_{i+1}$ được coi là hai số nguyên tố liên tiếp.
Theo định lí phần dư Trung Hoa thì hệ này chắc chắn có nghiệm $x_0$, khi đó dãy $x_0+1,x_0+2,...,x_0+n$ có $n$ số nguyên dương liên tiếp mà trong đó số nào cũng chia hết cho $n$ số nguyên tố liên tiếp (điều phải chứng minh)
Bài toán 3 : Cho hai số nguyên dương $p,q$ nguyên tố cùng nhau. Chứng minh rằng tồn tại số nguyên $k$ sao cho $(pq-1)^n.k+1$ là hợp số với mọi số nguyên dương $n$.
Lời giải :
Xét hệ đồng dư $\left\{\begin{matrix} k\equiv 1\;(mod\;p)\\ k\equiv -1\;(mod\;q) \end{matrix}\right.$, do $gcd(p,q)=1$ nên theo định lí phần dư Trung Hoa thì hệ này chắc chắn có nghiệm.
Nếu $n$ chẵn thì $(pq-1)^n.k+1\equiv k+1\equiv -1+1=0\;\;(mod\;q)$, suy ra $(pq-1)^n.k+1$ là hợp số
Nếu $n$ lẻ thì $(pq-1)^n.k+1\equiv -k+1\equiv -1+1=0\;\;(mod\;p)$, suy ra $(pq-1)^n.k+1$ là hợp số.
Vậy luôn tồn tại số $k$ sao cho $(pq-1)^n.k+1$ là hợp số với mọi số nguyên dương $n$.
Bài toán 4 : Chứng minh rằng với mọi số nguyên dương $n$ luôn tồn tại một dãy gồm $n$ số nguyên liên tiếp sao cho bất kì số nào trong dãy cũng đều có ước dạng $2^k-1$.
Lời giải :
Bổ đề : Với $m,n$ là các số nguyên dương và $a$ là số nguyên dương khác $1$ thì ta có $gcd(a^m-1,a^n-1)=a^{gcd(m,n)}-1$
Chứng minh bổ đề :
Đặt $d=gcd(m,n)$ và $\left\{\begin{matrix} m=dm'\\ n=dn' \end{matrix}\right.\;\;gcd(m',n')=1$
Ta có $a^m-1=a^{dm'}-1\;\vdots \;a^d-1$ và $a^n-1=a^{dn'}-1\;\vdots \;a^d-1$
Gọi $d'=gcd(a^m-1,a^n-1)$ thì $d'\;\vdots \;a^d-1\;\;(1)$
Vì $d=gcd(m,n)$ nên theo định lí $Bezout$ thì tồn tại hai số nguyên dương $x,y$ sao cho $mx-ny=1$
Từ đó $a^{mx}-1\;\vdots \;a^{m}-1\;\vdots \;d'$ và $a^{ny}-1\;\vdots \;a^{n}-1\;\vdots \;d'$
Do đó $(a^{mx}-1)-(a^{ny}-1)\;\vdots \;d'\Rightarrow a^{ny}(a^{mx-ny}-1)\;\vdots\; d'\Rightarrow a^{ny}(a^d-1)\;\vdots \;d'$
Nhưng vì $a^{ny}-1\;\vdots d'\;\Rightarrow d'\nmid a^{ny}-1$
Nên $a^{d}-1\;\vdots \;d'\;\;(2)$
Từ $(1)(2)$ suy ra $a^d-1=d'$.
Bổ đề chứng minh hoàn tất.
Trở lại bài toán :
Xét hệ đồng dư tuyến tính :
$\left\{\begin{matrix} x\equiv -1\;\;(mod\;2^{p_1}-1)\\ x\equiv -2\;\;(mod\;2^{p_2}-1)\\ ....\\ x\equiv -n\;\;(mod\;2^{p_n}-1) \end{matrix}\right.$
Với $p_1,p_2,...,p_n$ là các số nguyên tố phân biệt
Theo bổ đề ta có $gcd(2^{p_i}-1,2^{p_j-1})=2^{gcd(p_i,p_j)}-1=2-1=1$ với mọi $i\neq j,i,j\in \left \{ 1,2,...,n \right \}$
Từ đó theo định lí phần dư Trung Hoa thì hệ này có nghiệm.
Suy ra điều cần chứng minh.
Bài toán 5 : Cho $p$ là số nguyên tố. Chứng minh rằng tồn tại một bội số của $p$ sao cho $10$ chữ số tận cùng của nó đôi một khác nhau.
Lời giải :
Nếu $p=2$ thì hiển nhiên luôn tồn tại một số thỏa đề, ví dụ $1234567899876543210$
Nếu $p=5$ thì cũng luôn tồn tại một số thỏa đề, ví dụ $1234567899876432105$
Xét $p\notin \left \{ 2,5 \right \}$.
Xét hệ đồng dư tuyến tính : $\left\{\begin{matrix} x\equiv \overline{a_0a_1a_2...a_{9}}\;(mod\;10^{10})\\ x\equiv 0\;(mod\;p) \end{matrix}\right.$ trong đó $a_i$ đôi một khác nhau và $a_{i}\in \left \{ 0,1,2,3,4,5,6,7,8,9 \right \}$.
Vì $p\in \mathbb{P},p\neq 2,p\neq 5$ nên $gcd(p,10^{10})=1$, do đó theo định lí phần dư Trung Hoa thì hệ này chắc chắn có nghiệm, nghiệm của hệ chính là số thỏa mãn đề bài.
Ta có điều phải chứng minh.
Bài toán 6 (Balkan MO 2000) Cho tập $A=\left \{ a_1,a_2,...,a_k \right \}$ với $a_i\in \mathbb{N}\;\forall i=\overline{1,k}$. Chứng minh rằng tồn tại số nguyên $n$ sao cho các phần tử của tập $B=\left \{ na_1,na_2,...,na_k \right \}$ đều là lũy thừa của một số tự nhiên với số mũ lớn hơn $1$.
Lời giải :
Xét $k$ số nguyên tố phân biệt $p_1,p_2,...,p_k$.
Xét các hệ đồng dư tuyến tính :
$\left\{\begin{matrix} x_1\equiv -1\;(mod\;p_1)\\ x_1\equiv 0\;(mod\;p_i)\;\;\forall i\in \left \{ 2,3,..,k \right \}\\\ \end{matrix}\right.$
$\left\{\begin{matrix} x_2\equiv -1\;(mod\;p_2)\\ x_2\equiv 0\;(mod\;p_i)\;\;\forall i\in \left \{ 1,3,..,k \right \}\\\ \end{matrix}\right.$
$\left\{\begin{matrix} x_3\equiv -1\;(mod\;p_3)\\ x_3\equiv 0\;(mod\;p_i)\;\;\forall i\in \left \{ 1,2,4,..,k \right \}\\\ \end{matrix}\right.$
....
$\left\{\begin{matrix} x_k\equiv -1\;(mod\;p_k)\\ x_k\equiv 0\;(mod\;p_i)\;\;\forall i\in \left \{ 1,2,3,..,k-1 \right \}\\\ \end{matrix}\right.$
Theo định lí phần dư Trung Hoa thì các hệ này đều có nghiệm.
Từ đó ta suy ra rằng $\left\{\begin{matrix} \dfrac{x_1+1}{p_1},\dfrac{x_2}{p_1},...,\dfrac{x_k}{p_1}\in \mathbb{Z}\\ \\\ \dfrac{x_2}{p_1},\dfrac{x_2+1}{p_2},...,\dfrac{x_2}{p_k}\in \mathbb{Z}\\ .\\ .\\ \dfrac{x_k}{p_1},\dfrac{x_k}{p_2},...,\dfrac{x_k+1}{p_k}\in \mathbb{Z} \end{matrix}\right.$
Khi đó chọn số $n=a_1^{x_1}a_2^{x_2}...a_k^{x_k}$ thì $na_1=a_1^{x_1+1}a_2^{x_2}...a_k^{x_k}=\left ( a_1^{\frac{x_1+1}{p_1}}a_2^{\frac{x_2}{p_1}}...a_k^{\frac{x_k}{p_1}} \right )^{p_1}$, $na_2=a_1^{x_1}a_2^{x_2+1}...a_k^{x_k}=\left ( a_1^{\frac{x_1}{p_2}}a_2^{\frac{x_2+1}{p_2}}...a_k^{\frac{x_k}{p_2}} \right )^{p_2}$, ....,$na_k=a_1^{x_1}a_2^{x_2}...a_k^{x_k+1}=\left ( a_1^{\frac{x_1}{p_k}}a_2^{\frac{x_2}{p_k}}...a_k^{\frac{x_k+1}{p_k}} \right )^{p_k}$
Điều này cho thấy các phần tử của $B$ đều là lũy thừa của một số tự nhiên.
Suy ra điều phải chứng minh.
Bài toán 7 : Chứng minh rằng với mọi số nguyên dương $n$ luôn tồn tại $n$ số nguyên $a_1,a_2,...,a_n$ sao cho $a_i+a_j$ là lũy thừa của một số tự nhiên với số mũ lớn hơn $1$ với mọi $i, j\in \left \{ 1,2,3,...,n \right \}$
Lời giải :
Ta chọn các số như sau :
$\left\{\begin{matrix} a_1=1^{x_1+1}2^{x_2}3^{x_3}...(2n)^{x_{2n}}\\ a_2=1^{x_1}2^{x_2+1}3^{x_3}...(2n)^{x_{2n}}\\ ...\\ a_n=1^{x_1}2^{x_2}3^{x_3}...(2n)^{x_{2n}+1} \end{matrix}\right.$
Khi đó thì :
$a_i+a_j=1^{x_1}2^{x_2}...i^{x_i+1}...(2n)^{x_{2n}}+1^{x_1}2^{x_2}...j^{x_j+1}...(2n)^{x_{2n}}=1^{x_1}2^{x_2}...(2n)^{x_{2n}}(i+j)=1^{x_1}2^{x_2}...(i+j)^{x_{i+j}+1}...(2n)^{x_{2n}}$
Xét các số nguyên tố $p_1,p_2,...,p_{2n}$ phân biệt
Xét các hệ đồng dư tuyến tính :
$\left\{\begin{matrix} x_1\equiv -1\;(mod\;p_1)\\ x_1\equiv 0\;(mod\;p_k)\forall k\in \left \{ 2,3,...,2n-1,2n \right \} \end{matrix}\right.$
$\left\{\begin{matrix} x_2\equiv -1\;(mod\;p_2)\\ x_2\equiv 0\;(mod\;p_k)\forall k\in \left \{ 1,3,4...,2n \right \} \end{matrix}\right.$
....
$\left\{\begin{matrix} x_{i+j}\equiv -1\;(mod\;p_{i+j})\\ x_{i+j}\equiv 0\;(mod\;p_k)\forall k\in \left \{ 1,2,...,i+j-1,i+j+1,...,2n \right \} \end{matrix}\right.$
....
$\left\{\begin{matrix} x_{2n}\equiv -1\;(mod\;p_{2n})\\ x_{2n}\equiv 0\;(mod\;p_k)\forall k\in \left \{ 1,2,...,2n-1 \right \} \end{matrix}\right.$
Theo định lí phần dư Trung Hoa thì các hệ này chắc chắn có nghiệm
Từ đó suy ra :
$\dfrac{x_1}{p_1},\dfrac{x_2}{p_2},...,\dfrac{x_k+1}{p_k},...,\dfrac{x_{2n}}{p_{2n}}\in \mathbb{Z}\;\forall k=\overline{1,2n}$
Khi đó $a_i+a_j=1^{x_1}2^{x_2}...(i+j)^{x_{i+j}+1}..(2n)^{x_{2n}}=\left [ 1^{\frac{x_1}{p_{i+j}}}.2^{\frac{x_2}{p_{i+j}}}...(i+j)^{\frac{x_{i+j}+1}{p_{i+j}}} ...(2n)^{\frac{x_{2n}}{p_{i+j}}}\right ]^{p_{i+j}}$ là lũy thừa của một số tự nhiên.
Đây là điều phải chứng minh.
Bài toán 8 : Tìm tất cả các số nguyên dương $n$ sao cho luôn tồn tại số nguyên $m$ thỏa mãn $2^n-1\mid m^2+9$.
Lời giải :
Bổ đề 1 : Một số nguyên có dạng $4k+3$ thì luôn tồn tại một ước số nguyên tố $p\equiv 3\;(mod\;4)$
Chứng minh bổ đề 1 :
Số nguyên $a$ dạng $4k+3$ là một số lẻ nên nó không có ước nguyên tố $2$.
Gỉa sử $a=p_{1}^{\alpha _1}p_{2}^{\alpha _{2}}...p_{n}^{\alpha _n}\;\;\;(p_i\in \mathbb{P},\alpha _i\in \mathbb{N}^*,i=\overline{1,n})$
Nếu $p_i\equiv 4\;(mod\;4)\;\forall i=1,2,...,n\Rightarrow a\equiv 1\;(mod\;4)$ , mâu thuẫn với giả thiết.
Do đó $a$ có ít nhất một ước nguyên tố $p\equiv 3\;(mod\;4)$
Bổ đề 2 : Nếu các số nguyên $x,y$ và số nguyên tố $p\equiv 3\;(mod\;4)$ thỏa mãn $p\mid x^2+y^2$ thì $p\mid x,p\mid y$.
Chứng minh bổ đề 2 :
Nếu $p|x$ hoặc $p|y$ thì hiển nhiên ta có điều phải chứng minh. Xét $p\nmid x,p\nmid y$
Đặt $p=4k+3\qquad(k\in \mathbb{N})$
Theo định lí $Fermat$ nhỏ : $x^{4k+2}+y^{4k+2}\equiv x^{p-1}+y^{p-1}\equiv 2\;(mod\;p)\qquad(1)$
Mặt khác $x^{2}+y^2\equiv 0\;(mod\;p)\Rightarrow x^{4k+2}+y^{4k+2}\equiv 0\;(mod\;p)\qquad(2)$
Từ $(1)(2)$ suy ra $p=2$, mâu thuẫn.
Trở lại bài toán :
Nếu $n=1$ thì hiển nhiên với mọi $m$ nguyên, bài toán đều được thỏa mãn.
Xét $n>1$. Gọi $q$ là một ước nguyên tố lẻ của $n$, khi đó $2^{q}-1\equiv 3\;(mod\;4)$ nên $2^q-1$ có ít nhất một ước nguyên tố $p\equiv 3\;(mod\;4)$. Khi đó dễ dàng thấy rằng :
$m^2+9\;\vdots \;2^{n}-1\;\vdots \;2^q-1\;\vdots\; p$
Khi đó theo bổ đề 2 ta có $p|3$,$p=3$. Suy ra $3\mid 2^{q}-1\Rightarrow 2\mid q$, điều này mâu thuẫn vì $q$ lẻ.
Như vậy $n$ không có ước nguyên tố lẻ, do đó $n=2^k\;(k\in \mathbb{N}^{*})$.
Ta sẽ chứng minh rằng với mọi $k\in \mathbb{N}^{*}$ thì $n=2^k$ luôn thỏa mãn đề bài.
Thật vậy,
Ta có $2^n-1=2^{2^{k}}-1=(2^{2^0}+1)(2^{2^1}+1)(2^{2^2}+1)...(2^{2^{t-1}}+1)$
Xét hệ đồng dư tuyến tính :
$\left\{\begin{matrix} x\equiv 0\;(mod\;2^{2^0}+1)\\ x\equiv 3.2^{2^{0}}\;(mod\;2^{2^1}+1)\\ x\equiv 3.2^{2^{1}}\;(mod\;2^{2^{2}}+1)\\ ...\\ x\equiv 3.2^{2^{k-2}}\;(mod\;2^{2^{k-1}}+1) \end{matrix}\right.$
Dễ thấy rằng $gcd(2^{2^i}+1,2^{2^j}+1)=1\;\forall i\neq ,j,i,j\in \left \{ 0,1,2,...,k-1 \right \}$ vì chúng là các số $Fermat$.
Theo định lí phần dư Trung Hoa thì hệ này chắc chắn có nghiệm $x_0$.
Ta suy ra
$\left\{\begin{matrix} x_{0}^{2}\equiv 0\equiv -9\;(mod\;2^{2^0}+1)\\ x_0^2\equiv 9.2^{2^{1}}\equiv -9\;(mod\;2^{2^1}+1)\\ x_0^2\equiv 9.2^{2^2}\equiv -9\;(mod\;2^{2^2}+1)\\ ...\\ x_0^2\equiv 9.2^{2^{k-1}}\equiv -9\;(mod\;2^{2^{k-1}}+1) \end{matrix}\right.\Rightarrow x_0^2+9\equiv 0\;(mod\;2^n-1)$
Khi đó với mọi $n=2^k$ thì luôn tồn tại số nguyên $m=x_0$ là nghiệm của hệ trên thỏa mãn đề bài.
Kết luận : $\boxed{n=2^k\;\;(k\in \mathbb{N})}$
Xin kết thúc bài viết, chúc mọi người một năm mới thật hạnh phúc, vui vẻ và gặt hái nhiều thành công trong học tập.
Bài viết đã được chỉnh sửa nội dung bởi Juliel: 01-01-2014 - 14:00