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