Thuật toán Euclid mở rộng và Bổ đề Bézout

2026-Sep-14 1723 từ 9 phút

Nội dung

Trong số học và đại số trừu tượng, Đồng nhất thức Bézout (Bézout’s identity) — trong các giáo trình toán học tại Việt Nam phổ biến nhất thường được gọi là Định lý Bézout hoặc Bổ đề Bézout (Bézout’s lemma) — khẳng định rằng với hai số nguyên bất kỳ $a$ và $b$ không đồng thời bằng $0$, ước chung lớn nhất $d = \gcd(a, b)$ luôn biểu diễn được dưới dạng tổ hợp tuyến tính nguyên của $a$ và $b$:

$$d = ra + sb \quad (r, s \in \mathbb{Z}).$$

Để vừa tìm $\gcd(a, b)$ vừa xác định cặp hệ số Bézout $(r, s)$, cách làm trực quan và hệ thống nhất khi tính tay là lập bảng chia 4 cột ($b, a, r, q$) rồi áp dụng phương pháp thế ngược.

Nguyên lý bảng chia 4 cột ($b, a, r, q$)

$$b = a \cdot q + r \quad (0 \le r < a)$$

Bảng được thiết lập gồm 4 cột theo thứ tự:

$b$: Số bị chia (chọn $b > a$)
$a$: Số chia
$r$: Số dư ($r = b - a \cdot q$)
$q$: Thương nguyên ($q = \lfloor b / a \rfloor$)

Quy tắc cuốn chiếu giữa các dòng:

Số chia $a$ của dòng trước trở thành số bị chia $b$ của dòng sau ($b \leftarrow a$).
Số dư $r$ của dòng trước trở thành số chia $a$ của dòng sau ($a \leftarrow r$).
Lặp lại quá trình cho đến khi số dư $r = 0$.
Xác định $\gcd(a, b)$: Số dư khác $0$ cuối cùng (ở dòng ngay trước dòng có $r = 0$) chính là $\gcd(a, b)$.
Tìm hệ số Bézout: Sử dụng các đẳng thức $r = b - a \cdot q$ từ dưới lên bằng phương pháp thế ngược (back-substitution) để biểu diễn $\gcd(a, b)$ theo $a$ và $b$ ban đầu.

Đề bài

$$d = ra + sb.$$

Các bước thực hiện với $a = 14, b = 39$

Bước 1: Lập bảng chia 4 cột ($b, a, r, q$)

Xếp số lớn $b = 39$ và số nhỏ $a = 14$:

