Thuật toán Euclide

Thuật toán Euclide

Thuật toán Euclide tìm ước số chung lớn nhất (gcd) của hai số \(a\) và \(b\).

Ước chung lớn nhất là số lớn nhất chia cả \(a\) và \(b\) mà không để lại số dư.

Thuật toán sử dụng phép chia có số dư. Phần còn lại của bước trước sẽ được sử dụng để thiết lập phép tính ở bước tiếp theo.

Tiếp tục đọc để biết thuật toán Euclide có thể được thực hiện bằng tay như thế nào, bằng cách lập trình, cũng như hiểu cách thức và lý do thuật toán thực sự hoạt động.

Thuật ngữ toán học

Dưới đây là những từ dùng để mô tả Thuật toán Euclide mà bạn cần biết để hiểu những lời giải thích trên trang này.

Số chia: Một số chúng ta có thể dùng để chia một số cho mà không để lại số dư. Chúng ta nói rằng 3 là ước của 6 vì \(6/3=2\), không để lại số dư (số dư là 0).

Phần dư: Phần còn lại sau khi chia một số với một số khác. Chia 7 cho 3 được 2, dư 1. (Vậy 3 không phải là ước của 7.)

Ước chung: Đối với các số \(a\) và \(b\), ước số chung là số có thể chia cả \(a\) và \(b\) mà không để lại số dư. Ước chung của 18 và 12 là 2, 3 và 6, vì cả 18 và 12 đều có thể chia hết cho 2, 3 và 6 mà không có số dư.

Ước chung lớn nhất: Ước chung lớn nhất. Ước chung lớn nhất của 18 và 12 là 6 vì đó là ước chung lớn nhất của 2, 3 và 6.

Ước chung lớn nhất được sử dụng trong lĩnh vực toán học của Lý thuyết số và trong mật mã để mã hóa tin nhắn.

Chạy qua thủ công

Để hiểu cách hoạt động của thuật toán Euclide và viết mã cho nó, trước tiên chúng ta hãy chạy thủ công để tìm ước chung lớn nhất của \(120\) và \(25\).

Để làm điều này, chúng tôi sử dụng phép chia với số dư.

Bước 1: Chúng ta bắt đầu chia \(120\) cho \(25\):

\[ \begin{equation} \begin{aligned} 120 & = 4 \cdot 25 + 20 \end{aligned} \end{equation} \]

Chúng ta có thể nhét \(25\) vào trong \(120\) bao nhiêu lần? Đó là \(4\) lần, phải không? \(4 \cdot 25\) là \(100\). Chúng ta lấy phần còn lại \(20\) bằng cách trừ \(100\) từ \(120\).

Bước 2: Ta dùng số dư \(20\) ở bước tiếp theo để chia \(25\):

\[ \begin{equation} \begin{aligned} 25 & = 1 \cdot 20 + 5 \end{aligned} \end{equation} \]

Chúng ta có thể nhét \(20\) vào bên trong \(25\) một lần. Chúng ta lấy phần còn lại \(5\) bằng cách trừ \(20\) từ \(25\).

Bước 3: Trong phép tính tiếp theo chúng ta chia \(20\) cho số dư trước đó \(5\):

\[ \begin{equation} \begin{aligned} 20 & = 4 \cdot 5 + 0 \end{aligned} \end{equation} \]

Chúng tôi nhận được \(0\) là phần còn lại và điều đó có nghĩa là chúng tôi đã hoàn tất việc tính toán.

Ước chung lớn nhất của \(120\) và \(25\) là \(5\).

Thực hiện thuật toán Euclide

Để tìm ước chung lớn nhất bằng phép chia, ta tiếp tục chạy thuật toán cho đến khi số dư được tính là \(0\).

