5.1. Trường

Định nghĩa 5.1 (Trường)

Cho tập hợp \(F\) và hai toán tử hai ngôi trên \(F\) là phép cộng \(+\) và phép nhân \(\times\). Khi đó \((F, +, \times)\) là trường (hay field, поля) nếu

1. \((F, +, \times)\) là vành giao hoán với đơn vị.

2. Với mọi phần tử \(f \neq 0_F\), tồn tại nghịch đảo \(f^{-1}\) của \(f\) đối với phép nhân, nghĩa là

\[f \times f^{-1} = f^{-1} \times f = 1_F.\]

Nói cách khác, \((F, \times)\) là nhóm Abel. Trên trường ta thực hiện được bốn phép tính cộng, trừ, nhân, chia.

Ví dụ 5.1

Các tập hợp sau với phép cộng và nhân là trường.

1. Tập hợp số thực \(\mathbb{R}\).

2. Tập hợp các số phức \(\mathbb{C}\).

3. Tập hợp các số dạng \(a + b \sqrt{2}\) với \(a, b \in \mathbb{Q}\).

Những trường trên được gọi là trường vô hạn vì có vô số phần tử.

Ngược lại, chúng ta cũng có các trường hữu hạn.

5.1.1. Trường hữu hạn

5.1.1.1. Trường hữu hạn modulo nguyên tố

Cho \(p\) là số nguyên tố. Khi đó tập hợp các số dư khi chia cho \(p\) cùng với phép cộng và nhân modulo \(p\) tạo thành trường.

Chứng minh

Xét tập hợp các số dư khi chia cho \(p\) là

\[S = \{0, 1, \ldots, p-2, p-1\}.\]

Ta thấy rằng với mọi \(a, b \in S\) thì \(a + b \pmod p\) và \(a \cdot b \pmod p\) đều thuộc \(S\).

1. Vì \(0 + a = a + 0 = a \pmod p\) với mọi \(a \in S\) nên \(0\) là phần tử đơn vị của phép cộng.

2. Với mọi \(a \in S\), ta có \((p-a) + a = a + (p-a) \equiv 0 \pmod p\) nên phần tử nghịch đảo của \(a\) đối với phép cộng là \(p-a \in S\).

3. Phép cộng modulo có tính kết hợp.

4. Phép cộng modulo có tính giao hoán.

Như vậy \((S, +)\) là nhóm Abel.

Tiếp theo, ta thấy rằng phép cộng và nhân có tính phân phối trên modulo.

Đồng thời phép nhân modulo cũng có tính kết hợp. Do đó \((S, +, \cdot)\) là vành.

1. Phần tử đơn vị của phép nhân là \(1\).

2. Phép nhân modulo có tính giao hoán.

3. Do mọi phần tử thuộc \(S\) đều nguyên tố cùng nhau với \(p\) nên luôn tồn tại nghịch đảo của phần tử khác \(0\) trong \(S\).

Kết luận: \((S, +, \cdot)\) là trường.

Ta thường kí hiệu trường này là \(\mathrm{GF}(p)\) (GF là viết tắt của Galois Field để tưởng nhớ người có đóng góp quan trọng trong lý thuyết nhóm).

5.1.1.2. Trường hữu hạn modulo đa thức

Xét các đa thức với hệ số nguyên

\[f(x) = a_n x^n + a_{n-1} x^{n-1} + \ldots + a_2 x^2 + a_1 x + a_0.\]

Ta thấy rằng phép cộng và nhân hai đa thức tạo thành một vành giao hoán với đơn vị là đa thức \(f(x) \equiv 1\).

Thêm nữa vành này có vô số phần tử. Ta cần một phương án để số phần tử là hữu hạn, và đồng thời là trường.

Với \(p\) là số nguyên tố và \(n\) là số nguyên dương. Mình xét các đa thức có bậc tối đa là \(n-1\) với hệ số nằm trong tập hợp các số dư khi chia cho \(p\). Như vậy mình có \(p^n\) đa thức như vậy.