$b$	$a$	$r$	$q$
$\textcolor{#9B59B6}{39}$	$\textcolor{#FF4757}{14}$	$\textcolor{#1E90FF}{11}$	$2$
$\textcolor{#FF4757}{14}$	$\textcolor{#1E90FF}{11}$	$\textcolor{#2ECC71}{3}$	$1$
$\textcolor{#1E90FF}{11}$	$\textcolor{#2ECC71}{3}$	$\textcolor{#E67E22}{2}$	$3$
$\textcolor{#2ECC71}{3}$	$\textcolor{#E67E22}{2}$	$1$	$1$
$\textcolor{#E67E22}{2}$	$1$	$0$	$2$

Dòng 1: $\textcolor{#9B59B6}{39} = \textcolor{#FF4757}{14} \cdot 2 + \textcolor{#1E90FF}{11} \implies r = \textcolor{#1E90FF}{11}, q = 2$
Dòng 2: $\textcolor{#FF4757}{14} = \textcolor{#1E90FF}{11} \cdot 1 + \textcolor{#2ECC71}{3} \implies r = \textcolor{#2ECC71}{3}, q = 1$
Dòng 3: $\textcolor{#1E90FF}{11} = \textcolor{#2ECC71}{3} \cdot 3 + \textcolor{#E67E22}{2} \implies r = \textcolor{#E67E22}{2}, q = 3$
Dòng 4: $\textcolor{#2ECC71}{3} = \textcolor{#E67E22}{2} \cdot 1 + 1 \implies r = 1, q = 1$
Dòng 5: $\textcolor{#E67E22}{2} = 1 \cdot 2 + 0 \implies r = 0, q = 2$ (dừng lại vì số dư bằng $0$)

$$d = \gcd(14, 39) = 1.$$

Bước 2: Tìm hệ số Bézout bằng phương pháp thế ngược

Từ các dòng của bảng chia trên, ta biểu diễn số dư $r$ thành hiệu $b - a \cdot q$:

Từ dòng 4: $1 = \textcolor{#2ECC71}{3} - \textcolor{#E67E22}{2} \cdot 1$
Từ dòng 3: $\textcolor{#E67E22}{2} = \textcolor{#E67E22}{11 - 3 \cdot 3}$
Từ dòng 2: $\textcolor{#2ECC71}{3} = \textcolor{#2ECC71}{14 - 11 \cdot 1}$
Từ dòng 1: $\textcolor{#1E90FF}{11} = \textcolor{#1E90FF}{39 - 14 \cdot 2}$

Thế ngược lần lượt từ dưới lên (các số dư được tô màu tương ứng với cụm biểu thức thế):

$$\begin{aligned} 1 &= \textcolor{#2ECC71}{3} - \textcolor{#E67E22}{2} \cdot 1 \\ &= \textcolor{#2ECC71}{3} - \textcolor{#E67E22}{(11 - 3 \cdot 3)} \cdot 1 = 4 \cdot \textcolor{#2ECC71}{3} - 1 \cdot \textcolor{#1E90FF}{11} \\ &= 4 \cdot \textcolor{#2ECC71}{(14 - 11 \cdot 1)} - 1 \cdot \textcolor{#1E90FF}{11} = 4 \cdot \textcolor{#FF4757}{14} - 5 \cdot \textcolor{#1E90FF}{11} \\ &= 4 \cdot \textcolor{#FF4757}{14} - 5 \cdot \textcolor{#1E90FF}{(39 - 14 \cdot 2)} = 14 \cdot \textcolor{#FF4757}{14} - 5 \cdot \textcolor{#9B59B6}{39}. \end{aligned}$$$$1 = 14 \cdot (\textcolor{#FF4757}{14}) + (-5) \cdot (\textcolor{#9B59B6}{39}).$$

Kết luận bài toán:

$d = \gcd(14, 39) = 1$
Cặp hệ số Bézout tìm được: $r = 14, \quad s = -5$
Biểu diễn: $$1 = 14 \cdot (\textcolor{#FF4757}{14}) + (-5) \cdot (\textcolor{#9B59B6}{39}).$$

Tính không duy nhất của hệ số Bézout

Cặp hệ số Bézout $(r, s)$ không phải là duy nhất. Với nghiệm riêng tìm được $(r_0, s_0) = (14, -5)$, tập hợp tất cả các cặp nghiệm nguyên $(r, s)$ thỏa mãn $ra + sb = d$ có dạng:

$$r = r_0 + k \cdot \frac{b}{d} = 14 + 39k, \quad s = s_0 - k \cdot \frac{a}{d} = -5 - 14k \qquad (k \in \mathbb{Z}).$$

Ý nghĩa bản chất của Bổ đề Bézout

Việc biến một khẳng định về “ước số” thành một “tổ hợp tuyến tính” mang ý nghĩa cấu trúc sâu sắc trong số học và đại số trừu tượng, thể hiện rõ qua các khía cạnh sau:

1. Từ “quan hệ thụ động” sang “đẳng thức đại số chủ động”

Quan hệ chia hết ($d \mid a$ và $d \mid b$) chỉ là một mệnh đề kiểm tra (đúng hoặc sai). Ta không thể cộng, trừ, hay nhân hai vế của một quan hệ chia hết như một phương trình thông thường.
Tổ hợp tuyến tính ($d = ra + sb$) là một đẳng thức với dấu bằng ($=$). Khi đã có một đẳng thức, ta được quyền dùng toàn bộ công cụ của đại số:
- Nhân cả hai vế với một đại lượng bất kỳ.
- Chuyển vế, đổi dấu.
- Thế đại lượng này vào một phương trình khác.

2. $\gcd(a, b)$ là số nguyên dương nhỏ nhất tạo được từ $a$ và $b$

$$S = \{xa + yb > 0 \mid x, y \in \mathbb{Z}\}.$$

Theo Nguyên lý thứ tự tốt (Well-Ordering Principle), tập con khác rỗng $S \subset \mathbb{N}$ bắt buộc phải có một phần tử nhỏ nhất $d_{\min}$. Bổ đề Bézout chỉ ra hai kết quả nền tảng:

Phần tử cực tiểu $d_{\min}$ đó chính là $\gcd(a, b)$.
Mọi số nguyên có dạng $xa + yb$ bắt buộc phải là bội số của $d_{\min}$.

Nói cách khác, $\gcd(a, b)$ là mắt lưới cơ sở nhỏ nhất sinh ra toàn bộ các tổ hợp nguyên của $a$ và $b$.

3. Chìa khóa để chứng minh Bổ đề Euclid (Bản lề của Số học)

Hãy xem định lý nền tảng: “Nếu số nguyên tố $p$ chia hết tích $ab$, thì $p \mid a$ hoặc $p \mid b$.”
Nếu chỉ dùng định nghĩa “ước số”, ta hoàn toàn bế tắc vì không có cách nào tách rời $a$ và $b$ từ giả thiết $p \mid ab$.

Nhưng nhờ tổ hợp tuyến tính Bézout:

Nếu $p$ không chia hết $a$, thì $\gcd(p, a) = 1$.
Bézout cho phép ta viết: $rp + sa = 1$.
Bây giờ, chỉ cần nhân cả hai vế với $b$: $$rpb + sab = b$$
Nhìn vào vế trái: $p \mid rpb$ (hiển nhiên), và $p \mid sab$ (vì $p \mid ab$).
Do đó, $p$ chia hết toàn bộ vế trái $\implies p \mid b$.

Chứng minh chặt chẽ chỉ trong hai dòng. Không có tổ hợp tuyến tính này, ta không thể chứng minh được tính duy nhất của phân tích thừa số nguyên tố (Định lý cơ bản của số học).

4. Tìm “nghịch đảo nhân” trong số học Modulo (Nền tảng Mật mã học)

Trong tập số thực, muốn chia cho $a$ ta nhân với $\frac{1}{a}$ (vì $a \cdot a^{-1} = 1$). Nhưng trong vành đồng dư $\mathbb{Z}_m$ (chỉ gồm các số nguyên dư), không tồn tại phân số.

Làm thế nào để tìm một số nguyên $x$ đóng vai trò là “nghịch đảo” của $a$ modulo $m$ ($ax \equiv 1 \pmod m$)?

Bézout khẳng định: Nếu $\gcd(a, m) = 1$, thì tồn tại $r, s \in \mathbb{Z}$ sao cho: $$ra + sm = 1$$
Lấy modulo $m$ cả hai vế: $$ra + 0 \equiv 1 \pmod m \iff r \cdot a \equiv 1 \pmod m$$
Như vậy, hệ số Bézout $r$ chính là nghịch đảo modulo $a^{-1} \pmod m$.

Đây chính là thuật toán lõi để tính khóa giải mã trong hệ mật mã khóa công khai RSA và giao thức trao đổi khóa Diffie-Hellman đang bảo vệ an ninh Internet ngày nay.

5. Giải quyết trọn vẹn phương trình Diophantine tuyến tính

$$ax + by = c$$

Phương trình này có nghiệm nguyên khi nào và giải ra sao?

Nhờ biểu diễn tuyến tính, vế trái $ax + by$ luôn là bội của $d = \gcd(a, b)$. Do đó, phương trình có nghiệm khi và chỉ khi $d \mid c$.
Khi điều kiện thỏa mãn ($c = k \cdot d$), từ nghiệm Bézout cơ sở $ra + sb = d$, ta nhân $k$ vào hai vế để có ngay một nghiệm riêng cụ thể: $$(x_0, y_0) = (kr, ks)$$

6. Ý nghĩa hình học và cấu trúc đại số trừu tượng (Vành I-đê-an chính - PID)

Mạng lưới điểm nguyên (Lattice): Biểu thức $xa + yb$ mô tả toàn bộ mạng lưới các điểm nguyên tạo bởi $a$ và $b$ trên trục số. Toàn bộ mạng lưới vô hạn đó thực chất chỉ là các bội số nguyên của một mắt lưới cơ sở nhỏ nhất là $d = \gcd(a, b)$.
Cầu nối sang Đại số hiện đại: Trong vành số nguyên $\mathbb{Z}$, tập hợp các tổ hợp nguyên lập thành i-đê-an $\langle a, b \rangle = {xa + yb \mid x, y \in \mathbb{Z}}$. Bổ đề Bézout khẳng định $\langle a, b \rangle = \langle \gcd(a, b) \rangle$, chứng minh $\mathbb{Z}$ là một Vành I-đê-an chính (Principal Ideal Domain - PID).

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

🗺️ Bản đồ chuỗi bài viết Đại số: Từ Thứ tự tốt đến Bổ đề Bézout và Vành PID: Tổng quan lộ trình và mối liên hệ giữa các bài viết trong chuỗi.
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): Mô hình hóa bước nhảy trên trục số và cấu trúc PID của vành số nguyên.
Hai số nguyên tố cùng nhau: Chiều đảo Bổ đề Bézout và Tính đối xứng của hệ số: Đặc trưng tương đương $ar + bs = 1 \iff \gcd(a, b) = 1$ và tính nguyên tố cùng nhau của các cặp hệ số.
Nguyên lý thứ tự tốt và phép chứng minh Quy nạp Toán học: Cơ sở xác lập phần tử đáy cực tiểu của các tập con số tự nhiên.