# Giải thuật Euclid mở rộng

## Lịch sử thuật toán
Thuật toán Euclid là một trong những thuật toán cổ nhất được biết đến, từ khi nó xuất hiện trong cuốn Euclid’s Elements khoảng năm 300 trước công nguyên. Euclid khởi đầu đã trình bày rõ ràng vấn đề về phương diện hình học, như vấn đề tìm ra một thước đo chung cho độ dài hai đường thẳng, và thuật toán của ông đã xử lý bằng cách lặp lại phép trừ đoạn dài hơn cho đoạn ngắn hơn. Tuy nhiên, thuật toán đã hầu như không được phát hiện ra bởi Euclid và nó đã có thể được biết đến sớm hơn 200 năm. Nó cũng đã được biết đến bởi Eudoxus of Cnidus (khoảng năm 375 trước công nguyên) và Aristotle (khoảng năm 330 trước công nguyên).

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

**Phương trình diophantine:** $ax + by = c$ $(1)$.

**Định lý Bézout (Bézout’s indentify):** Cho hai số nguyên $a$, $b$ khi đó luôn tồn tại hai số $x$, $y$ sao cho $ax + by = gcd(a, b)$.

Xét hai số nguyên $a$, $b$ nguyên tố cùng nhau và phương trình $ax + by = 1$. Ta có thể tiến hành tìm nghiệm $x$, $y$ của bài toán. Áp dụng thuật toán tìm ước chung lớn nhất.

Giả sử ta có biểu thức: $52x + 47y = 1$ $(a = 52,\ b = 47)$.

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

Ta có thể thấy nếu không rơi vào trường hợp $b = 0$ thì thuật toán tiến hành gọi đệ quy $gcd$$($$b$, $a$ % $b$$)$. Gọi $a'$ là $b$ và $b'$ là $a$ % $b$, ta có:
- $a'$ = $b$.
- $b'$ = $a$ % $b$ $=$ $a - (a / b) * b$.

Từ $(1)$ ta có:
$<=>$ $bx’ + (a – (a / b) * b) * y’ = g$
$<=>$ $bx’ + a * y’ – (a / b) * by’ = g$