Máy Tính UCLN Bằng Thuật Toán Euclid

Nhập phép tính

Số thứ nhất

Số thứ hai

Kết quả

https://example.com

Ước số chung lớn nhất

4

UCLN (còn gọi là GCF/GCD)

Solution — Euclid's Algorithm

Step 1: 2260 ÷ 816 = 2 R 628   (2260 = 2 × 816 + 628)
Step 2: 816 ÷ 628 = 1 R 188   (816 = 1 × 628 + 188)
Step 3: 628 ÷ 188 = 3 R 64   (628 = 3 × 188 + 64)
Step 4: 188 ÷ 64 = 2 R 60   (188 = 2 × 64 + 60)
Step 5: 64 ÷ 60 = 1 R 4   (64 = 1 × 60 + 4)
Step 6: 60 ÷ 4 = 15 R 0   (60 = 15 × 4 + 0)

Thuật toán Euclid là gì?

Ước số chung lớn nhất (UCLN), trong tiếng Anh gọi là GCF hay GCD, là số nguyên lớn nhất chia hết cho cả hai số đã cho. Thuật toán Euclid là một phương pháp cổ xưa nhưng cực kỳ hiệu quả để tìm ra giá trị này bằng cách chia có dư lặp đi lặp lại. Công cụ này trả về UCLN của hai số nguyên bất kỳ và trình bày từng bước chia để bạn dễ dàng theo dõi cách giải.

Thuật toán Euclid lát hình chữ nhật bằng các hình vuông bằng nhau lớn nhất có thể — cạnh hình vuông đó chính là ƯCLN.

Cách sử dụng

Nhập hai số nguyên vào ô Số thứ nhất và Số thứ hai. Công cụ sẽ lấy số lớn làm số bị chia và số nhỏ làm số chia, rồi chia liên tục cho đến khi số dư bằng 0. Số chia khác 0 cuối cùng chính là UCLN. Thứ tự nhập không quan trọng và dấu âm sẽ được bỏ qua, vì UCLN chỉ phụ thuộc vào giá trị tuyệt đối của hai số.

Giải thích công thức

Ở mỗi bước, bạn tính thương và số dư theo công thức: \(a = c \times b + R\), trong đó \(c = \lfloor a / b \rfloor\) (phần nguyên của phép chia) và \(R = a \bmod b\) (số dư). Sau đó, bạn thay \(a\) bằng \(b\), thay \(b\) bằng \(R\) rồi lặp lại. Vì mỗi số dư luôn nhỏ hơn số chia trước đó, quá trình này chắc chắn sẽ dừng lại. Khi \(R = 0\), số chia hiện tại chính là đáp án. Viết dưới dạng đệ quy: $$\gcd(a, b) = \gcd(b, a \bmod b),\quad \gcd(a, 0) = a$$

Quảng cáo

Ví dụ minh họa

Tìm UCLN(816, 2260). Đặt \(a = 2260\), \(b = 816\).

$$2260 = 2 \times 816 + 628$$ $$816 = 1 \times 628 + 188$$ $$628 = 3 \times 188 + 64$$ $$188 = 2 \times 64 + 60$$ $$64 = 1 \times 60 + 4$$ $$60 = 15 \times 4 + 0$$ Số dư bằng 0 khi số chia là 4, vậy UCLN(816, 2260) = 4.

Mỗi bước thay (a, b) bằng (b, a mod b) cho đến khi số dư bằng 0; ước số khác 0 cuối cùng là ƯCLN.

Câu hỏi thường gặp

GCF và GCD có giống nhau không? Có. "Greatest common factor" và "greatest common divisor" là hai cách gọi của cùng một khái niệm, đều tương ứng với UCLN trong tiếng Việt; công cụ này cho ra kết quả như nhau cho cả hai.

Nếu một số nhập vào bằng 0 thì sao? \(\gcd(a, 0) = a\), vì mọi số đều chia hết cho 0. Nếu cả hai số đều bằng 0 thì UCLN không xác định.

Tôi có thể tìm UCLN của ba số được không? Hãy áp dụng công cụ theo từng cặp: \(\gcd(x, y, z) = \gcd(\gcd(x, y), z)\).