1. Phép chia Euclid. Thuật toán Euclid

1.1. Phép chia Euclid

Đây là nền tảng, cơ sở của số học. Từ khi biết tới phép chia hai số nguyên, ta có thể tìm thương và số dư. Nói theo toán học, nếu ta có hai số nguyên dương \(a\) và \(b\) thì tồn tại cặp số \(q\), \(r\) sao cho \(a = qb + r\) với \(0 \leqslant r < b\).

Khi đó, \(a\) gọi là số bị chia, \(b\) gọi là số chia, \(q\) là thương (q trong quotient) và \(r\) là số dư (r trong remainder).

Đặc biệt, sự tồn tại của cặp số \(q\) và \(r\) là duy nhất. Thật vậy, nếu ta giả sử tồn tại hai cặp số \((q_1, r_1)\) và \((q_2, r_2)\) đều thỏa đẳng thức trên, nghĩa là

\[a = q_1 b + r_1, \quad a = q_2 b + r_2.\]

Trừ hai đẳng thức vế theo vế ta có

\[(q_1 - q_2) b + (r_1 - r_2) = 0,\]

tương đương \((r_2 - r_1) = (q_1 - q_2) b\), mà \(0 \leqslant r_1, r_2 < b\) nên \(-b < r_2 - r_1 < b\).

Như vậy chỉ có thể xảy ra trường hợp \(r_2 - r_1 = 0\) (vì giá trị tuyệt đối của vế phải là bội của \(b\) nên sẽ lớn hơn \(b\), còn vế trái lại có giá trị tuyệt đối nhỏ hơn \(b\)) hay \(r_2 = r_1\), kéo theo \(q_1 = q_2\).

1.2. Thuật toán Euclid

Dựa trên phép chia Euclid, ta có một thuật toán hiệu quả để tìm ước chung lớn nhất giữa hai số \(a\) và \(b\).

Kí hiệu \(\gcd(a, b)\) là ước chung lớn nhất của \(a\) và \(b\). Chúng ta thực hiện đệ quy như sau:

\[\begin{split}\gcd(a, b) = \begin{cases} a, \ & \text{nếu} \, b = 0 \\ \gcd(b, a \bmod b), \ & \text{nếu} \, b \neq 0. \end{cases}\end{split}\]

Điểm quan trọng ở thuật toán Euclid là thuật toán chắc chắn sẽ dừng sau một số hữu hạn bước, và kết quả sẽ là ước chung lớn nhất của hai số \(a\) và \(b\).

Chứng minh

Đặt \(r_0 = a\) và \(r_1 = b\). Theo phép chia Euclid tồn tại các số \(q_0\) và \(r_2\) sao cho \(r_0 = r_1 q_0 + r_2\) với \(0 \leqslant r_2 < r_1\).

Trong thuật toán Euclid, ở bước thứ \(i\) (\(i = 1, 2, \ldots\)) vì đã biết \(r_i\) và \(r_{i+1}\) nên ta tìm được thương \(q_i\) và số dư \(r_{i+2}\) trong phép chia \(r_i\) cho \(r_{i+1}\).

\[\begin{split}r_0 & = r_1 q_0 + r_2 \\ r_1 & = r_2 q_1 + r_3 \\ r_2 & = r_3 q_2 + r_4 \\ \ldots & = \ldots \\ r_i & = r_{i+1} q_i + r_{i+2} \\ \ldots & = \ldots \\ r_k & = r_{k+1} q_k + 0 \\\end{split}\]

Ở mỗi bước, \(r_{i+2}\) luôn nhỏ hơn \(r_{i+1}\). Do đó cuối cùng sẽ bằng \(0\), và khi đó ta có ước chung lớn nhất là \(r_{k+1}\) như trên.

Ví dụ 1.29

Tìm ước chung lớn nhất của \(784\) và \(74\).

\[\begin{split}\begin{array}{ccccc} r_i & = & r_{i+1} \cdot q_i & + & r_{i+2} \\ 784 & = & {\color{red}{74}} \cdot 10 & + & {\color{blue}{44}} \\ {\color{red}74} & = & {\color{blue}{44}} \cdot 1 & + & {\color{green}{30}} \\ {\color{blue}{44}} & = & {\color{green}{30}} \cdot 1 & + & {\color{magenta}{14}} \\ {\color{green}{30}} & = & {\color{magenta}{14}} \cdot 2 & + & {\color{orange}{2}} \\ {\color{magenta}{14}} & = & {\color{orange}{2}} \cdot 7 & + & {\boxed{\color{purple}{0}}} \end{array}\end{split}\]

Vậy \(\gcd(784, 74) = 2\).

1.3. Thuật toán Euclid mở rộng

