[Qn2009.4]: Số học của Z/pZ


Mục đích của bài này là giới thiệu một trường số khác, trường có p phần tử, khác với các trường số mà các học sinh đã biết là trường các số hữu tỷ, số thực, số phức, kí hiệu của chúng là \mathbb{Q},\mathbb{R}\mathbb{C}. Sau khi làm quen với trường số này, chúng ta sẽ giải một vài bài toán số học sơ cấp bằng cách dùng các phép toán trong \mathbb{Z}/p\mathbb{Z}, đương nhiên là các bài toán này có thể giải theo cách thông thường, nhưng cồng kềnh và giả tạo hơn nhiều. Khi chuẩn bị bài giảng này tôi giả sử rằng học sinh đã có các kiến thức cơ bản về Lý thuyết số, ví dụ như đồng dư, định lý Fermat bé, luật tương hỗ,…Sau đây, nếu không nói gì thêm thì p luôn được hiểu là một số nguyên tố.

Với mỗi số nguyên a ta ký hiệu \bar{a} là tập hợp \{b\in\mathbb{Z}|b\equiv a\pmod{p}\}\mathbb{Z}/p\mathbb{Z} là tập \{\bar{a}|a\in\mathbb{Z}\}. Như thế nếu ab là các số nguyên thoả mãn a\equiv b\pmod{p} thì \bar{a}=\bar{b}(ngược lại cũng đúng) và |\mathbb{Z}/p\mathbb{Z}|=p, cụ thể là \mathbb{Z}/p\mathbb{Z}=\{\bar{0},\bar{1},\cdots,\overline{p-1}\}, hơn nữa ta còn thấy rằng \mathbb{Z}/p\mathbb{Z} là một phân hoạch của \mathbb{Z}. Gìơ là lúc chúng ta trang bị cho \mathbb{Z}/p\mathbb{Z} hai phép toán mà nó cùng với hai phép toán này lập thành một trường (đương nhiên tôi hiểu rằng học sinh phổ thông chưa biết trường là gì, nhưng qua \mathbb{Q},\mathbb{R},\mathbb{C} các em sẽ thấy sự tương tự ở đây). Tổng của hai tập \bar{a}\bar{b}, ký hiệu là \bar{a}+\bar{b} sẽ là tập \overline{a+b}, và tích của hai tập đó, ký hiệu là \bar{a}\cdot\bar{b} sẽ là tập \overline{ab}(chú ý rằng cùng các dấu +,. nhưng ý nghĩa của nó ở trên lại hoàn toàn khác nhau). Bởi các tính chất cơ bản của đồng dư ta thấy việc định nghĩa như trên là thoả đáng, và các phép toán đó có các tính chất sau đây, các bạn đồng nghiệp sẽ thấy rằng đấy chính là các tiên đề của trường.

(1)(\bar{a}+\bar{b})+\bar{c}=\bar{a}+(\bar{b}+\bar{c})\forall \bar{a},\bar{b},\bar{c}\in\mathbb{Z}/p\mathbb{Z};
(2)\bar{a}+\bar{b}=\bar{b}+\bar{a}\forall \bar{a},\bar{b}\in\mathbb{Z}/p\mathbb{Z};
(3)\bar{a}+\bar{0}=\bar{0}+\bar{a}=\bar{a}\forall \bar{a}\in\mathbb{Z}/p\mathbb{Z};
(4)Với mỗi \bar{a} thuộc \mathbb{Z}/p\mathbb{Z}, tồn tại duy nhất \bar{b} thuộc \mathbb{Z}/p\mathbb{Z} sao cho \bar{a}+\bar{b}=\bar{b}+\bar{a}=\bar{0}.  Phần tử duy nhất này chúng ta sẽ kí hiệu bởi -\bar{a}, và gọi là phần tử đối của \bar{a} thấy ngay là -\bar{a}=\overline{-a}. Và ta có thể định nghĩa hiệu của hai lớp như là \bar{a}-\bar{b}:=\bar{a}+(-\bar{b});
(5)(\bar{a}\cdot\bar{b})\cdot\bar{c}=\bar{a}\cdot(\bar{b}\cdot\bar{c})\forall \bar{a},\bar{b},\bar{c}\in\mathbb{Z}/p\mathbb{Z};
(6)\bar{a}\cdot\bar{b}=\bar{b}\cdot\bar{a}\forall \bar{a},\bar{b}\in\mathbb{Z}/p\mathbb{Z};
(7)\bar{a}\cdot\bar{1}=\bar{1}\cdot\bar{a}=\bar{a}\forall \bar{a}\in\mathbb{Z}/p\mathbb{Z};
(8)Với mỗi \bar{a}\not =\bar{0} thuộc \mathbb{Z}/p\mathbb{Z}, tồn tại duy nhất \bar{b} thuộc \mathbb{Z}/p\mathbb{Z} sao cho \bar{a}\cdot\bar{b}=\bar{b}\cdot \bar{a}=\bar{1}. Phần tử duy nhất này chúng ta sẽ kí hiệu bởi \bar{a}^{-1}, và gọi là phần tử nghịch đảo của \bar{a}. Và khi đó ta có thể định nghĩa thương của hai lớp như là \dfrac{\bar{a}}{\bar{b}}:=\bar{a}\cdot \bar{b}^{-1};
(9)\bar{a}\cdot (\bar{b}+\bar{c})=\bar{a}\cdot\bar{b}+\bar{a}\cdot\bar{c}\forall \bar{a},\bar{b},\bar{c}\in\mathbb{Z}/p\mathbb{Z}.

