Phan Đình Trung: Định lí thặng dư Trung Hoa và ứng dụng

Bài toán 1 : Chứng minh rằng với mọi số nguyên dương $n$ , luôn tồn tại một tập hợp $S$ gồm $n$ phần tử sao cho bất kì một tập con nào của $S$ cũng có tổng các phần tử là lũy thừa của một số tự nhiên.

Lời giải :

Gỉa sử rằng :

$S=\left \{ a_1,a_2,...,a_{n-1},a_n \right \}$

Ta chọn các số $a_i$ như sau :

$a_1=1^{b_1+1}2^{b_2}3^{b_3}...k^{b_k}$

$a_2=1^{b_1}2^{b_2+1}3^{b_3}...k^{b_k}$

$...$

$a_i=1^{b_1}2^{b_2}...(i-1)^{b_{i-1}}.i^{b_i+1}.(i+1)^{b_{i+1}}...k^{b_k}$

$...$

$a_n=1^{b_1}2^{b_2}3^{b_3}...n^{b_n+1}...k^{b_k}$

Trong đó $k$ là số nguyên dương thỏa mãn $k>1+2+3+...+n$ .

Gỉa sử $T=\left \{ a_{i_1},a_{i_2},...a_{i_m} \right \}\subset S$ $(m<n)$ .

Khi đó ta có :

$a_{i_1}+a_{i_2}+...+a_{i_m}=1^{b_1}2^{b_2}...i_1^{b_{i_1}+1}...k^{b_k}+1^{b_1}2^{b_2}...i_2^{b_{i_2}+1}...k^{b_k}+...+1^{b_1}2^{b_2}...i_m^{b_{i_m}+1}...k^{b_k}=1^{b_1}2^{b_2}...k^{b_k}(i_1+i_2+...+i_m)=1^{b_1}2^{b_2}...(i_1+i_2+...+i_m)^{b_{i_1+i_2+...+i_m}}...k^{b_k}$

Ta sẽ chọn ra $k$ số nguyên tố phân biệt $p_1,p_2,...,p_k$ thỏa mãn hệ sau :

$p_1\mid b_1+1,p_1\mid b_2,b_3,...b_k$

$p_2\mid b_2+1,p_2\mid b_1,b_3,...b_k$

$...$

$p_k\mid b_k+1,p_k\mid b_1,b_2,...,b_{k-1}$ .

Hiển nhiên chọn được theo định lí phần dư Trung Hoa, khi đó dễ thấy :

$a_{i_1}+a_{i_2}+...+a_{i_m}=A^{p_{i_1+i_2+..+i_m}}$

Là lũy thừa của một số tự nhiên. Trong đó :

$A=1^{b_1/p_{i_1+i_2+..+i_m}}.2^{b_2/p_{i_1+i_2+...+i_m}}....(i_1+i_2+...+i_m)^{b_{i_1+i_2+...+i_m}/p_{i_1+i_2+...+i_m}}...k^{b_k/p_{i_1+i_2+...+i_m}}$

và hiển nhiên $A$ nguyên

Bài toán được giải quyết trọn vẹn.

Bài toán 2 : Chứng minh rằng nếu $p_1,p_2,....,p_n$ là các số nguyên tố phân biệt thì phương trình $x_1^{p_1}+x_2^{p_2}+....+x_{n-1}^{p_{n-1}}=x_n^{p_n}$ có vô số nghiệm nguyên dương $(x_1,x_2,....,x_n)$

Lời giải :

Ta có đẳng thức hiển nhiên sau : $\underset{n-1}{\underbrace{(n-1)^k+(n-1)^k+....+(n-1)^k}}=(n-1)^{k+1}$

Khi đó ta chọn $x_1=(n-1)^{\frac{k}{p_1}},x_2=(n-1)^{\frac{k}{p_2}},...,x_{n-1}=(n-1)^{\frac{k}{p_{n-1}}},x_n=(n-1)^{\frac{k+1}{p_n}}$

Thì ta thu được ngay phương trình $x_1^{p_1}+x_2^{p_2}+....+x_{n-1}^{p_{n-1}}=x_n^{p_n}$

Vậy nếu ta chỉ ra được số nguyên dương $k$ sao cho $x_1,x_2,...,x_n$ đều nguyên thì ta có ngay điều phải chứng minh.

Mà điều này tương đương với hệ sau có nghiệm : $\left\{\begin{matrix} k\equiv 0\;(mod\;p_1)\\ k\equiv 0\;(mod\;p_2)\\ ....\\ k\equiv 0\;(mod\;p_{n-1})\\ k\equiv -1\;(mod\;p_n) \end{matrix}\right.$

Điều này luôn đúng theo định lí phần dư Trung Hoa vì $p_1,p_2,...,p_n$ là các số nguyên tố phân biệt.

Bài toán 3 : 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 4 : 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}...n^{x_n+1}..(2n)^{x_{2n}} \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 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 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 : 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ố.

Kết luận : 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 8:

a) 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ố.

b) 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 :

a) 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) Xét hệ đồng dư tuyến tính :

$\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 9 : 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\;(t\in \mathbb{N}^{*})$ .

Ta sẽ chứng minh rằng với mọi $t\in \mathbb{N}^{*}$ thì $n=2^t$ 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)$