Định nghĩa 1.59 (Phương trình Diophantus)

Cho trước các số nguyên \(a\), \(b\) và \(c\). Phương trình Diophantus là phương trình có dạng

\[ax + by = c\]

với \(x\), \(y\) là các số nguyên.

Ví dụ 1.30

Giải phương trình \(5x+3y = 1\).

Ta có

\[y = \dfrac{1-5x}{3} = \dfrac{1-2x-3x}{3} = \dfrac{1-2x}{3} - x.\]

Như vậy nếu \(y \in \mathbb{Z}\) thì \(\dfrac{1-2x}{3} \in \mathbb{Z}\), nghĩa là \(1-2x\) chia hết cho \(3\). Vậy \(1-2x = 3k\) với \(k \in \mathbb{Z}\).

Tiếp tục, \(1-2x = 3k\), suy ra

\[x = \dfrac{1-3k}{2} = \dfrac{1-k-2k}{2} = \dfrac{1-k}{2} - k.\]

Do \(x\) nguyên nên tương tự \(\dfrac{1-k}{2}\) cũng nguyên, hay \(1-k = 2t\), tương đương với \(k = 1-2t\).

Thay ngược lại ta có

\[x = \dfrac{1-3k}{2} = \dfrac{1-3(1-2t)}{2} = {-1+3t}.\]

Tiếp tục thay vào để tìm \(y\) thì

\[y = \dfrac{1-5x}{3} = \dfrac{1-5(-1+3t)}{3} = 2 - 5t.\]

Như vậy nghiệm của phương trình là tất cả các nghiệm \((x, y)\) mà \(x = -1+3t\), \(y = 2-5t\) với \(t \in \mathbb{Z}\).

Ở đây chúng ta đã thực hiện phép chia có dư liên tiếp để tìm nghiệm. Nói cách khác ta đã thực hiện thuật toán Euclid ở bên trên để làm giảm độ phức tạp ở mỗi bước giải.

Tổng quát ta có thuật toán Euclid mở rộng để tìm ước chung lớn nhất \(\gcd(a, b)\) của hai số \(a\), \(b\), và một nghiệm của phương trình \(ax + by = \gcd(a, b)\).

Ở ví dụ trên, ta đã tìm được một nghiệm của phương trình \(5x + 3y = 1\) là \((-1, 2)\) khi \(t = 0\). Khi đó ta có thể suy ra tất cả nghiệm (họ nghiệm) của phương trình có dạng \((-1+3t, 2-5t)\) với \(t \in \mathbb{Z}\).

Thuật toán 1.1 (Thuật toán Euclid mở rộng)

Input: \(a, b \in \mathbb{Z}\)

Output: \(\gcd(a, b)\), \(x\), \(y\)

1. \(r_0 \gets a\), \(r_1 \gets b\), \(r_2 \gets 0\)

2. \(x_0 \gets 1\), \(x_1 \gets 0\), \(x_2 \gets 0\)

3. \(y_0 \gets 0\), \(y_1 \gets 1\), \(y_2 \gets 0\)

4. While \(r_1 \neq 0\)

   1. \(q \gets r_0 \;\text{div}\; r_1\)

   2. \(r_2 \gets r_0 - q * r_1\), \(r_0 \gets r_1\), \(r_1 \gets r_2\)

   3. \(x_2 \gets x_0 - q * x_1\), \(x_0 \gets x_1\), \(x_1 \gets x_2\)

   4. \(y_2 \gets y_0 - q * y_1\), \(y_0 \gets y_1\), \(y_1 \gets y_2\)

5. EndWhile

6. Return \(r_0\), \(x_0\), \(y_0\)

Ở thuật toán trên, \(r_0\), \(r_1\) và \(r_2\) hoạt động như thuật toán Euclid chuẩn.

Ở mỗi bước, \(q\) là thương của phép chia \(r_0\) cho \(r_1\), và ta sử dụng \(q\) đó để tính \(x_0\) và \(y_0\) mới. Kết quả cuối cùng \((r_0, x_0, y_0)\) lần lượt là ước chung lớn nhất \(r_0\), và hai số \(x_0\), \(y_0\) thỏa mãn \(a x_0 + y b_0 = r_0\).

Tại sao chúng ta lại có \((x_0, x_1) = (1, 0)\) và \((y_0, y_1) = (0, 1)\)? Thêm nữa, làm sao biết thuật toán hoạt động đúng?

Mục đích của chúng ta là tìm các số \((x, y)\) sao cho \(ax + by = \gcd(a, b)\). Khi đó, dựa trên thuật toán Euclid cơ bản ở trên, ta xây dựng dãy số \(\{ x_n \}\) và \(\{ y_n \}\) sao cho ở mọi bước thứ \(n\) ta đều có