Ta có thể định nghĩa \mathbb{Z}/n\mathbb{Z} với n không phải là số nguyên tố bằng cách tương tự như trên, tất cả các tính chất vẫn còn đúng trừ tính tồn tại phần tử nghịch đảo của phép nhân.

Bài 1. Chứng minh rằng phương trình x^2+y^2=3z^2 có nghiệm nguyên duy nhất là (0,0,0).
Lời giải và bình luận. Kiểm tra thấy (0,0,0) là một nghiệm nguyên của phương trình. Gỉa sử (x,y,z) là nghiệm nguyên của phương trình mà x,y,z không đồng thời bằng 0, do hai vế là đẳng cấp cùng bậc nên không giảm tổng quát ta có thể giả sử \gcd (x,y,z)=1. Trong \mathbb{Z}/4\mathbb{Z} ta có \bar{x}^2+\bar{y}^2=3\bar{z}^2, nhưng \bar{a}^2\in \{\bar{0},\bar{1}\}\forall\bar{a}\in\mathbb{Z}/4\mathbb{Z} nên ta phải có \bar{x}^2=\bar{y}^2=\bar{z}^2=\bar{0}, suy ra cả ba số x,y,z phải là bội của 2, điều này là không thể và dó đó bài toán được giải.
Rõ ràng là việc chuyển một phương trình trên \mathbb{Z} (là tập vô hạn) sang một phương trình trên \mathbb{Z}/n\mathbb{Z} (một tập hữu hạn) theo một nghĩa nào đó là đơn giản hơn. Không may, có những phương trình có nghiệm không tầm thường trên \mathbb{Z}/n\mathbb{Z} với mỗi số nguyên dương n nhưng lại không có nghiệm không tầm thường trên \mathbb{Z}, ví dụ 3x^3+4y^3+5z^3=0. Chứng minh kết quả này không dễ và nó vượt quá khuôn khổ của bài giảng này.

Bài 2. Cho p là một số nguyên tố lẻ. Chứng minh rằng khi viết số hữu tỉ \dfrac{1}{1}+\dfrac{1}{2}+\cdots+\dfrac{1}{p-1} dưới dạng phân số tối giản thì tử số của nó chia hết cho p.
Lời giải và bình luận. Trong \mathbb{Z}/p\mathbb{Z} ta có \bar{1}^{-1}+\bar{2}^{-1}+\cdots+\overline{p-1}^{-1}=\overline{1}+\overline{2}+\cdots+\overline{p-1}=\overline{1+2+\cdots+(p-1)}=

\overline{(\dfrac{(p-1)p}{2})}=\overline{0}. Do đó ta có điều phải chứng minh. Tính toán thật là thuận lợi!

Bài 3(Định lý Lagrange). Cho p là một số nguyên tố và f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0 là một đa thức với hệ số nguyên có bậc n>0. Chứng minh rằng nếu a_n không chia hết cho p thì đồng dư f(x)\equiv 0\pmod{p} có nhiều nhất n nghiệm phân biệt modulo p.
Lời giải và bình luận. Trong dạng khác, bài toán trên có dạng: Cho f(x)\in\mathbb{Z}/p\mathbb{Z}[x] có bậc n>0 thì f(x) có nhiều nhất n nghiệm trong \mathbb{Z}/p\mathbb{Z}. Rõ ràng đây là kết quả tương tự như trong \mathbb{Q}[x],\mathbb{R}[x]\mathbb{C}[x] mà các bạn đã biết. Bởi vậy tôi để lại chứng minh cho các bạn.

Bài 4. Cho p là một số nguyên tố và f(x)=\sum_{i=0}^{n}a_ix^i là một đa thức với hệ số nguyên. Nếu đồng dư f(x)\equiv 0\pmod{p} có nhiều hơn n nghiệm phân biệt modulo p thì tất cả các hệ số của f(x) phải chia hết cho p.
Lời giải và bình luận. Bài toán này được suy ra ngay lập tức từ bài toán trước. Kết quả tương tự trong \mathbb{Q}[x],\mathbb{R}[x]\mathbb{C}[x] được áp dụng rộng rãi trong Đại số nên đương nhiên kết quả này sẽ được áp dụng rộng rãi trong Lý thuyết số theo cái cách mà nó đã làm với Đại số. Bài toán sau đây là một ví dụ, các ví dụ khác tôi cho vào trong phần Bài tập ở cuối bài giảng.

