Tài liệu học tập: Thuật toán Euclid tìm UCLN

1. Giới thiệu

Ước chung lớn nhất (UCLN) của hai số nguyên $a$ và $b$ là số nguyên dương lớn nhất chia hết cả $a$ và $b$. Việc tìm UCLN có nhiều ứng dụng trong Toán học và Tin học, đặc biệt trong các bài toán về phân số, đồng dư và mã hóa. Thuật toán Euclid là một phương pháp hiệu quả để tìm UCLN của hai số nguyên, được phát triển từ thời Hy Lạp cổ đại.

2. Định nghĩa và Kí hiệu

• Ước chung (ƯC): Số nguyên $d$ là ước chung của $a$ và $b$ nếu $d$ chia hết cả $a$ và $b$, ký hiệu $d | a$ và $d | b$.
• Ước chung lớn nhất (UCLN): UCLN của $a$ và $b$, ký hiệu $\text{UCLN}(a, b)$, là số nguyên dương $d$ thỏa mãn:
  1. $d$ là ước chung của $a$ và $b$.
  2. Mọi ước chung $d'$ của $a$ và $b$ đều là ước của $d$ ($d' | d$).

3. Thuật toán Euclid

3.1. Nguyên lý cơ bản

Thuật toán Euclid dựa trên một tính chất quan trọng của UCLN:

$\text{UCLN}(a, b) = \text{UCLN}(b, a \mod b)$

trong đó $a \mod b$ là phần dư của phép chia $a$ cho $b$.

Chứng minh:

Giả sử $d = \text{UCLN}(a, b)$. Khi đó, tồn tại các số nguyên $m$ và $n$ sao cho:

$a = md$ $b = nd$

Gọi $r = a \mod b$. Theo định nghĩa phép chia có dư, ta có:

$a = qb + r$

với $q$ là thương và $0 \le r < b$.

Thay $a$ và $b$ vào, ta được:

$md = q(nd) + r$ $r = md - qnd = (m - qn)d$

Vậy $d$ là ước của $r$. Suy ra $d$ là ước chung của $b$ và $r$.

Ngược lại, giả sử $d'$ là ước chung của $b$ và $r$. Khi đó, tồn tại các số nguyên $x$ và $y$ sao cho:

$b = xd'$ $r = yd'$

Từ $a = qb + r$, ta có:

$a = q(xd') + yd' = (qx + y)d'$

Vậy $d'$ là ước của $a$. Suy ra $d'$ là ước chung của $a$ và $b$.

Do đó, tập các ước chung của $(a, b)$ và $(b, a \mod b)$ là như nhau. Vậy ước chung lớn nhất của chúng cũng bằng nhau:

$\text{UCLN}(a, b) = \text{UCLN}(b, a \mod b)$

3.2. Mô tả thuật toán

Để tìm UCLN của hai số nguyên dương $a$ và $b$ ($a \ge b$), thuật toán Euclid thực hiện các bước sau:

1. Nếu $b = 0$, thì $\text{UCLN}(a, b) = a$. Kết thúc thuật toán.
2. Nếu $b \ne 0$, gán $a \leftarrow b$ và $b \leftarrow a \mod b$.
3. Quay lại bước 1.

3.3. Ví dụ minh họa

Tìm $\text{UCLN}(1071, 462)$:

1. $1071 = 2 \cdot 462 + 147$ -> $\text{UCLN}(1071, 462) = \text{UCLN}(462, 147)$
2. $462 = 3 \cdot 147 + 21$ -> $\text{UCLN}(462, 147) = \text{UCLN}(147, 21)$
3. $147 = 7 \cdot 21 + 0$ -> $\text{UCLN}(147, 21) = \text{UCLN}(21, 0)$
4. Vì $b = 0$ nên $\text{UCLN}(21, 0) = 21$.

Vậy $\text{UCLN}(1071, 462) = 21$.

4. Tính chất

• Tính chất đối xứng: $\text{UCLN}(a, b) = \text{UCLN}(b, a)$
• UCLN của số với 0: $\text{UCLN}(a, 0) = |a|$
• UCLN của số với chính nó: $\text{UCLN}(a, a) = |a|$
• UCLN của hai số nguyên tố cùng nhau: $\text{UCLN}(a, b) = 1$
• Tính chất mở rộng: Nếu $d$ là một ước chung của $a$ và $b$, thì $d$ cũng là ước của $\text{UCLN}(a, b)$.

5. Ứng dụng

Thuật toán Euclid có nhiều ứng dụng trong Toán học và Tin học, bao gồm:

• Rút gọn phân số: UCLN được sử dụng để rút gọn phân số về dạng tối giản. Ví dụ, để rút gọn phân số $\frac{1071}{462}$, ta tìm $\text{UCLN}(1071, 462) = 21$, sau đó chia cả tử và mẫu cho 21, ta được $\frac{1071}{462} = \frac{1071/21}{462/21} = \frac{51}{22}$.
• Giải phương trình Diophantine tuyến tính: Thuật toán Euclid mở rộng có thể được sử dụng để tìm nghiệm của phương trình Diophantine dạng $ax + by = c$.
• Mật mã học: UCLN đóng vai trò quan trọng trong một số thuật toán mã hóa, chẳng hạn như RSA.
• Kiểm tra tính nguyên tố cùng nhau: Nếu $\text{UCLN}(a, b) = 1$, thì $a$ và $b$ là nguyên tố cùng nhau.

6. Bài tập áp dụng

1. Tìm $\text{UCLN}(252, 105)$.
2. Tìm $\text{UCLN}(12345, 6789)$.
3. Rút gọn phân số $\frac{360}{840}$.
4. Chứng minh rằng nếu $d = \text{UCLN}(a, b)$, thì $\text{UCLN}(\frac{a}{d}, \frac{b}{d}) = 1$.
5. Tìm hai số nguyên $x$ và $y$ sao cho $18x + 48y = \text{UCLN}(18, 48)$. (Gợi ý: Sử dụng thuật toán Euclid mở rộng).

7. Tổng kết

Thuật toán Euclid là một công cụ mạnh mẽ và hiệu quả để tìm UCLN của hai số nguyên. Nó có nhiều ứng dụng trong Toán học, Tin học và các lĩnh vực khác. Việc nắm vững thuật toán này sẽ giúp bạn giải quyết nhiều bài toán phức tạp một cách dễ dàng và nhanh chóng.