(1.3)\[a x_n + b y_n = r_n.\]

Từ thuật toán Euclid, với \(r_i\) và \(r_{i+1}\) ở bước thứ \(i\) ta thực hiện phép chia Euclid \(r_i = r_{i+1} q_i + r_{i+2}\) để tìm \(q_i\) và \(r_{i+2}\). Từ \(q_i\) ở mỗi bước ta tính

\[x_{i+2} = x_i - x_{i+1} q_i, \quad y_{i+2} = y_i - y_{i+1} q_i.\]

Chuyển vế hai phương trình trên ta có

\[x_i = x_{i+1} q_i + x_{i+2}, \quad y_i = y_{i+1} q_i + y_{i+2}.\]

Nếu thay hai phương trình vừa rồi vào (1.3) ta được

\[a (x_{i+1} q_i + x_{i+2}) + b (y_{i+1} q_i + y_{i+2}) = r_i,\]

tương đương với

\[(a x_{i+1} + b y_{i+1}) \cdot q_i + (a x_{i+2} + b x_{i+2}) = r_i.\]

Do

\[a x_{i+1} + b y_{i+1} = r_{i+1}, \quad a x_{i+2} + b y_{i+2} = r_{i+2},\]

nên \(r_{i+1} q_i + r_{i+2} = r_i\), đúng với thuật toán Euclid chuẩn ban đầu. Như vậy thuật toán mở rộng hoạt động đúng.

Bây giờ ta cần chọn \((x_0, x_1)\) và \((y_0, y_1)\) vì chúng ta đã đặt \(r_0 = a\) và \(r_1 = b\).

Ở bước thứ \(0\), vì

\[r_0 = a = a x_0 + b y_0,\]

và ở bước thứ \(1\),

\[r_1 = b = a x_1 + b y_1.\]

Dễ thấy ở bước \(0\) ta chọn \(x_0 = 1\) và \(x_1 = 0\), còn ở bước \(1\) ta chọn \(y_0 = 0\) và \(y_1 = 1\) là được.

Ví dụ 1.31

Tìm một nghiệm nguyên của phương trình \(784 x + 74 y = 2\).

\[\begin{split}\begin{array}{ccccc|ccccc|ccccc} r_i & = & r_{i+1} \cdot q_i & + & r_{i+2} & x_{i+2} & = & x_i & - & x_{i+1} \cdot q_i & y_{i+2} & = & y_i & - & y_{i+1} \cdot q_i \\ 784 & = & {\color{red}{74}} \cdot 10 & + & {\color{blue}{44}} & {\color{blue}1} & = & 1 & - & {\color{red}0} \cdot 10 & {\color{blue}-10} & = & 0 & - & {\color{red}1} \cdot 10 \\ {\color{red}74} & = & {\color{blue}{44}} \cdot 1 & + & {\color{green}{30}} & {\color{green}-1} & = & {\color{red}0} & - & {\color{blue}1} \cdot 1 & {\color{green}11} & = & {\color{red}1} & - & {\color{blue}(-10)} \cdot 1 \\ {\color{blue}{44}} & = & {\color{green}{30}} \cdot 1 & + & {\color{magenta}{14}} & {\color{magenta}2} & = & {\color{blue}1} & - & {\color{green}(-1)} \cdot 1 & {\color{magenta}-21} & = & {\color{blue}-10} & - & {\color{green}11} \cdot 1 \\ {\color{green}{30}} & = & {\color{magenta}{14}} \cdot 2 & + & {\color{orange}{2}} & {\color{orange}-5} & = & {\color{green}(-1)} & - & {\color{magenta}2} \cdot 2 & {\color{orange}53} & = & {\color{green}11} & - & {\color{magenta}(-21)} \cdot 2\\ {\color{magenta}{14}} & = & {\color{orange}{2}} \cdot 7 & + & {\boxed{\color{purple}{0}}} \end{array}\end{split}\]

Các bạn có thể thấy ước chung lớn nhất là số màu cam. Do đó các số \(x_{i+2}\) và \(y_{i+2}\) cũng chính là điểm dừng và mình không cần tính toán thêm.

Như vậy một nghiệm của phương trình \(784 x + 74 y = 2\) là \((-5, 53)\).

Chúng ta cũng có một cách trình bày khác để giải phương trình nghiệm nguyên trên là sử dụng biến đổi tương đương của ma trận.

Ví dụ, để tìm một nghiệm nguyên \((x, y)\) của phương trình \(a x + b y = c\) với \(a\), \(b\), \(c\) là các số cho trước, chúng ta viết ma trận

\[\begin{split}\left(\begin{array}{cc|c} 1 & 0 & a \\ 0 & 1 & b \end{array}\right)\end{split}\]

