Định lý thặng dư Trung Hoa
Định lý thặng dư Trung Hoa được coi là một trong những viên kim cương trong số học sơ cấp.
Đây có thể coi là một định lý quan trọng lý thuyết đồng dư, trong bài viết này hi vọng trao đổi cùng bạn đọc một số ứng dung của nó trong việc giải một số bài toán phổ thông.
1. Nội dung định lý và chứng minh.
Định lý thặng dư Trung Hoa được phát biểu như sau: Cho m_1,m_2,...,m_n là n số nguyên dương đôi một nguyên tố cùng nhau và a_1,a_2,...,a_n là n số nguyên bất kì. Khi đó hệ phương trình đồng dư x\equiv a_i(\text{ mod }m_i) có nghiệm và nghiệm này là duy nhất theo mod m_1m_2....,m_n.
Trước hết ta hay nhìn lại vấn đề được ra, có hai vấn đề chúng ta cần quan tâm ở đây: Thứ nhất là tính giải được của hệ phương trình đồng dư này, thứ hai là tính duy nhất của nghiệm.
Bây giờ ta hay tiếp cận bài toán, đương nhiên ta chỉ cần chứng minh cho trường hợp n=2, các trường hợp n>2 là hệ quả của trường hợp này (giải thích tại sao ?): Có rất nhiều cách chứng minh bài toán này, dưới đây là một trong những cách thông dung.
Trước hết ta sẽ chứng minh bổ đề sau:
Bổ đề Berzout: Cho hai số nguyên m và n sao cho gcd(m,n)=1. Khi đó luôn tồn tại x và y sao cho mx+ny=1.
Chứng minh: Ta xét tập {1-mx}, do m và n nguyên tố cùng nhau nên ta có {1-mx} chạy qua một hệ thặng dư đầy đủ mod n. Khi đó tồn tại số x sao cho n|1-mx, ta chỉ cần xét y=\frac{1-mx}{n}. Bổ đề Berzout được chứng minh xong.
Hệ quả: Với mọi d nguyên luôn tồn tại u và v sao cho d=mu+nv.
* Bây giờ quay lại bài toán của chúng ta, theo lý thuyết đồng dư, tồn tại u,v sao cho:
x=a_1+m_1u,x=a_2+m_2v.
Do đó ta chỉ cần chọn u và v thỏa mãn a_1-a_2=m_2v-m_1u, điều này hiển nhiên theo bổ đề Berzout ở trên. Như vậy tức là tồn tại x thỏa mãn hệ phương trình đồng dư trên. Phép chứng minh hoàn tất cho bài toán tồn tại nghiệm. Bây giờ ta sẽ chứng minh tính duy nhất của nghiệm.
Thật vậy ta hay xét hai nghiệm x và x' của hệ phương trình đã cho , khi đó ta có:
x\equiv x'(\text{ mod }m_i),\forall I=1,2,...,n.
Do m_i đôi một nguyên tố cùng nhau nên ta phải có x\equiv x'(\text{ mod }m_1m_2...m_n), ta khẳng định về tính duy nhất của nghiệm theo mod m_1...m_n. Có một số chứng minh khác cho bài toán này, tuy nhiên tác giả vẫn thích cách dung này hơn vì nó vẫn có tác dung cho định lý thặng dư Trung Hoa trong trường hợp tổng quát:
Cho m_1,...,m_n là các số nguyên dương. a_1,a_2,...,a_n là các số nguyên khi đó hệ phương trình đồng dư x\equiv a_i(\text{ mod }m_i) có nghiệm khi và chỉ khi gcd(m_i,m_j)|a_i-a_j,\forall I\ne j
Khi đó các bạn hay lien hệ với định lý Berzout ở trên để tự tìm lời giải cho mình coi như là bài tập để hiểu rõ hơn bản chat của vấn đề.
Nghiệm của phương trình đồng dư (1).
Nếu ta đặt M=\prod m_i và d_i=\frac{M}{m_i}. Hãy chứng minh rang với x=\sum\limits_{I=1}^{n}a_i(d_i)^{\phi(m_i)} thì \overline{x} là nghiệm của phương trình đồng dư đã cho.
Bây giờ ta quan tâm hơn đến việc ứng dung của định lý Trung Hoa trong lý thuyết đồng dư
Trước hết ta sẽ nêu lại một số khái niệm cơ bản.
Cho P(x) là một đa thức hệ số nguyên, việc giải phương trình đồng dư P(x)\equiv 0(\text{ mod }n) là việc tìm tất cả các lớp \overline{x} trong \mathbb{Z}_n=\left\{\overline{0},\overline{1},...\overline{n-1}\right\} mà thỏa mãn n|P(x).
Chẳng hạn xét P(x)=x^3-x, khi đó phương trình đồng dư P(x)\equiv (\text{ mod }3) có 3 nghiệm phân biệt là \overline{x}=\overline{0},\overline{1},\overline{2}.
Tuy nhiên phương trình đồng dư P(x)\equiv 0(\text{ mod }4) ta chỉ lại có 3 nghiệm \overline{x}=\overline{1},\overline{x}=overline{3},\overline{x}=\overline{0}.
Định lý sau đây cho phép ta chỉ cần quan tâm đến việc giải các phương trình đồng dư với n=p^a với p là các số nguyên tố.
Định lý 1. Cho n=\prod\limits_{I=1}^{r} p_i^{a_i}, khi đó phương trình đồng dư P(x)\equiv 0(\text{ mod }n) có nghiệm khi và chỉ khi tất cả các phương trình đồng dư P(x)\equiv 0(\text{ mod }p_i^{a_i})(*) có nghiệm. Hơn nữa nếu gọi N_i là số nghiệm của phương trình đó thì phương trình P(x)\equiv 0(\text{ mod }n) có đúng N_1...N_r nghiệm.
Chứng minh:
Chiều thuận của bài toán là hiển nhiên, bởi nếu tồn tại x mà P(x)\equiv 0(\text{ mod }n) thì hiển nhiên x sẽ thỏa mãn tất cả các phương trình đồng dư P(x)\equiv 0(\text{ mod }p _I^{a_i}).
Ta xét chiều đảo của bài toán, nhưng trước hết ta chú ý đến một tính chat đơn gain của đa thức hệ số nguyên a-b|P(a)-P(b).
Bây giờ ta tạm gọi \overline{x_{p_i}} là 1 trong các nghiệm của phương trình đồng dư (*), theo tính chat trên ta chỉ cần xét sự tồn tại của x sao cho x\equiv x_{p_i}(\text{ mod }p_i^{a_i}).
Khi đó câu trả lời là tồn tại theo định lý Trung Hoa. Với ý tưởng này câu sau thực chat là hệ quả, với mỗi cách chọn nghiệm trong N_i nghiệm của các phương trình đồng dư ở trên lại cho ta 1 nghiệm duy nhất mod n, và hiển nhiên các nghiệm này phân biệt theo mod n (giải thích tại sao ?), từ đó ta có chính xác N_1...N_r nghiệm: Phép chứng minh của ta hoàn tất. Như vậy như đã nói, việc nghiên cứu nghiệm của phương trình đồng dư mod n, có thể chuyển về nghiên cứu nghiệm trong trường hợp n là lũy thừa của số nguyên tố, và từ đó có thể chuyển về nghiển cứu nghiệm trong trường hợp n là số nguyên tố dựa theo kết quả sau:
Định lý 2. Giả sử phương trình đồng dư P(x)\equiv 0(\text{ mod }p) có k nghiệm \overline{x_1},...,\overline{x_k}đồng thời gcd(P'(x_i),p)=1 thì với mọi a nguyên dương phương trình P(x)\equiv 0(\text{ mod }p^a) cũng có đúng k nghiệm theo mod p^a. Phép chứng minh của bài toán này dựa vào hệ quả của bổ đề Helsen sau, các bạn có thể tự chứng minh coi như bài tập.
Bổ đề: Với mọi x và h luôn tôn tại r(x,h) sao cho: P(x+h)=P(x)+hP'(x)+h^2r(x,h).
Áp dung bổ đề này ta có thể chứng minh được bài toán theo quy nạp. Để hiểu rõ hơn định lý 1 ta sẽ đưa ra một ví dụ minh họa
Ví dụ 1: Cho n là số nguyên dương lớn hơn 1, hay tính số nghiệm của phương trình đồng dư x(x-1)\equiv 0(\text{ mod }n).
Lời giải: Ta viết n dưới dạng phân tích thừa số nguyên tố n=\prod\limits_{I=1}^{r}a_i. Khi đó theo định lý 1 ta sẽ quan tâm đến số nghiệm của phương trình đồng dư: x(x-1)\equiv 0(\text{ mod }_I^{a_i}), chú ý rang x và x-1 nguyên tố cùng nhau nên phương trình đồng dư này chỉ có 2 nghiệm x\equiv 0(\text{ mod }p_i^{a_i}) hoặc x\equiv 1(\text{ mod }p_i^{a_i}), từ đó theo định lý 1 phương trình này có tất cả 2^r nghiệm, bài toán được chứng minh xong.
Ví dụ 2: Cho n là số nguyên lẻ có dạng \prod\limits_{I=1}^{r} p_I^{a_i}. Khi đó xét a là số nguyên bất kì và nguyên tố cùng nhau với n thì phương trình đồng dư x^2\equiv a (\text{ mod }n) có đúng \prod\limits_{I=1}^{r}(1+{a\choose p_i}) trong đó a\choose p_i là kí hiệu Legendre.
Chứng minh: Theo tư tưởng trên ta chỉ cần quan tâm đến việc xét bài toán khi n=p^a, ta sẽ chứng minh rang với mọi k phương trình x^2\equiv a(\text{ mod }p^{k}) có đúng 1+{a \choose p} nghiệm.
Với k=1 thì kết quả của bài toán là hiển nhiên, nếu a là số chính phương mod p thì phương trình đã cho có đúng 2 nghiệm, nếu a là phi thặng dư chính phương mod p thì hiển nhiên phương trình vô nghiệm. Vậy ta có kết quả bài toán.
Bây giờ ta hay xét khi k>1, hiển nhiên ta chỉ cần quan tâm khi mà a là số chính phương mod p. Khi đó gọi x_0 là nghiệm của phương trình P(x)\equiv 0(\text{ mod }p) với P(x)=x^2-a thì ta có: P'(x_0)=2x_0 sẽ nguyên tố cùng nhau với p.
Khi p lẻ. Theo định lý (2) ta có kết quả bài toán cho trường hợp k>1. Phép chứng minh của ta hoàn tất.
Đương nhiên bài toán này vẫn có thể giải được cho trường hợp n tổng quát, tuy nhiên phép chứng minh này khá dài vì phải chia 1 số trường hợp về lũy thừa của 2, phần này Xin dành cho bạn đọc coi như là một bài tìm hiểu nhỏ. Cuối cùng để hiểu hơn ví dụ 1 và ví dụ 2 ác bạn hay thử sức vận dung để giải bài toán sau đây:
**) Ta xét S=\left\{k\in \mathbb{Z}_n|k^2\equiv 1(\text{ mod }n)\right\}. Hãy tính \prod\limits_{k\in S} k theo mod n.
***) Tổng quát của định lý Wilson: Xét T=\left\{k\in \mathbb{Z}_n | gcd(k,n)=1\right\}, hay tính \prod_{k\in T} k theo mod n.
Có một gợi ý nhỏ cho hai bài toán này để các bạn tiện theo dõi:
Đầu tiên để ý rang nếu k thuộc S thì n-k cũng thuộc S, ta có thể phân S thành các cặp số (k,n-k) vaf chú ý rang tích của các phần tử này đồng dư -1 mod n do k^2\equiv 1(\text{ mod }n). Do vậy \prod_{k\in S}k(\text{ mod }n)=(-1)^{\frac{|S|}{2}}, chúng ta quay lại ví dụ 1. Tương tự trong T ta cũng chia thành các cặp "nghịch đảo" tuy nhiên cần lưu ý một số phần tử mà nghịch đảo mod n của nó là chính nó, hay chính là thỏa mãn phương trình k^2\equiv 1(\text{ mod }n) và chúng ta phải quay lại xét tương tự ví dụ 1 với 1 chút rắc rối hơn… Ta tiếp tục với một ví dụ khá kinh điển cho ứng dung của định lý Trung Hoa.
Ví dụ 3: Cho S=\left\{p_1,p_2,...,p_r\right\} là tập r số nguyên tố phân biệt, và P là đa thức hệ số nguyên sao cho với mọi n đều tồn tại p_i trong S sao cho p_i|P(n). Chứng minh rang tồn tại i sao cho p_i|P(n),\forall n\in \mathbb{N}.
Chứng minh: Ta phản chứng điều ngược lại, tức là với mỗi p_i trong S tồn tại a_i sao cho p không là ước của P(a_i), khi đó bang phép xét x thỏa mãn hệ đồng dư x\equiv a_i(\text{ mod }p_i)
Theo định lý Trung Hoa, luôn tồn tại x thỏa mãn bài toán, ta suy ra P(x) không có ước nguyên tố trong S, và từ đó vô lý nghĩa là phải tồn tại p_i thỏa mãn bài toán, đó là điều cần chứng minh.
Bài toán tổng quát sau đây vẫn đúng nếu ta thay S bang 1 tập số nguyên dương bất kỳ, ý tưởng của bài toán hoàn toàn going lời giải ở trên nhưng cần đôi chút kĩ thuật khéo léo Xin được tiếp tục lời giải cho bạn đọc.
Ví dụ 4. Đây là một ví dụ khá điển hình cho định lý Trung Hoa. Chứng minh rang với mọi số nguyên n ta có thể chọn số nguyên lien tiếp sao cho tất cả các số đó đều là hợp số.
Gợi ý: Xét p_1,p_2,...,p_n là các số nguyên tố phân biệt sau đó xét hệ đồng dư x\equiv -k(\text{ mod }p_k^2).
Ví dụ 5: Chứng minh rang với mọi n luôn tồn tại một tập S mà |S|=n sao cho với mỗi tập con T khác rỗng của S thì \sum\limits_{x\in T}x không là lũy thừa của một số nguyên.
Lời giải: Với những dạng toán như vậy ta quan tâm nhiều đến số mũ của các thừa số nguyên tố, ta biết rang một số sẽ là lũy thừa của một số nguyên nếu như gcd\left\{v_{p_i}(n)\right\} với p_i là tập các ước nguyên tố của n. Do vậy một mẹo để giải quyết bài toán là tìm cách xác lập một ước nguyên tố của n mà số mũ của nó trong khai triển của n bang 1. Điều này gợi ý cho ta bổ đề sau:
Cho a_1,...,a_n là các số nguyên phân biệt. Khi đó tồn tại x sao cho x+a_i không là số lũy thừa với mọi i=1,2,...,n. Để chứng minh bổ đề này ta chỉ cần chọn ra n số nguyên tố phân biệt p_n>…>p_2>p_1>max(a_1,...,a_n) và xét hệ phương trình đồng dư : x\equiv p_i-a_i(\text{ mod }p_i^2). Khi đó ta có với mọi i từ 1 đến n thì v_{p_i}(x+a_i)=1 và ta có kết quả bài toán.
Quay lại ví dụ đang xét, bài toán là hệ quả của bổ đề trên thông qua phép quy nạp. Đầu tiên ta dung cho n. Sau đó chọn số x theo thuật toán trên, bổ sung x vào tập đó ta được tập n+1 phần tử. Và do đó kết thúc bài toán.
Ví dụ 6 (Thi vô địch toán Đài Loan). Ta định nghĩa một hình vuông có 4 đỉnh là các điểm nguyên, đồng thời đoạn thẳng nối tâm O với tất cả các điểm nguyên trên biên và trong hình vuông đó chứa ít nhất một điểm nguyên khác hai đầu mút. Chứng minh rang với mọi số nguyên dương n, tồn tại một hình vuông tốt dạng n*n.
Lời giải. Bài toán nêu ra vấn đề về đoạn thẳng chứa điểm nguyên, vì vậy buộc ta phải tìm hiểu về tính chat của hai điểm nguyên trên mặt phẳng tọa độ, điều kiện để đoạn thẳng đó chứa điểm nguyên khác hai đầu mút.
Bổ đề: Cho hai điểm A(a,b) và B(c,d) nguyên trên mặt phẳng tọa độ, khi đó đoạn AB chứa ít nhất 1 điểm nguyên khác A và B khi và chỉ khi gcd(a-c,b-d)>1. Phép chứng minh của bổ đề này khá đơn gain với công cụ vector.
Quay lại bài toán ta đang xét. Ta gọi đỉnh gần O nhất là (x,y). Khi đó tọa độ các điểm nguyên của hình vuông sẽ là (x+i,y+j) với I,j=0,...,n. Khi đó ta cần tìm điều kiện để cho với mọi cặp (I,j) với i,j\in \left\{0,1,2,...,n\right\} ta luôn có gcd(x+i,y+j)>1. Điều này gợi ý cho ta sử dung định lý Trung Hoa để xây dung điều kiện cho bài toán. Với mỗi cặp (I,j) ta xác định một số nguyên tố p_{ij} sao cho p_{ij} phân biệt. Từ đó ta chỉ cần xét x,y thỏa mãn hệ:
x\equiv -I(\text{ mod }p_{ij}) và y\equiv -j(\text{ mod }p_{ij}).
Theo định lý Trung Hoa hệ này có nghiệm x,y, tức là tồn tại một hình vuông n*n thỏa mãn bài toán. Bài toán được chứng minh xong.
Ví dụ 7: Cho f_1,...,f_n là n đa thức khác 0, khi đó chứng minh rang tồn tại đa thức P hệ so nguyên
sao cho với mọi i=1,2,...,n ta luôn có P+f_n là đa thức bất khả quy.
Gợi ý: Hãy sử dung tiêu chuẩn Eistein: Nếu P(x)=a_n.x^{n}+...+a_1x+a_0 là đa thức hệ số nguyên thỏa mãn, tồn tại một số nguyên p sao cho :
I) p|a_i,\forall I=2,...,n và p không là ước của a_1.
ii) p^2 không là ước của a_0
thì P(x) là đa thức bất khả quy. Từ đó xây dung một đa thức thỏa mãn hệ đồng dư phù hợp với hai điều kiện I và II.
Link:
1)https://dellday23khtn.files.wordpress.com/2010/07/nhom1_lop10_tv1.pdf
2)https://diendantoanhoc.net/topic/63807-dịnh-ly-thặng-dư-trung-hoa/
Đây có thể coi là một định lý quan trọng lý thuyết đồng dư, trong bài viết này hi vọng trao đổi cùng bạn đọc một số ứng dung của nó trong việc giải một số bài toán phổ thông.
1. Nội dung định lý và chứng minh.
Định lý thặng dư Trung Hoa được phát biểu như sau: Cho m_1,m_2,...,m_n là n số nguyên dương đôi một nguyên tố cùng nhau và a_1,a_2,...,a_n là n số nguyên bất kì. Khi đó hệ phương trình đồng dư x\equiv a_i(\text{ mod }m_i) có nghiệm và nghiệm này là duy nhất theo mod m_1m_2....,m_n.
Trước hết ta hay nhìn lại vấn đề được ra, có hai vấn đề chúng ta cần quan tâm ở đây: Thứ nhất là tính giải được của hệ phương trình đồng dư này, thứ hai là tính duy nhất của nghiệm.
Bây giờ ta hay tiếp cận bài toán, đương nhiên ta chỉ cần chứng minh cho trường hợp n=2, các trường hợp n>2 là hệ quả của trường hợp này (giải thích tại sao ?): Có rất nhiều cách chứng minh bài toán này, dưới đây là một trong những cách thông dung.
Trước hết ta sẽ chứng minh bổ đề sau:
Bổ đề Berzout: Cho hai số nguyên m và n sao cho gcd(m,n)=1. Khi đó luôn tồn tại x và y sao cho mx+ny=1.
Chứng minh: Ta xét tập {1-mx}, do m và n nguyên tố cùng nhau nên ta có {1-mx} chạy qua một hệ thặng dư đầy đủ mod n. Khi đó tồn tại số x sao cho n|1-mx, ta chỉ cần xét y=\frac{1-mx}{n}. Bổ đề Berzout được chứng minh xong.
Hệ quả: Với mọi d nguyên luôn tồn tại u và v sao cho d=mu+nv.
* Bây giờ quay lại bài toán của chúng ta, theo lý thuyết đồng dư, tồn tại u,v sao cho:
x=a_1+m_1u,x=a_2+m_2v.
Do đó ta chỉ cần chọn u và v thỏa mãn a_1-a_2=m_2v-m_1u, điều này hiển nhiên theo bổ đề Berzout ở trên. Như vậy tức là tồn tại x thỏa mãn hệ phương trình đồng dư trên. Phép chứng minh hoàn tất cho bài toán tồn tại nghiệm. Bây giờ ta sẽ chứng minh tính duy nhất của nghiệm.
Thật vậy ta hay xét hai nghiệm x và x' của hệ phương trình đã cho , khi đó ta có:
x\equiv x'(\text{ mod }m_i),\forall I=1,2,...,n.
Do m_i đôi một nguyên tố cùng nhau nên ta phải có x\equiv x'(\text{ mod }m_1m_2...m_n), ta khẳng định về tính duy nhất của nghiệm theo mod m_1...m_n. Có một số chứng minh khác cho bài toán này, tuy nhiên tác giả vẫn thích cách dung này hơn vì nó vẫn có tác dung cho định lý thặng dư Trung Hoa trong trường hợp tổng quát:
Cho m_1,...,m_n là các số nguyên dương. a_1,a_2,...,a_n là các số nguyên khi đó hệ phương trình đồng dư x\equiv a_i(\text{ mod }m_i) có nghiệm khi và chỉ khi gcd(m_i,m_j)|a_i-a_j,\forall I\ne j
Khi đó các bạn hay lien hệ với định lý Berzout ở trên để tự tìm lời giải cho mình coi như là bài tập để hiểu rõ hơn bản chat của vấn đề.
Nghiệm của phương trình đồng dư (1).
Nếu ta đặt M=\prod m_i và d_i=\frac{M}{m_i}. Hãy chứng minh rang với x=\sum\limits_{I=1}^{n}a_i(d_i)^{\phi(m_i)} thì \overline{x} là nghiệm của phương trình đồng dư đã cho.
Bây giờ ta quan tâm hơn đến việc ứng dung của định lý Trung Hoa trong lý thuyết đồng dư
Trước hết ta sẽ nêu lại một số khái niệm cơ bản.
Cho P(x) là một đa thức hệ số nguyên, việc giải phương trình đồng dư P(x)\equiv 0(\text{ mod }n) là việc tìm tất cả các lớp \overline{x} trong \mathbb{Z}_n=\left\{\overline{0},\overline{1},...\overline{n-1}\right\} mà thỏa mãn n|P(x).
Chẳng hạn xét P(x)=x^3-x, khi đó phương trình đồng dư P(x)\equiv (\text{ mod }3) có 3 nghiệm phân biệt là \overline{x}=\overline{0},\overline{1},\overline{2}.
Tuy nhiên phương trình đồng dư P(x)\equiv 0(\text{ mod }4) ta chỉ lại có 3 nghiệm \overline{x}=\overline{1},\overline{x}=overline{3},\overline{x}=\overline{0}.
Định lý sau đây cho phép ta chỉ cần quan tâm đến việc giải các phương trình đồng dư với n=p^a với p là các số nguyên tố.
Định lý 1. Cho n=\prod\limits_{I=1}^{r} p_i^{a_i}, khi đó phương trình đồng dư P(x)\equiv 0(\text{ mod }n) có nghiệm khi và chỉ khi tất cả các phương trình đồng dư P(x)\equiv 0(\text{ mod }p_i^{a_i})(*) có nghiệm. Hơn nữa nếu gọi N_i là số nghiệm của phương trình đó thì phương trình P(x)\equiv 0(\text{ mod }n) có đúng N_1...N_r nghiệm.
Chứng minh:
Chiều thuận của bài toán là hiển nhiên, bởi nếu tồn tại x mà P(x)\equiv 0(\text{ mod }n) thì hiển nhiên x sẽ thỏa mãn tất cả các phương trình đồng dư P(x)\equiv 0(\text{ mod }p _I^{a_i}).
Ta xét chiều đảo của bài toán, nhưng trước hết ta chú ý đến một tính chat đơn gain của đa thức hệ số nguyên a-b|P(a)-P(b).
Bây giờ ta tạm gọi \overline{x_{p_i}} là 1 trong các nghiệm của phương trình đồng dư (*), theo tính chat trên ta chỉ cần xét sự tồn tại của x sao cho x\equiv x_{p_i}(\text{ mod }p_i^{a_i}).
Khi đó câu trả lời là tồn tại theo định lý Trung Hoa. Với ý tưởng này câu sau thực chat là hệ quả, với mỗi cách chọn nghiệm trong N_i nghiệm của các phương trình đồng dư ở trên lại cho ta 1 nghiệm duy nhất mod n, và hiển nhiên các nghiệm này phân biệt theo mod n (giải thích tại sao ?), từ đó ta có chính xác N_1...N_r nghiệm: Phép chứng minh của ta hoàn tất. Như vậy như đã nói, việc nghiên cứu nghiệm của phương trình đồng dư mod n, có thể chuyển về nghiên cứu nghiệm trong trường hợp n là lũy thừa của số nguyên tố, và từ đó có thể chuyển về nghiển cứu nghiệm trong trường hợp n là số nguyên tố dựa theo kết quả sau:
Định lý 2. Giả sử phương trình đồng dư P(x)\equiv 0(\text{ mod }p) có k nghiệm \overline{x_1},...,\overline{x_k}đồng thời gcd(P'(x_i),p)=1 thì với mọi a nguyên dương phương trình P(x)\equiv 0(\text{ mod }p^a) cũng có đúng k nghiệm theo mod p^a. Phép chứng minh của bài toán này dựa vào hệ quả của bổ đề Helsen sau, các bạn có thể tự chứng minh coi như bài tập.
Bổ đề: Với mọi x và h luôn tôn tại r(x,h) sao cho: P(x+h)=P(x)+hP'(x)+h^2r(x,h).
Áp dung bổ đề này ta có thể chứng minh được bài toán theo quy nạp. Để hiểu rõ hơn định lý 1 ta sẽ đưa ra một ví dụ minh họa
Ví dụ 1: Cho n là số nguyên dương lớn hơn 1, hay tính số nghiệm của phương trình đồng dư x(x-1)\equiv 0(\text{ mod }n).
Lời giải: Ta viết n dưới dạng phân tích thừa số nguyên tố n=\prod\limits_{I=1}^{r}a_i. Khi đó theo định lý 1 ta sẽ quan tâm đến số nghiệm của phương trình đồng dư: x(x-1)\equiv 0(\text{ mod }_I^{a_i}), chú ý rang x và x-1 nguyên tố cùng nhau nên phương trình đồng dư này chỉ có 2 nghiệm x\equiv 0(\text{ mod }p_i^{a_i}) hoặc x\equiv 1(\text{ mod }p_i^{a_i}), từ đó theo định lý 1 phương trình này có tất cả 2^r nghiệm, bài toán được chứng minh xong.
Ví dụ 2: Cho n là số nguyên lẻ có dạng \prod\limits_{I=1}^{r} p_I^{a_i}. Khi đó xét a là số nguyên bất kì và nguyên tố cùng nhau với n thì phương trình đồng dư x^2\equiv a (\text{ mod }n) có đúng \prod\limits_{I=1}^{r}(1+{a\choose p_i}) trong đó a\choose p_i là kí hiệu Legendre.
Chứng minh: Theo tư tưởng trên ta chỉ cần quan tâm đến việc xét bài toán khi n=p^a, ta sẽ chứng minh rang với mọi k phương trình x^2\equiv a(\text{ mod }p^{k}) có đúng 1+{a \choose p} nghiệm.
Với k=1 thì kết quả của bài toán là hiển nhiên, nếu a là số chính phương mod p thì phương trình đã cho có đúng 2 nghiệm, nếu a là phi thặng dư chính phương mod p thì hiển nhiên phương trình vô nghiệm. Vậy ta có kết quả bài toán.
Bây giờ ta hay xét khi k>1, hiển nhiên ta chỉ cần quan tâm khi mà a là số chính phương mod p. Khi đó gọi x_0 là nghiệm của phương trình P(x)\equiv 0(\text{ mod }p) với P(x)=x^2-a thì ta có: P'(x_0)=2x_0 sẽ nguyên tố cùng nhau với p.
Khi p lẻ. Theo định lý (2) ta có kết quả bài toán cho trường hợp k>1. Phép chứng minh của ta hoàn tất.
Đương nhiên bài toán này vẫn có thể giải được cho trường hợp n tổng quát, tuy nhiên phép chứng minh này khá dài vì phải chia 1 số trường hợp về lũy thừa của 2, phần này Xin dành cho bạn đọc coi như là một bài tìm hiểu nhỏ. Cuối cùng để hiểu hơn ví dụ 1 và ví dụ 2 ác bạn hay thử sức vận dung để giải bài toán sau đây:
**) Ta xét S=\left\{k\in \mathbb{Z}_n|k^2\equiv 1(\text{ mod }n)\right\}. Hãy tính \prod\limits_{k\in S} k theo mod n.
***) Tổng quát của định lý Wilson: Xét T=\left\{k\in \mathbb{Z}_n | gcd(k,n)=1\right\}, hay tính \prod_{k\in T} k theo mod n.
Có một gợi ý nhỏ cho hai bài toán này để các bạn tiện theo dõi:
Đầu tiên để ý rang nếu k thuộc S thì n-k cũng thuộc S, ta có thể phân S thành các cặp số (k,n-k) vaf chú ý rang tích của các phần tử này đồng dư -1 mod n do k^2\equiv 1(\text{ mod }n). Do vậy \prod_{k\in S}k(\text{ mod }n)=(-1)^{\frac{|S|}{2}}, chúng ta quay lại ví dụ 1. Tương tự trong T ta cũng chia thành các cặp "nghịch đảo" tuy nhiên cần lưu ý một số phần tử mà nghịch đảo mod n của nó là chính nó, hay chính là thỏa mãn phương trình k^2\equiv 1(\text{ mod }n) và chúng ta phải quay lại xét tương tự ví dụ 1 với 1 chút rắc rối hơn… Ta tiếp tục với một ví dụ khá kinh điển cho ứng dung của định lý Trung Hoa.
Ví dụ 3: Cho S=\left\{p_1,p_2,...,p_r\right\} là tập r số nguyên tố phân biệt, và P là đa thức hệ số nguyên sao cho với mọi n đều tồn tại p_i trong S sao cho p_i|P(n). Chứng minh rang tồn tại i sao cho p_i|P(n),\forall n\in \mathbb{N}.
Chứng minh: Ta phản chứng điều ngược lại, tức là với mỗi p_i trong S tồn tại a_i sao cho p không là ước của P(a_i), khi đó bang phép xét x thỏa mãn hệ đồng dư x\equiv a_i(\text{ mod }p_i)
Theo định lý Trung Hoa, luôn tồn tại x thỏa mãn bài toán, ta suy ra P(x) không có ước nguyên tố trong S, và từ đó vô lý nghĩa là phải tồn tại p_i thỏa mãn bài toán, đó là điều cần chứng minh.
Bài toán tổng quát sau đây vẫn đúng nếu ta thay S bang 1 tập số nguyên dương bất kỳ, ý tưởng của bài toán hoàn toàn going lời giải ở trên nhưng cần đôi chút kĩ thuật khéo léo Xin được tiếp tục lời giải cho bạn đọc.
Ví dụ 4. Đây là một ví dụ khá điển hình cho định lý Trung Hoa. Chứng minh rang với mọi số nguyên n ta có thể chọn số nguyên lien tiếp sao cho tất cả các số đó đều là hợp số.
Gợi ý: Xét p_1,p_2,...,p_n là các số nguyên tố phân biệt sau đó xét hệ đồng dư x\equiv -k(\text{ mod }p_k^2).
Ví dụ 5: Chứng minh rang với mọi n luôn tồn tại một tập S mà |S|=n sao cho với mỗi tập con T khác rỗng của S thì \sum\limits_{x\in T}x không là lũy thừa của một số nguyên.
Lời giải: Với những dạng toán như vậy ta quan tâm nhiều đến số mũ của các thừa số nguyên tố, ta biết rang một số sẽ là lũy thừa của một số nguyên nếu như gcd\left\{v_{p_i}(n)\right\} với p_i là tập các ước nguyên tố của n. Do vậy một mẹo để giải quyết bài toán là tìm cách xác lập một ước nguyên tố của n mà số mũ của nó trong khai triển của n bang 1. Điều này gợi ý cho ta bổ đề sau:
Cho a_1,...,a_n là các số nguyên phân biệt. Khi đó tồn tại x sao cho x+a_i không là số lũy thừa với mọi i=1,2,...,n. Để chứng minh bổ đề này ta chỉ cần chọn ra n số nguyên tố phân biệt p_n>…>p_2>p_1>max(a_1,...,a_n) và xét hệ phương trình đồng dư : x\equiv p_i-a_i(\text{ mod }p_i^2). Khi đó ta có với mọi i từ 1 đến n thì v_{p_i}(x+a_i)=1 và ta có kết quả bài toán.
Quay lại ví dụ đang xét, bài toán là hệ quả của bổ đề trên thông qua phép quy nạp. Đầu tiên ta dung cho n. Sau đó chọn số x theo thuật toán trên, bổ sung x vào tập đó ta được tập n+1 phần tử. Và do đó kết thúc bài toán.
Ví dụ 6 (Thi vô địch toán Đài Loan). Ta định nghĩa một hình vuông có 4 đỉnh là các điểm nguyên, đồng thời đoạn thẳng nối tâm O với tất cả các điểm nguyên trên biên và trong hình vuông đó chứa ít nhất một điểm nguyên khác hai đầu mút. Chứng minh rang với mọi số nguyên dương n, tồn tại một hình vuông tốt dạng n*n.
Lời giải. Bài toán nêu ra vấn đề về đoạn thẳng chứa điểm nguyên, vì vậy buộc ta phải tìm hiểu về tính chat của hai điểm nguyên trên mặt phẳng tọa độ, điều kiện để đoạn thẳng đó chứa điểm nguyên khác hai đầu mút.
Bổ đề: Cho hai điểm A(a,b) và B(c,d) nguyên trên mặt phẳng tọa độ, khi đó đoạn AB chứa ít nhất 1 điểm nguyên khác A và B khi và chỉ khi gcd(a-c,b-d)>1. Phép chứng minh của bổ đề này khá đơn gain với công cụ vector.
Quay lại bài toán ta đang xét. Ta gọi đỉnh gần O nhất là (x,y). Khi đó tọa độ các điểm nguyên của hình vuông sẽ là (x+i,y+j) với I,j=0,...,n. Khi đó ta cần tìm điều kiện để cho với mọi cặp (I,j) với i,j\in \left\{0,1,2,...,n\right\} ta luôn có gcd(x+i,y+j)>1. Điều này gợi ý cho ta sử dung định lý Trung Hoa để xây dung điều kiện cho bài toán. Với mỗi cặp (I,j) ta xác định một số nguyên tố p_{ij} sao cho p_{ij} phân biệt. Từ đó ta chỉ cần xét x,y thỏa mãn hệ:
x\equiv -I(\text{ mod }p_{ij}) và y\equiv -j(\text{ mod }p_{ij}).
Theo định lý Trung Hoa hệ này có nghiệm x,y, tức là tồn tại một hình vuông n*n thỏa mãn bài toán. Bài toán được chứng minh xong.
Ví dụ 7: Cho f_1,...,f_n là n đa thức khác 0, khi đó chứng minh rang tồn tại đa thức P hệ so nguyên
sao cho với mọi i=1,2,...,n ta luôn có P+f_n là đa thức bất khả quy.
Gợi ý: Hãy sử dung tiêu chuẩn Eistein: Nếu P(x)=a_n.x^{n}+...+a_1x+a_0 là đa thức hệ số nguyên thỏa mãn, tồn tại một số nguyên p sao cho :
I) p|a_i,\forall I=2,...,n và p không là ước của a_1.
ii) p^2 không là ước của a_0
thì P(x) là đa thức bất khả quy. Từ đó xây dung một đa thức thỏa mãn hệ đồng dư phù hợp với hai điều kiện I và II.
Link:
1)https://dellday23khtn.files.wordpress.com/2010/07/nhom1_lop10_tv1.pdf
2)https://diendantoanhoc.net/topic/63807-dịnh-ly-thặng-dư-trung-hoa/
Nhận xét
Đăng nhận xét