Ví dụ 5.2

Với \(p = 3\) và \(n = 2\). Khi đó các đa thức có thể có là

\[\{ 0, 1, 2, x, x+1, x+2, 2x, 2x+1, 2x+2 \}.\]

Tương tự với việc modulo cho một số nguyên tố, ở đây mình xét phép cộng và nhân trên modulo một đa thức tối giản (irreducible polynomial) có bậc \(n\) (vì khi modulo một đa thức bậc bất kì cho đa thức bậc \(n\) ta có đa thức bậc nhỏ hơn \(n\)).

Đồng thời hệ số của đa thức từ phép cộng và nhân cũng được modulo \(p\) (nằm trong \(\mathrm{GF}(p)\)).

Với trường hợp \(p = 3\) và \(n = 2\) ở trên mình có thể chọn đa thức modulo là \(m(x) = x^2 + 2x + 2\).

Sau đây là bảng phép cộng hai đa thức bậc nhỏ hơn \(2\) trong modulo \(m(x)\).

	\(0\)	\(1\)	\(2\)	\(x\)	\(x+1\)	\(x+2\)	\(2x\)	\(2x+1\)	\(2x+2\)
\(0\)	\(0\)	\(1\)	\(2\)	\(x\)	\(x+1\)	\(x+2\)	\(2x\)	\(2x+1\)	\(2x+2\)
\(1\)	\(1\)	\(2\)	\(0\)	\(x+1\)	\(x+2\)	\(x\)	\(2x+1\)	\(2x+2\)	\(2x\)
\(2\)	\(2\)	\(0\)	\(1\)	\(x+2\)	\(x\)	\(x+1\)	\(2x+2\)	\(2x\)	\(2x+1\)
\(x\)	\(x\)	\(x+1\)	\(x+2\)	\(2x\)	\(2x+1\)	\(2x+2\)	\(0\)	\(1\)	\(2\)
\(x+1\)	\(x+1\)	\(x+2\)	\(x\)	\(2x+1\)	\(2x+2\)	\(2x\)	\(1\)	\(2\)	\(0\)
\(x+2\)	\(x+2\)	\(x\)	\(x+1\)	\(2x+2\)	\(2x\)	\(2x+1\)	\(2\)	\(0\)	\(1\)
\(2x\)	\(2x\)	\(2x+1\)	\(2x+2\)	\(0\)	\(1\)	\(2\)	\(x\)	\(x+1\)	\(x+2\)
\(2x+1\)	\(2x+1\)	\(2x+2\)	\(2x\)	\(1\)	\(2\)	\(0\)	\(x+1\)	\(x+2\)	\(x\)
\(2x+2\)	\(2x+2\)	\(2x\)	\(2x+1\)	\(2\)	\(0\)	\(1\)	\(x+2\)	\(x\)	\(x+1\)

Tương tự, sau đây là bảng phép nhân hai đa thức bậc nhỏ hơn \(2\) trong modulo \(m(x)\).

	\(0\)	\(1\)	\(2\)	\(x\)	\(x+1\)	\(x+2\)	\(2x\)	\(2x+1\)	\(2x+2\)
\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)
\(1\)	\(0\)	\(1\)	\(2\)	\(x\)	\(x+1\)	\(x+2\)	\(2x\)	\(2x+1\)	\(2x+2\)
\(2\)	\(0\)	\(2\)	\(1\)	\(2x\)	\(2x+2\)	\(2x+1\)	\(x\)	\(x+2\)	\(x+1\)
\(x\)	\(0\)	\(2x\)	\(x+1\)	\(2x\)	\(2x+1\)	\(1\)	\(2x+2\)	\(2\)	\(x+2\)
\(x+1\)	\(0\)	\(x+1\)	\(2x+2\)	\(2x+1\)	\(2\)	\(x\)	\(x+2\)	\(2x\)	\(1\)
\(x+2\)	\(0\)	\(x+2\)	\(2x+1\)	\(1\)	\(x\)	\(2x+2\)	\(2\)	\(x+1\)	\(2x\)
\(2x\)	\(0\)	\(2x\)	\(x\)	\(2x+2\)	\(x+2\)	\(2\)	\(x+1\)	\(1\)	\(2x+1\)
\(2x+1\)	\(0\)	\(2x+1\)	\(x+2\)	\(2\)	\(2x\)	\(x+1\)	\(1\)	\(2x+2\)	\(x\)
\(2x+2\)	\(0\)	\(2x+2\)	\(x+1\)	\(x+2\)	\(1\)	\(2x\)	\(2x+1\)	\(x\)	\(2\)

