Để tìm ƯC(a,b) biết ƯCLN(a,b) = m, ta có thể sử dụng công thức Euclid mở rộng.

Công thức Euclid mở rộng:
ƯCLN(a,b) = ax + by

Với a, b là hai số nguyên dương và m là ƯCLN của a và b, ta có thể tìm được x và y là hai số nguyên sao cho phương trình trên đúng.

Cách tìm ƯC(a,b) biết ƯCLN(a,b) = m:
1. Sử dụng thuật toán Euclid để tìm ƯCLN(a,b) = m.
2. Áp dụng công thức Euclid mở rộng để tìm x và y.
- Gán x₀ = 1, y₀ = 0, x₁ = 0, y₁ = 1.
- Lặp lại các bước sau cho đến khi b = 0:
+ Tính q = a // b (phép chia lấy phần nguyên).
+ Gán (a, b) = (b, a - q * b).
+ Gán (x₀, x₁) = (x₁, x₀ - q * x₁).
+ Gán (y₀, y₁) = (y₁, y₀ - q * y₁).
3. Khi b = 0, ta có a = m * x₀ và b = m * y₀.
- ƯC(a,b) = a = m * x₀.

Vậy, để tìm ƯC(a,b) biết ƯCLN(a,b) = m, ta chỉ cần tính x₀ và nhân m vào x₀ để tìm ƯC(a,b).