và biến đổi tương đương về dạng

\[\begin{split} \left(\begin{array}{cc|c} * & * & c \\ * & * & 0 \end{array}\right)\end{split}\]

Khi đó hai số ở hàng trên sẽ là nghiệm cần tìm.

Ví dụ 1.32

Sử dụng bài toán ở trên làm ví dụ: tìm một nghiệm nguyên của phương trình \(784 x + 74 y = 2\).

\[\begin{split}\left(\begin{array}{cc|c} 1 & 0 & 784 \\ 0 & 1 & 74 \end{array}\right) \sim \left(\begin{array}{cc|c} {\color{blue}1} & {\color{blue}-10} & {\color{blue}44} \\ 0 & 1 & 74 \end{array}\right) \sim \left(\begin{array}{cc|c} {\color{blue}1} & {\color{blue}-10} & {\color{blue}44} \\ {\color{green}-1} & {\color{green}11} & {\color{green}30} \end{array}\right) \\ \sim \left(\begin{array}{cc|c} {\color{magenta}2} & {\color{magenta}-21} & {\color{magenta}14} \\ {\color{green}-1} & {\color{green}11} & {\color{green}30} \end{array}\right) \sim \left(\begin{array}{cc|c} {\color{magenta}2} & {\color{magenta}-21} & {\color{magenta}14} \\ {\color{orange}-5} & {\color{orange}53} & {\color{orange}2} \end{array}\right) \sim \left(\begin{array}{cc|c} 37 & -392 & 0 \\ {\color{orange}-5} & {\color{orange}53} & {\color{orange}2} \end{array}\right)\end{split}\]

Về bản chất thì hai cách trình bày là giống nhau.

1.4. Bài tập sưu tầm

Câu 1 (đề kiểm tra, ITMO). Tính

\[\gcd(61^{610} + 1, 61^{671} - 1).\]

Mình thay \(61\) bởi biến \(x\) và thực hiện phép chia đa thức theo thuật toán Euclid.

Đầu tiên, xét phép chia \(x^{671} - 1\) cho \(x^{610} + 1\). Kết quả phép chia là

\[x^{671} - 1 = (x^{610} + 1) \cdot x^{61} - x^{61} - 1.\]

Tiếp theo, xét phép chia \(x^{610} + 1\) cho \(-x^{61} - 1\). Kết quả là

\[x^{610} + 1 = (-x^{61} - 1) \cdot (-x^{549} + x^{488} - \cdots + 1) + 2.\]

Như vậy, ước chung lớn nhất của hai đa thức là \(2\).

Câu 2 (đề kiểm tra, ITMO). Chứng minh rằng với mọi \(a, b, c \in \mathbb{N}\) thì

\[[a, b, c] = \frac{a \cdot b \cdot c \cdot (a, b, c)}{(a, b) \cdot (a, c) \cdot (b, c)},\]

trong đó

• \([a, b, c]\) là bội chung nhỏ nhất của ba số \(a\), \(b\), \(c\)

• \((a, b, c)\) là ước chung lớn nhất của ba số \(a\), \(b\), \(c\)

• \((a, b)\) là ước chung lớn nhất của hai số \(a\), \(b\).

Chưa làm ra.

Câu 3 (đề kiểm tra, ITMO). Tìm ít nhất một nghiệm nguyên của phương trình

\[311 x - 28 y = 2.\]

Sử dụng thuật toán Euclid:

\[\begin{split}& \left(\begin{array}{cc|c} 1 & 0 & 311 \\ 0 & 1 & -28 \end{array}\right) \stackrel{(1) \to (1) + 11 \cdot (2)}{\sim} \left(\begin{array}{cc|c} 1 & 11 & 3 \\ 0 & 1 & -28 \end{array}\right) \stackrel{(2) \to (2) + 10 \cdot (1)}{\sim} \left(\begin{array}{cc|c} 1 & 11 & 3 \\ 10 & 111 & 2 \end{array}\right) \\ \stackrel{(1) \to (1) - (2)}{\sim} & \left(\begin{array}{cc|c} -9 & -100 & 1 \\ 10 & 111 & 2 \end{array}\right) \stackrel{(2) \to (2) - 2 \cdot (1)}{\sim} \left(\begin{array}{cc|c} -9 & -100 & 1 \\ 28 & 311 & 0 \end{array}\right)\end{split}\]

Như vậy mình có \((-9, -100)\) là một nghiệm của phương trình

\[311 x - 28 y = 1.\]

Từ đó suy ra một nghiệm của phương trình

\[311 x - 28 y = 2\]

là \((2 \cdot (-9), 2 \cdot (-100)) = (-18, -200)\).