Định lý Bezout

TÀI LIỆU HỌC TẬP: ĐỊNH LÝ BÉZOUT VÀ ỨNG DỤNG

1. Định lý:

Cho hai số nguyên $a$ và $b$ khác 0. Khi đó, phương trình Diophantine bậc nhất hai ẩn:

$ax + by = \text{UCLN}(a, b)$

luôn có nghiệm nguyên $(x, y)$ .

2. Phát biểu mở rộng:

Phương trình $ax + by = c$ có nghiệm nguyên khi và chỉ khi $\text{UCLN}(a, b)$ là ước của $c$ , tức là $c \vdots \text{UCLN}(a, b)$ .
Nếu $(x_0, y_0)$ là một nghiệm của phương trình $ax + by = c$ , thì tất cả các nghiệm nguyên của phương trình này có dạng:
$x = x_0 + \dfrac{bk}{\text{UCLN}(a, b)} \\ y = y_0 - \dfrac{ak}{\text{UCLN}(a, b)} \end{cases}$$ trong đó $k$ là số nguyên.$

1. Thuật toán Euclid:

Thuật toán Euclid là một phương pháp hiệu quả để tìm UCLN của hai số nguyên. Nó dựa trên nhận xét sau:

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

trong đó $r$ là số dư trong phép chia $a$ cho $b$ , tức là $a = bq + r$ .

Thuật toán lặp lại quá trình chia và thay thế cho đến khi số dư bằng 0. Số chia cuối cùng khác 0 chính là UCLN của $a$ và $b$ .

2. Chứng minh định lý Bézout bằng thuật toán Euclid:

Giả sử ta áp dụng thuật toán Euclid để tìm UCLN của $a$ và $b$ :

undefined