Điều này cũng giống như việc nói rằng chúng ta tiếp tục chạy thuật toán miễn là \(b\) không phải là \(0\). Đó là lý do tại sao b != 0 là điều kiện trong vòng lặp while bên dưới.

 def gcd_division(a, b):
    while b != 0:
        remainder = a % b
        print(f"{a} = {a//b} * {b} + {remainder}")
        a = b
        b = remainder
    return a

a = 120
b = 25
print("The Euclidean algorithm using division:\n")
print(f"The GCD of {a} and {b} is: {gcd_division(a, b)}")

Thuật toán Euclide gốc

Thay vì sử dụng phép chia như chúng tôi đã làm ở trên, thuật toán Euclide ban đầu được mô tả trong cuốn sách “Các phần tử” hơn 2000 năm trước lại sử dụng phép trừ.

Sử dụng phép trừ thay vì phép chia không nhanh bằng, nhưng cả phương pháp chia và phương pháp trừ đều sử dụng cùng một nguyên tắc toán học:

Điều này có thể được hiển thị chỉ trong một vài dòng.

Các số \(a\) và \(b\) có ước chung lớn nhất \(x\).

Điều này có nghĩa là cả \(a\) và \(b\) đều có thể được phân tích thành thừa số như thế này:

\[ \begin{equation} \begin{aligned} a & = k \cdot x \\ b & = l \cdot x \end{aligned} \end{equation} \]

Sau khi nhân tử hóa, việc trừ \(b\) khỏi \(a\) cho chúng ta một kết quả rất thú vị:

\[ \begin{equation} \begin{aligned} ab & = k \cdot x - l \cdot x \\ & = (kl) \cdot x \end{aligned} \end{equation} \]

Chúng ta có thể thấy rằng ước chung lớn nhất (\(x\)) của \(a\) và \(b\) cũng là ước chung lớn nhất của chênh lệch giữa \(a\) và \(b\)!

Nguyên tắc này là lý do tại sao thuật toán Euclide hoạt động và nó là điều khiến thuật toán này trở nên khả thi.

Tìm ước chung lớn nhất bằng phép trừ

Sử dụng nguyên tắc được mô tả ở trên, rằng hiệu giữa \(a\) và \(b\) cũng có cùng ước số chung lớn nhất, chúng ta có thể sử dụng phép trừ để tìm ước số chung lớn nhất, giống như thuật toán ban đầu của Euclid.

Hãy tìm ước chung lớn nhất của \(120\) từ \(25\) bằng phép trừ.

\[ \begin{equation} \begin{aligned} 120 - 25 & = 95 \end{aligned} \end{equation} \]

Theo nguyên tắc toán học đã được mô tả, các số \(120\), \(25\) và \(95\) đều có chung ước số chung lớn nhất.

Điều này có nghĩa là chúng ta có thể giảm bớt vấn đề của mình hơn nữa bằng cách trừ \(25\) khỏi \(95\):

\[ \begin{equation} \begin{aligned} 95 - 25 & = 70 \end{aligned} \end{equation} \]

Nếu chúng ta tiếp tục như vậy, luôn lấy hai số thấp nhất từ ​​bước trước và tìm sự khác biệt giữa chúng, chúng ta sẽ có được các phép tính sau:

\[ \begin{equation} \begin{aligned} 70 - 25 & = 45 \\ 45 - 25 & = 20 \\ 25 - 20 & = 5 \\ 20 - 5 & = 15 \\ 15 - 5 & = 10 \\ 10 - 5 & = \underline{\textbf{5}} \\ 5 - 5 & = 0 \end{aligned} \end{equation} \]

Thuật toán Euclide sử dụng phép trừ được thực hiện khi chênh lệch là \(0\).

Ước chung lớn nhất của \(120\) và \(25\) có thể được tìm thấy ở bước trước, đó là \(5\).

Bây giờ chúng ta có thể tính ước chung lớn nhất bằng phép trừ bằng tay, việc triển khai nó bằng ngôn ngữ lập trình sẽ dễ dàng hơn.

Thực hiện thuật toán Euclide bằng phép trừ

