# Các lớp đồng dư tạo thành phân hoạch của tập số nguyên


Tập số nguyên $\mathbb{Z}$ là một tập hợp vô hạn, rời rạc, trải dài vô tận về cả hai phía âm và dương. Thoạt nhìn, đó là một dải số liên tục không có bất kỳ ranh giới tự nhiên nào để chia cắt.

**Mấu chốt sâu xa nhất của bài toán này là khẳng định: Tập số nguyên $\mathbb{Z}$ là phân hoạch được (partitionable).** 

Chỉ thông qua một số nguyên dương $n$ bất kỳ, quan hệ đồng dư modulo $n$ thực hiện một phép phẫu thuật cấu trúc lên toàn bộ trục số: phân rã không gian vô hạn $\mathbb{Z}$ thành đúng $n$ lát cắt hoàn toàn độc lập, đôi một không giao nhau và hợp lại phủ kín toàn bộ thế giới số nguyên. 

Bài viết này trình bày chứng minh chặt chẽ cho tính chất phân hoạch của $\mathbb{Z}$, làm rõ tại sao việc phân hoạch được là điều kiện tiên quyết để xây dựng **Vành thương $\mathbb{Z}/n\mathbb{Z}$**, đồng thời giải mã mối liên hệ cốt lõi dẫn lối đến lý thuyết **Cơ sở Gröbner** trong đại số máy tính hiện đại.

---

## Đề bài

Cho $n \in \mathbb{N}$ với $n \ge 1$.

1. Sử dụng Thuật toán chia với số dư (Division Algorithm) để chứng minh rằng mọi số nguyên $a \in \mathbb{Z}$ đều đồng dư modulo $n$ với **chính xác một** số nguyên thuộc tập hợp $\{0, 1, \dots, n - 1\}$.
2. Kết luận rằng nếu $r \in \mathbb{Z}$, thì tồn tại duy nhất một phần tử $s \in \{0, 1, \dots, n - 1\}$ sao cho $[r] = [s]$. Từ đó suy ra các lớp tương đương modulo $n$ lập thành một **phân hoạch** (partition) của tập số nguyên $\mathbb{Z}$.

---

## 1. Câu 1: Thuật toán chia có dư — Chiếc chìa khóa phân loại số nguyên

Để chứng minh mỗi số nguyên $a$ đồng dư với chính xác một số trong $\{0, 1, \dots, n - 1\}$, ta cần chứng minh hai mệnh đề độc lập: tính **tồn tại** và tính **duy nhất**.

### Bước 1: Chứng minh tính tồn tại (Mỗi số nguyên đều có chỗ đứng)
Cho $a \in \mathbb{Z}$ và $n \in \mathbb{Z}^+$. Theo [Thuật toán chia với số dư]({{< ref "posts/math/algebra/well-ordering-and-induction.md" >}}), tồn tại duy nhất cặp số nguyên $q$ (thương) và $r$ (số dư) sao cho:
$$a = qn + r, \quad \text{với } 0 \le r < n.$$

Từ phương trình trên, ta chuyển vế:
$$a - r = qn \implies n \mid (a - r).$$

Theo định nghĩa của quan hệ đồng dư, điều này tương đương với:
$$a \equiv r \pmod n.$$

Vì $r$ là số nguyên thỏa mãn $0 \le r < n$, nên chắc chắn:
$$r \in \{0, 1, \dots, n - 1\}.$$

Như vậy, với bất kỳ số nguyên $a$ nào, luôn **tồn tại** một số nguyên $r$ thuộc tập $\{0, 1, \dots, n - 1\}$ đồng dư với $a$ modulo $n$.

---

### Bước 2: Chứng minh tính duy nhất (Không có sự chồng lấn)
Giả sử tồn tại hai số nguyên $r_1, r_2 \in \{0, 1, \dots, n - 1\}$ cùng đồng dư với $a$ modulo $n$:
$$a \equiv r_1 \pmod n \quad \text{và} \quad a \equiv r_2 \pmod n.$$

