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

Number Theory

By

Bài toán : 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] Phương trình nghiệm nguyên, Định lí phần dư Trung Hoa

By

Bài toán : 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] Ứng dụng định lí phần dư Trung Hoa

By

Bài toán : 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] Ứng dụng định lí phần dư Trung Hoa

By

Bài toán : 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] Ứng dụng định lí phần dư Trung Hoa

By

Bài toán : 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] Ứng dụng định lí phần dư Trung Hoa

By

Bài toán  (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] Ứng dụng định lí phần dư Trung Hoa

By

Bài toán : 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] Định lí phần dư Trung Hoa

By

Bài toán :

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] Tính chất số nguyên tố 4k+3, phần dư Trung Hoa

By

Bài toán : 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)

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})}