Ta thấy rằng bảng phép nhân đối xứng qua đường chéo chính. Điều này chứng tỏ phép nhân có tính giao hoán. Thêm nữa ở mỗi hàng hoặc cột khác \(0\) đều có \(9\) phần tử khác nhau.

5.1.2. Phân tích \(x^p - x\) và \(x^{p^n} - x\) thành nhân tử

Tiếp theo chúng ta sẽ phân tích các đa thức \(x^p - x\) và \(x^{p^n} - x\) thành nhân tử với \(p\) là số nguyên tố.

Định lý 5.1 (Phân tích \(x^p - x\))

Với \(p\) là số nguyên tố, đa thức \(q(x) = x^p - x\) trên \(\mathbb{F}_p\) có phân tích là

\[q(x) = x^p - x = x (x - 1) (x - 2) \cdots (x - (p - 1)).\]

Chứng minh

Theo định lí Fermat nhỏ, \(a^p \equiv a \pmod{p}\) với mọi \(a \in \mathbb{F}_p\). Nói cách khác với mọi \(a \in \mathbb{F}_p\) ta có \(q(a) = a^p - a = 0\) trên \(\mathbb{F}_p\), hay \(a\) là nghiệm của \(q(x)\).

Đa thức \(q(x)\) có bậc là \(p\) nên có tối đa \(p\) nghiệm, và mọi phần tử \(a \in \mathbb{F}_p\) đều là nghiệm, nên ta có điều phải chứng minh khi đồng nhất hệ số \(x^p\) ở hai vế.

Định lý 5.2 (Phân tích \(x^{p^n} - x\))

Với \(p\) là số nguyên tố và \(n\) là số nguyên dương bất kì, đa thức \(q(x) = x^{p^n} - x\) trên \(\mathbb{F}_p\) là tích của tất cả đa thức tối giản có bậc là ước của \(n\).

Để chứng minh định lí trên ta cần ba bổ đề:

1. Hàm số \(x^{p^n} - x\) không có nhân tử bội (Bổ đề 5.1).