Do quan hệ đồng dư có tính chất bắc cầu và đối xứng:
$$r_1 \equiv r_2 \pmod n \implies n \mid (r_1 - r_2).$$

Không mất tính tổng quát, giả sử $r_1 \ge r_2$. Vì cả $r_1$ và $r_2$ đều thuộc $\{0, 1, \dots, n - 1\}$, khoảng cách giữa chúng bị chặn nghiêm ngặt:
$$0 \le r_1 - r_2 \le r_1 \le n - 1 < n.$$

Nghĩa là:
$$0 \le r_1 - r_2 < n.$$

Trong khoảng $[0, n)$, số nguyên duy nhất chia hết cho $n$ chính là số $0$:
$$r_1 - r_2 = 0 \implies r_1 = r_2.$$

Do đó, số nguyên $r \in \{0, 1, \dots, n - 1\}$ thỏa mãn $a \equiv r \pmod n$ là **duy nhất**.

---

## 2. Câu 2: Tập số nguyên $\mathbb{Z}$ là phân hoạch được

### Bước 1: Đại diện chuẩn tắc duy nhất của mỗi lớp tương đương
Với mỗi số nguyên $r \in \mathbb{Z}$, lớp tương đương của nó modulo $n$ (còn gọi là lớp đồng dư) được định nghĩa là tập hợp tất cả các số nguyên có cùng số dư với $r$:
$$[r] = \{ x \in \mathbb{Z} \mid x \equiv r \pmod n \}.$$

Theo kết quả của Câu 1, với bất kỳ số nguyên $r \in \mathbb{Z}$, tồn tại duy nhất một số $s \in \{0, 1, \dots, n - 1\}$ sao cho:
$$r \equiv s \pmod n.$$

Vì quan hệ đồng dư là quan hệ tương đương, hai phần tử đồng dư với nhau sẽ sinh ra cùng một lớp tương đương:
$$r \equiv s \pmod n \iff [r] = [s].$$

Điều này khẳng định: **Dù tập số nguyên có vô hạn lớp hình thức $[r]$ với $r \in \mathbb{Z}$, thực chất chúng chỉ là bản sao của đúng $n$ lớp chuẩn tắc:**
$$[0], [1], [2], \dots, [n - 1].$$
Mỗi số $s \in \{0, 1, \dots, n - 1\}$ đóng vai trò là **đại diện chuẩn tắc** (canonical representative) duy nhất cho lớp của mình.

---

### Bước 2: Chứng minh họ các lớp lập thành một phân hoạch của $\mathbb{Z}$

Trong lý thuyết tập hợp, một họ các tập con $\mathcal{P}$ của một tập hợp $X$ được gọi là một **phân hoạch** (partition) của $X$ nếu và chỉ nếu nó thỏa mãn đồng thời 3 điều kiện tiên quyết:

1. **Khác rỗng:** Mọi tập con trong họ đều chứa ít nhất một phần tử.
2. **Đôi một rời nhau:** Hai tập con bất kỳ khác nhau trong họ hoàn toàn không có phần tử chung.
3. **Phủ kín không gian:** Hợp của toàn bộ các tập con trong họ tái tạo lại chính xác tập ban đầu $X$.

Xét họ $n$ lớp tương đương:
$$\mathcal{P} = \{ [0], [1], [2], \dots, [n - 1] \}.$$

Ta kiểm chứng từng điều kiện trên tập hợp $\mathbb{Z}$:

- **Điều kiện 1 (Mỗi ngăn kéo đều có phần tử):**  
  Với mọi $s \in \{0, 1, \dots, n - 1\}$, vì $s \equiv s \pmod n$ nên hiển nhiên $s \in [s]$. Do đó $[s] \neq \emptyset$.
