Đến nội dung

Hình ảnh

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


  • Please log in to reply
Chủ đề này có 7 trả lời

#1
Juliel

Juliel

    Thượng úy

  • Thành viên
  • 1240 Bài viết

                 ĐỊ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

Đừng rời xa tôi vì tôi lỡ yêu người mất rồi !
 

Welcome to My Facebook !


#2
cong9002

cong9002

    Lính mới

  • Thành viên
  • 1 Bài viết

Bài viết hay quá! Thầy cho em xin thêm một ít tài liệu liên quan đến bài tập ứng dụng định lý Trung hoa với! Cảm ơn thầy rất nhiều!

Mail của em: [email protected]



#3
Juliel

Juliel

    Thượng úy

  • Thành viên
  • 1240 Bài viết

Bài viết hay quá! Thầy cho em xin thêm một ít tài liệu liên quan đến bài tập ứng dụng định lý Trung hoa với! Cảm ơn thầy rất nhiều!

Mail của em: [email protected]

Mình chỉ là học sinh lớp 10 thôi, đâu phải thầy cô giáo nào đâu @@.


Đừng rời xa tôi vì tôi lỡ yêu người mất rồi !
 

Welcome to My Facebook !


#4
inuyasha98

inuyasha98

    Binh nhì

  • Thành viên
  • 18 Bài viết

Bạn ơi, cho mình hỏi bài này với :wacko: : 

     Cho hai số nguyên dương a, b thỏa mãn: $a^{n}+n\vdots b^{n}+n \forall n\in N^{*}$. 

CMR: a=b


Bài viết đã được chỉnh sửa nội dung bởi inuyasha98: 14-03-2014 - 19:17


#5
zipienie

zipienie

    Thiếu úy

  • Thành viên
  • 533 Bài viết

Một tài liệu về Định lý thặng dư Trung Hoa

 

 

File gửi kèm


Luận văn, tài liệu tham khảo toán học : http://diendantoanho...ảo/#entry499457

Sách, Luận Văn, Tài liệu tham khảo https://www.facebook...TailieuLuanvan/

#6
tthandb

tthandb

    Binh nhất

  • Thành viên
  • 37 Bài viết

Nói thật là phần này khó hiểu quá  :(  :(  :(


"Chúng ta bên nhau như một gia đình chỉ trong cuộc đời này thôi, dù bạn thích hay không. Vì thế, hãy trân trọng và nâng niu khi chúng ta bên nhau, chia sẻ, gắn bó. Dù muốn hay không, chúng ta sẽ không thể gặp nhau ở kiếp sau..."


#7
nhungvienkimcuong

nhungvienkimcuong

    Thiếu úy

  • Hiệp sỹ
  • 675 Bài viết

Bạn ơi, cho mình hỏi bài này với :wacko: : 

     Cho hai số nguyên dương a, b thỏa mãn: $a^{n}+n\vdots b^{n}+n \forall n\in N^{*}$. 

CMR: a=b

giả sử $a\neq b$ thì từ giả thiết ta có $a>b$

chọn $p$ là số nguyên tố lớn hơn $a$ và chọn $n=(b+1)(p-1)+1$

$\Rightarrow \left\{\begin{matrix} n\equiv 1(mod\ p-1)\\n\equiv -b(mod\ p) \end{matrix}\right.$

ta có

$r^n=r.\left ( r^{p-1} \right )^{b+1}\equiv r(mod\ p)\ \ \ \forall r\in \mathbb{N}^*,r<p$   $(*)$

do đó ta có

$b^n+n\equiv b-b\equiv 0(mod\ p)\Rightarrow p\mid b^n+n\Rightarrow p\mid a^n+n$

mặt khác

$\overset{(*)}{\Rightarrow}a^n+n\equiv a-b(mod\ p)\Rightarrow p\mid a-b$

điều trên vô lí do đó $\boxed{a=b}$

Spoiler


Đừng khóc vì chuyện đã kết thúc hãy cười vì chuyện đã xảy ra ~O) 
Thật kì lạ anh không thể nhớ đến tên mình mà chỉ nhớ đến tên em :wub:
Chúa tạo ra vũ trụ của con người còn em tạo ra vũ trụ của anh :ukliam2:


#8
dntp9703

dntp9703

    Lính mới

  • Thành viên mới
  • 1 Bài viết

:ukliam2: Bài đăng lâu rồi nhỉ

:nav: #relax






2 người đang xem chủ đề

0 thành viên, 2 khách, 0 thành viên ẩn danh