Algorytm Euklidesa- NWD

[DomiW]

Mam takie zadanie znaleźć \(\displaystyle{ u}\) i \(\displaystyle{ v}\) wiedząc , że \(\displaystyle{ au+bv= NWD (a,b)}\), gdzie \(\displaystyle{ a=3157, b=2281}\).
Wiem , że trzeba skorzystać z algorytmu Euklidesa.
I robię tak:
\(\displaystyle{ a= 3157 \ b= 2281 \ 3157= 1 \cdot 2281 + 876 \\
a= 2281 \ b=876 \ 2281= 2 \cdot 876 +529 \\
a= 876 \ b= 529 \ 876= 1 \cdot 529+347 \\
a= 529 \ b= 347 \ 529=1 \cdot 347+ 182 \\
a= 347 \ b= 182 \ 347= 182+ 165 \\
a= 182 \ b= 165 \ 182= 1 \cdot 165+ 17 \\
a= 165 \ b= 17 \ 165= 9 \cdot 17+12 \\
a= 17 \ b=12 \ 17=12+5 \\
a= 12 \ b=5 \ 12=2 \cdot 5+2 \\
a= 5 \ b=2 \ 5=2 \cdot 2+1 \\
a= 2 \ b=1 \ 2=2 \cdot 1\\
a=1 \ b= 0}\)
\(\displaystyle{ 1= 3157 u + 2281 v}\)
i jak to zrobić dalej ?
A może już tu źle robię, proszę o pomoc.