- **Điều kiện 2 (Các ngăn kéo không chồng lấn lên nhau):**  
  Lấy hai chỉ số khác nhau $s_1 \neq s_2$ thuộc $\{0, 1, \dots, n - 1\}$. Giả sử phản chứng rằng hai lớp này có điểm chung, tức tồn tại $x \in [s_1] \cap [s_2]$.  
  Khi đó:
  $$x \equiv s_1 \pmod n \quad \text{và} \quad x \equiv s_2 \pmod n.$$
  Bắc cầu suy ra $s_1 \equiv s_2 \pmod n$. Nhưng theo tính duy nhất đã chứng minh ở Câu 1, hai số khác nhau trong $\{0, 1, \dots, n - 1\}$ không thể đồng dư với nhau modulo $n$. Sự mâu thuẫn này chứng minh:
  $$[s_1] \cap [s_2] = \emptyset \quad (\forall s_1 \neq s_2).$$
- **Điều kiện 3 (Phủ kín không bỏ sót bất kỳ số nguyên nào):**  
  Với mọi số nguyên $a \in \mathbb{Z}$, theo Câu 1, phép chia có dư luôn tìm được một số dư $r \in \{0, 1, \dots, n - 1\}$ sao cho $a \equiv r \pmod n$, nghĩa là $a \in [r]$. Do đó:
  $$\mathbb{Z} \subseteq \bigcup_{s=0}^{n-1} [s].$$
  Vì mỗi $[s]$ đều là tập con của $\mathbb{Z}$, ta có đẳng thức phủ kín tuyệt đối:
  $$\mathbb{Z} = \bigcup_{s=0}^{n-1} [s] = [0] \cup [1] \cup \dots \cup [n - 1].$$

> **Kết luận cốt lõi:**  
> Họ các lớp tương đương $\{ [0], [1], \dots, [n - 1] \}$ tạo thành một **phân hoạch hoàn chỉnh** của tập số nguyên $\mathbb{Z}$. Tập hợp các lớp phân hoạch này được ký hiệu là **vành thương** $\mathbb{Z}/n\mathbb{Z}$ (hoặc $\mathbb{Z}_n$).

---

## 3. Ý nghĩa nền tảng: Bốn mấu chốt của tính chất "Phân hoạch được"

Việc tập số nguyên $\mathbb{Z}$ phân hoạch được không chỉ là một kết quả kỹ thuật về chia có dư, mà là **nền tảng cấu trúc** định hình toàn bộ tư duy đại số hiện đại. Bốn mấu chốt sâu sắc nhất bao gồm:

### 1. Khẳng định tính "Phân hoạch được" của $\mathbb{Z}$

- **Trục số nguyên $\mathbb{Z}$** là một tập hợp vô hạn rời rạc trải dài hai phía $-\infty \dots +\infty$. Nhìn bề ngoài, nó không có bất kỳ ranh giới tự nhiên nào để chia cắt.
- **Quan hệ đồng dư modulo $n$** đã thực hiện một phép phẫu thuật cấu trúc: phân rã toàn bộ tập vô hạn $\mathbb{Z}$ thành đúng $n$ "lát cắt" $\{[0], [1], \dots, [n - 1]\}$:
  - **Không bỏ sót:** Hợp của $n$ lớp phủ kín hoàn toàn $\mathbb{Z}$ ($\bigcup_{s=0}^{n-1}[s] = \mathbb{Z}$);
  - **Không chồng lấn:** Hai lớp bất kỳ hoàn toàn rời nhau ($[s_1] \cap [s_2] = \emptyset$ khi $s_1 \neq s_2$);
  - **Không rỗng:** Mỗi lớp đều có ít nhất một phần tử ($s \in [s]$).

```text
Trục số nguyên vô hạn Z:
... -4   -3   -2   -1    0    1    2    3    4    5    6    7    8 ...
─────────────────────────────────────────────────────────────────
[0] = { ..., -2n,  -n,   0,   n,  2n, ... }   (các bội của n)
[1] = { ..., -2n+1, -n+1, 1, n+1, 2n+1, ... } (dư 1)
[2] = { ..., -2n+2, -n+2, 2, n+2, 2n+2, ... } (dư 2)
...
[n-1] = { ..., -n-1, -1, n-1, 2n-1, 3n-1, ... } (dư n-1)
```