Để tìm ước chung lớn nhất bằng phép trừ, chúng ta tiếp tục chạy thuật toán cho đến khi hiệu giữa \(a\) và \(b\) là \(0\), như chúng ta vừa thấy.

Điều này cũng giống như việc nói rằng chúng ta tiếp tục chạy thuật toán miễn là \(a\) và \(b\) là các giá trị khác nhau. Đó là lý do tại sao a != b là điều kiện trong vòng while bên dưới.

 def gcd_subtraction(a, b):
    while a != b:
        if a > b:
            print(f"{a} - {b} = {a-b}")
            a = a - b
        else:
            print(f"{b} - {a} = {b-a}")
            b = b - a
    return a

a = 120
b = 25
print("The Euclidean algorithm using subtraction:\n")
print(f"The GCD of {a} and {b} is: {gcd_subtraction(a, b)}")

So sánh phương pháp trừ với phương pháp chia

Để xem phương pháp chia có thể tốt như thế nào để tìm ước chung lớn nhất và các phương pháp này giống nhau như thế nào, chúng ta sẽ:

1. Sử dụng phép trừ để tìm ước chung lớn nhất của \(120\) và \(25\).
2. Sử dụng phép chia có số dư để tìm ước chung lớn nhất của \(120\) và \(25\).
3. So sánh các phương pháp trừ và chia.

1. Sử dụng phép trừ

Tìm ước chung lớn nhất của \(120\) và \(25\) bằng phép trừ:

\[ \begin{equation} \begin{aligned} 120 - 25 & = 95 \\ 95 - 25 & = 70 \\ 70 - 25 & = 45 \\ 45 - 25 & = 20 \\ 25 - 20 & = 5 \\ 20 - 5 & = 15 \\ 15 - 5 & = 10 \\ 10 - 5 & = \underline{\textbf{5}} \\ 5 - 5 & = 0 \end{aligned} \end{equation} \]

Sử dụng phép trừ, thuật toán kết thúc khi chênh lệch là \(0\).

Trong phép tính cuối cùng thứ hai, chúng ta thấy rằng ước chung lớn nhất của \(120\) và \(25\) là \(5\).

Lưu ý cách \(25\) và \(5\) phải được trừ đi nhiều lần cho đến khi tìm thấy GCD.

2. Sử dụng phép chia

Tìm ước chung lớn nhất của \(120\) và \(25\) bằng phép chia có số dư như sau:

\[ \begin{equation} \begin{aligned} 120 & = 4 \cdot 25 + 20 \\ 25 & = 1 \cdot 20 + \underline{\textbf{5}} \\ 20 & = 4 \cdot 5 + 0 \end{aligned} \end{equation} \]

Sử dụng phép chia, thuật toán Euclide kết thúc khi phần còn lại là \(0\).

Số dư trước đó \(5\) là ước số chung lớn nhất của \(120\) và \(25\).

3. So sánh

Hãy xem các phương pháp trừ và chia ở trên.

Để dễ dàng nhận thấy phép tính chia về cơ bản giống như phép tính trừ, chúng ta có thể viết phép chia có số dư như sau:

\[ \begin{equation} \begin{aligned} 120 - 4 \cdot 25 & = 20 \\ 25 - 1 \cdot 20 & = \underline{\textbf{5}} \\ 20 - 4 \cdot 5 & = 0 \end{aligned} \end{equation} \]

Bằng cách sử dụng phép trừ, \(25\) được trừ khỏi \(120\) tổng cộng \(4\) lần, trong khi phương pháp chia thực hiện điều này chỉ trong một bước.

Tương tự, phương pháp trừ trừ \(5\) tổng cộng \(4\) lần, trong khi phương pháp chia thực hiện tương tự chỉ trong một phép tính.

Như bạn có thể thấy, các phương thức thực hiện điều tương tự, phương pháp chia chỉ thực hiện nhiều phép trừ trong cùng một phép tính, để tìm ước chung lớn nhất nhanh hơn.