Bài 5(Định lý Wilson). Chứng minh rằng nếu p là một số nguyên tố thì (p-1)!+1\equiv 0\pmod{p}.
Lời giải và bình luận. Quan tâm đến đa thức f(x)=(1-x)(2-x)\cdots (p-1-x)+1-x^{p-1}.
Bài 6. Cho p là một số nguyên tố lớn hơn 3. Chứng minh rằng \sum_{r=1}^{[2p/3]}C_p^r chia hết cho p^2.
Lời giải và bình luận. Vì C_p^i là bội của p với mỗi i\in\{1,2,\cdots,p-1\} nên ta chỉ cần chứng minh \sum_{r=1}^{k}\dfrac{C_p^r}{p} chia hết cho p là đủ, ở đây k=[2p/3]. (Như vậy từ modulo p^2 ta chuyển về modulo p) Trong \mathbb{Z}/p\mathbb{Z}, nhưng bỏ đi dấu gạch ngang trên đầu cho gọn, ta có \dfrac{C_p^r}{p}=\dfrac{(p-r+1)(p-r+2)\cdots (p-1)}{r!}=(-1)^{r-1}\dfrac{1}{r} với mỗi r=1,\cdots,k. Gìơ ta xét hai trường hợp
Nếu p=3h+1 với h là số nguyên dương lớn hơn 1 thì k=2h, là một số chẵn, và tổng ta đang quan tâm bằng \dfrac{1}{1}-\dfrac{1}{2}+\cdots-\dfrac{1}{2h}=\sum_{i=1}^{2h}\dfrac{1}{i}-\sum_{j=1}^h\dfrac{1}{j}

=\sum_{i=1}^{2h}\dfrac{1}{i}+\sum_{j=1}^h\dfrac{1}{p-j}=\sum_{i=1}^{p-1}\dfrac{1}{i}=1+2+\cdots+(p-1)=\dfrac{(p-1)p}{2}=0.
Nếu p=3h+2 với h là số nguyên dương thì chúng ta xét tương tự như trên.
Bài toán được chứng minh đầy đủ.

Bài tập
Bài 7. Viết cụ thể chứng minh của Định lý Lagrange đã nói đến trong bài giảng.
Bài 8. Cho p là một số nguyên tố lẻ khác 3. Chứng minh rằng khi viết số hữu tỉ \dfrac{1}{1}+\dfrac{1}{2}+\cdots+\dfrac{1}{p-1} dưới dạng phân số tối giản thì tử số của nó chia hết cho p^2.
Bài 9. Hai dãy (a_n)(b_n) xác định bởi a_0=1,b_0=4a_{n+1}=a_n^{2001}+b_n,b_{n+1}=b_n^{2001}+a_n với mỗi n\geq 0. Chứng minh rằng 2003 không là ước số của bất cứ số hạng nào trong cả hai dãy này.
Bài 10. Cho p>5 là một số nguyên tố. Với mỗi số nguyên x, định nghĩa f_p(x)=\sum_{k=1}^{p-1}\dfrac{1}{(px+k)^2}. Chứng minh rằng với mỗi cặp số nguyên dương x,y, khi viết phân số f_p(x)-f_p(y) dưới dạng tối giản thì tử số của nó chia hết cho p^3.
Bài 11. Với mỗi số nguyên tố p, tìm dư khi chia \prod_{i=0}^p(1+i^2) cho p.
Bài 12. Cho p>3 là một số nguyên tố. Chứng minh rằng p^3|C_{2p-1}^{p-1}-1.
Bài 13. Cho p>3 là một số nguyên tố. Chứng minh rằng p^2|\sum_{k=1}^{p^2-1}C_{2k}^k.
Bài 14. Chứng minh rằng nếu p là một số nguyên tố và 0\leq m<n<p thì C_{np+m}^{mp+n}\equiv (-1)^{m+n+1}p\pmod{p^2}.
Bài 15. Cho p là một số nguyên tố lẻ và \dfrac{1}{1}-\dfrac{1}{2}+\cdots-\dfrac{1}{p-1}=\dfrac{a}{(p-1)!}. Chứng minh rằng a\equiv \dfrac{2-2^p}{p}\pmod{p}.
Tài liệu tham khảo

(1) David S. Dummit and Richard M. Foote, Abstract Algebra, third edition.
(2) Gareth A. Jones and J. Mary Jones, Elementary number theory, Springer.
(3) Hà Huy Khoái, Số học, NXB Giáo dục.

1 thought on “[Qn2009.4]: Số học của Z/pZ”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s