### 2. Thu gọn vô hạn về hữu hạn (Taming Infinity)

- Nhờ $\mathbb{Z}$ phân hoạch được, ta không cần phải làm việc với vô hạn số nguyên nữa. Toàn bộ tính chất của $\mathbb{Z}$ được "nén" vào đúng $n$ đại diện chuẩn tắc $\{0, 1, \dots, n - 1\}$.
- Thay vì phải khảo sát vô số phần tử rời rạc trải dài trên trục số, ta quy toàn bộ các khảo sát đồng dư về một tập hợp hữu hạn chỉ gồm đúng $n$ phần tử:
  $$\mathbb{Z}/n\mathbb{Z} = \{ [0], [1], \dots, [n - 1] \}.$$
- **Trực giác Đồng hồ số học (Clock Arithmetic):** Hình ảnh trực quan nhất của sự phân hoạch này chính là mặt đồng hồ tròn 12 vạch:
  - Trục số vô hạn thời gian (các mốc giờ $\dots, -11, 1, 13, 25, 37, \dots$) đều rơi chính xác vào vạch số $1$ ($[1]$).
  - Các mốc giờ $\dots, -12, 0, 12, 24, 36, \dots$ đều rơi vào vạch số $12$ (tương ứng với lớp $[0]$).
  Mặt đồng hồ tròn chính là mô hình hình học của việc "uốn cong" trục số vô hạn $\mathbb{Z}$ thành một vòng tròn phân hoạch $12$ lớp.

### 3. Điều kiện sống còn cho cấu trúc Vành thương $\mathbb{Z}/n\mathbb{Z}$

- Nếu $\mathbb{Z}$ không phân hoạch được thành các lát cắt độc lập, phép toán cộng và nhân lớp:
  $$[a] + [b] = [a + b], \qquad [a] \cdot [b] = [a \cdot b]$$
  sẽ bị phụ thuộc vào đại diện được chọn (tính xác định đúng đắn — *well-definedness* bị phá vỡ), khiến cấu trúc đại số của vành thương sụp đổ ngay từ gốc.
- Cụ thể: giả sử ta chọn hai đại diện khác nhau trong cùng một lớp, $a \equiv a' \pmod n$ và $b \equiv b' \pmod n$. Do các lớp phân hoạch không chồng chéo và hoàn toàn xác định theo quan hệ đồng dư, ta luôn bảo đảm:
  $$a + b \equiv a' + b' \pmod n \implies [a + b] = [a' + b'],$$
  $$a \cdot b \equiv a' \cdot b' \pmod n \implies [a \cdot b] = [a' \cdot b'].$$
  Nếu không có phân hoạch chặt chẽ, việc chọn các phần tử đại diện khác nhau sẽ cho ra kết quả rơi vào các ngăn kéo hỗn loạn khác nhau, và $\mathbb{Z}/n\mathbb{Z}$ sẽ không thể là một cấu trúc đại số hợp thức.

### 4. Sợi dây nối tới Cơ sở Gröbner

- **Trong $\mathbb{Z}$**, việc phân hoạch được thực hiện dễ dàng nhờ tính duy nhất của số dư trong Thuật toán chia Euclid. Mọi số nguyên $a$ đều có duy nhất một dạng chuẩn tắc:
  $$a \bmod n = r \in \{0, 1, \dots, n - 1\}.$$
  Điều này cho phép kiểm tra quan hệ thuộc i-đê-an ($a \in n\mathbb{Z} \iff a \bmod n = 0$) và kiểm tra hai phần tử cùng lớp ($[a] = [b] \iff a \bmod n = b \bmod n$) một cách tức thì.