2. Nếu một đa thức tối giản có bậc là ước của \(n\) thì đa thức đó là ước của \(q(x)\) (Bổ đề 5.2.

3. Ngoài ra, không có đa thức tối giản nào khác là ước của \(q(x)\).

Bổ đề 5.1

Hàm số \(f(x)\) không có nhân tử bội khi và chỉ khi nó nguyên tố cùng nhau với đạo hàm của nó.

Chứng minh

Ta chứng minh mệnh đề đối: hàm số \(f(x)\) có nhân tử bội khi và chỉ khi nó không nguyên tố cùng nhau với đạo hàm của nó.

Điều kiện đủ. Với \(f(x)\) có nhân tử bội, ta cần chứng minh \(\gcd(f(x), f'(x)) \neq 1\).

Giả sử \(f(x) = [d(x)]^k \cdot g(x)\) với \(d(x)\) là đa thức tối giản có bậc thấp hơn \(f(x)\) và \(k \geqslant 2\). Khi đó

\[\begin{split}f'(x) = k \cdot [d(x)]^{k-1} \cdot d'(x) \cdot g(x) + [d(x)]^k \cdot g'(x) \\ = [d(x)]^{k-1}[k \cdot d'(x) \cdot g(x) + d(x) \cdot g'(x)],\end{split}\]

nên suy ra \([d(x)]^{k-1}\) chia hết \(f'(x)\), mà \(k \geqslant 2\) nên \([d(x)]^{k-1} \neq 1\), hay \(\gcd(f(x), f'(x)) \neq 1\).

Điều kiện cần. Giả sử \(\gcd(f(x), f'(x)) = d(x) \neq 1\), ta cần chứng minh \(f(x)\) có nhân tử bội.

Vì \(d(x)\) chia hết \(f(x)\) nên tồn tại \(g(x)\) sao cho \(f(x) = d(x) \cdot g(x)\). Khi đó

\[f'(x) = d'(x) \cdot g(x) + d(x) \cdot g'(x),\]

mà \(d(x)\) cũng chia hết \(f'(x)\) nên \(d(x)\) chia hết \(d'(x) \cdot g(x)\). Ở đây \(d'(x)\) có bậc thấp hơn \(d(x)\) nên \(d(x)\) không thể chia hết \(d'(x)\), suy ra \(d(x)\) phải chia hết \(g(x)\).

Như vậy \(g(x) = d(x) \cdot h(x)\), thay vào \(f(x)\) ta có nhân tử bội \([d(x)]^2\). Ta có điều phải chứng minh.

Bổ đề 5.2

Xét đa thức \(q(x) = x^{q^n} - x\) trên \(\mathbb{F}_p\). Khi đó mọi đa thức tối giản có bậc là ước của \(n\) thì chia hết cho \(q(x)\).

Chứng minh

Giả sử \(s(x)\) là đa thức tối giản bậc \(d\) trên \(\mathbb{F}_p\) sao cho \(n = ad\) với \(a \in \mathbb{Z}\).

Vì \(s(x)\) là đa thức tối giản trên \(\mathbb{F}_p\) nên nó xác định trường hữu hạn \(\mathbb{F}_{p^d}\) có \(p^d\) phần tử. Khi đó \(\mathbb{F}_{p^d}^*\) là nhóm đối với phép nhân nên

\[x^{p^d - 1} \equiv 1 \bmod{s(x)} \Longleftrightarrow (x^{p^d - 1} - 1) \ \vdots \ s(x).\]

Ta sử dụng bổ đề về tính chất của ước chung lớn nhất sau: với mọi \(a\), \(m\), \(n\) ta đều có

\[\gcd(a^m - 1, a^n - 1) = a^{\gcd(m, n)} - 1.\]

Thay \(a\) thành \(x\), \(m\) thành \(p^d - 1\) và \(p^n - 1\) ta có

(5.1)\[\gcd(x^{p^d - 1} - 1, x^{p^n - 1} - 1) = x^{\gcd(p^d - 1, p^n - 1)} - 1.\]

Vì \(n = ad\) nên

\[p^n - 1 = \left(p^d\right)^a - 1 = (p^d - 1)[(p^d)^{a-1} + (p^d)^{a-2} + \cdots + (p^d) + 1],\]

hay \(p^d - 1\) là ước của \(p^n - 1\), suy ra \(\gcd(p^d - 1, p^n - 1) = p^d - 1\). Do đó từ (5.1) suy ra

\[\gcd(x^{p^d - 1} - 1, x^{p^n - 1} - 1) = x^{p^d - 1} - 1,\]

nói cách khác \(x^{p^d - 1} - 1\) là ước của \(x^{p^n - 1} - 1\), và \(s(x)\) là ước của \(x^{p^d - 1} - 1\) từ chứng minh trên, nên suy ra \(s(x)\) là ước của \(x^{p^n - 1} - 1\) và

\[x^{p^n - 1} - 1 \equiv 0 \bmod{s(x)} \Longrightarrow x^{p^n} - x \equiv 0 \bmod{s(x)} \Longleftrightarrow (x^{p^n} - x) \ \vdots \ s(x).\]

Ta có điều phải chứng minh.

Bổ đề 5.3

Xét đa thức \(q(x) = x^{q^n} - x\) trên \(\mathbb{F}_p\). Khi đó mọi đa thức tối giản có bậc là không là ước của \(n\) thì cũng không là ước của \(q(x)\).

Chứng minh

Giả sử tồn tại đa thức \(s(x)\) là ước của \(q(x)\) nhưng có bậc không là ước của \(n\) gọi là \(d\). Rõ ràng \(s(x) \neq x\) vì đây là đa thức tối giản bậc \(1\), mà \(1\) là ước của mọi số nguyên. Như vậy suy ra \(s(x)\) là ước của \(x^{p^n - 1} - 1\).

Tương tự bên trên, \(s(x)\) xác định trường hữu hạn có \(p^d\) phần tử, do đó với mọi phần tử \(a \in \mathbb{F}_{p^d}\) ta có

\[a^{p^d - 1} \equiv 1 \bmod{s(x)}.\]

Vì

\[s(x) \mid (x^{p^n - 1} - 1) \Longrightarrow a^{p^n - 1} \equiv 1 \bmod{s(x)} \ \text{với mọi} \ a \in \mathbb{F}_{p^d}.\]

Như vậy, theo định lí Lagrange, order đối với phép nhân của bất kì phần tử nào trong \(\mathbb{F}_{p^d}\) phải là ước của \(p^d - 1\) và \(p^n - 1\), hay

\[a^{p^{\gcd(d, n)} - 1} \equiv 1 \bmod{s(x)} \ \text{với mọi} \ a \in \mathbb{F}_{p^d}.\]

Điều này là bất khả thi vì đa thức \(q(t) = t^{p^{\gcd(d, n)} - 1} - 1\) là đa thức bậc \(p^{\gcd(d, n) - 1}\), mà \(d\) không là ước của \(n\) nên \(\gcd(d, n) < d\), suy ra \(p^{\gcd(d, n) - 1} < p^d - 1\) và \(q(t)\) không thể có \(p^d - 1\) nghiệm.

Chứng minh (Định lý 5.2)

Với \(q(x) = x^{p^n} - x\) ta có

\[q'(x) = p^n x^{p^n - 1} - 1,\]

mà \(\mathbb{F}_p\) có đặc số là \(p\) nên ta rút gọn được \(p^n x^{p^n - 1}\), suy ra \(q(x)\) và \(q'(x)\) là hai đa thức nguyên tố cùng nhau. Như vậy \(q(x)\) không có nhân tử bội.

Ngoài ra, từ Bổ đề 5.2 và Bổ đề 5.3 ta có điều phải chứng minh.

Từ đây chúng ta có thể tính được số lượng đa thức tối giản bậc \(n\) trên trường \(\mathbb{F}_p\) bất kì.

Định lý 5.3

Số lượng đa thức tối giản bậc \(n\) trên trường hữu hạn \(\mathbb{F}_p\) với \(p\) nguyên tố là

\[f_q(n) = \dfrac{1}{n} \sum_{d \mid n} \mu(n / d) p^{d},\]

trong đó \(\mu(d)\) là hàm Mobius của số nguyên \(d\).

Chứng minh

Ở trên ta đã chứng minh được tích tất cả đa thức tối giản có bậc là ước của \(n\) trên \(\mathbb{F}_p\) là \(x^{p^n} - x\) (Định lý 5.2). Xét hạng tử bậc cao nhất trong mỗi đa thức tối giản ta có

\[x^{p^n} = \prod_{d \mid n} \left(x^d\right)^{f_q(d)} = \prod_{d \mid n} x^{d f_q(d)}\]

vì ta có \(f_q(d)\) đa thức tối giản bậc \(d\) với mọi \(d \mid n\). So sánh số mũ hai vế ta được

\[p^n = \sum_{d \mid n} d f_q(d).\]

Theo công thức nghịch đảo Mobius (bài viết Hàm Möbius) ta chọn \(f(n) = p^n\) và \(g(n) = n f_q(n)\) suy ra

\[f_q(n) = \dfrac{1}{n} \sum_{d \mid n} \mu(n / d) p^d.\]