solution

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

Euclid mở rộng tìm bộ hệ số Bézout $(x,y)$ thỏa:

$a\cdot x + b\cdot y = \gcd(a,b)$

Đây là công cụ chuẩn để tính nghịch đảo modular với modulo bất kỳ.

Cho $a$, $b$, in ba số $g$, $x$, $y$ với $g=\gcd(a,b)$ và $ax+by=g$. Để kết quả duy nhất, hãy dùng đúng công thức đệ quy chuẩn:

• $\text{extgcd}(a,0) = (a,1,0)$;
• $\text{extgcd}(a,b) = (g, y_1, x_1 - \lfloor a/b\rfloor y_1)$ với $(g,x_1,y_1)=\text{extgcd}(b, a\bmod b)$.

Ví dụ

$\text{extgcd}(30,12)=(6,1,-2)$ vì $30\cdot1+12\cdot(-2)=6$.