- **Trong vành đa thức nhiều biến $K[x_1, \dots, x_m]$**, phép chia thông thường không cho số dư duy nhất nên không tự phân hoạch được không gian thương. Khi lấy đa thức $f$ chia cho hệ sinh của một i-đê-an $I = \langle g_1, \dots, g_s \rangle$, thương và số dư phụ thuộc hoàn toàn vào thứ tự chia. Cùng một đa thức có thể cho nhiều số dư khác nhau, thậm chí $f \in I$ nhưng phép chia vẫn có thể để lại số dư khác 0. Do thiếu đại diện chuẩn tắc duy nhất, việc phân hoạch không gian thương $K[x_1, \dots, x_m]/I$ bị bế tắc.
- **Cơ sở Gröbner ra đời chính là để mang lại khả năng phân hoạch với đại diện chuẩn tắc duy nhất cho đại số đa biến:**
  > **Cơ sở Gröbner** $G$ là một hệ sinh đặc biệt của i-đê-an $I$ sao cho: đối với mọi đa thức $f$, thuật toán chia cho $G$ luôn cho ra **duy nhất một phần dư chuẩn tắc** (ký hiệu là $\operatorname{NF}(f, G)$), hoàn toàn độc lập với thứ tự chia.

Nhờ có Cơ sở Gröbner, vành đa thức nhiều biến $K[x_1, \dots, x_m]$ mới được phân hoạch chặt chẽ thành các lớp tương đương với đại diện chuẩn tắc duy nhất, khôi phục lại trọn vẹn khả năng phân hoạch mà phép chia có dư đã thiết lập trên tập số nguyên $\mathbb{Z}$:

| Tiêu chí phân hoạch | Trên số nguyên $\mathbb{Z}$ (Số học) | Trên vành đa thức nhiều biến $K[x_1, \dots, x_m]$ |
| :--- | :--- | :--- |
| **I-đê-an chia** | $I = n\mathbb{Z}$ | $I = \langle g_1, \dots, g_s \rangle$ |
| **Công cụ tạo phân hoạch** | Thuật toán chia Euclid với số chia $n$ | Phép chia đa thức theo **Cơ sở Gröbner** $G$ |
| **Đại diện chuẩn tắc duy nhất** | Số dư $r \in \{0, 1, \dots, n - 1\}$ | Đa thức dư chuẩn tắc $\operatorname{NF}(f, G)$ |
| **Vành thương được phân hoạch** | $\mathbb{Z}/n\mathbb{Z} = \{[0], [1], \dots, [n - 1]\}$ | $K[x_1, \dots, x_m]/I \cong \operatorname{Span}(\text{các đơn thức chuẩn})$ |
| **Kiểm tra thành viên $x \in I$** | $a \in n\mathbb{Z} \iff a \bmod n = 0$ | $f \in I \iff \operatorname{NF}(f, G) = 0$ |

---

## Xem thêm các bài viết liên quan

1. [Nguyên lý Thứ tự tốt và Quy nạp Toán học]({{< ref "posts/math/algebra/well-ordering-and-induction.md" >}}) — Cơ sở nền tảng xác lập tính dừng và tính duy nhất của Thuật toán chia có dư.
2. [Bổ đề Bézout dưới góc nhìn Hình học Mạng lưới và Vành I-đê-an chính (PID)]({{< ref "posts/math/algebra/bezout-pid-and-lattices.md" >}}) — Khảo sát cấu trúc i-đê-an chính $n\mathbb{Z}$ và giới hạn khi chuyển sang không gian đa biến.
3. [Bổ đề Euclid: Cầu nối giữa Bổ đề Bézout và Tính duy nhất của Phân tích Nguyên tố]({{< ref "posts/math/algebra/euclids-lemma.md" >}}) — Ứng dụng để chứng minh tính nguyên tố và cấu trúc trường $\mathbb{Z}/p\mathbb{Z}$ khi $n = p$.
4. [Bản đồ chuỗi bài viết Đại số: Từ Thứ tự tốt đến Bổ đề Bézout và Vành PID]({{< ref "posts/math/algebra/algebra-series-roadmap.md" >}}) — Bức tranh toàn cảnh kết nối 8 trạm dừng chân trong chuỗi bài.