najwiekszy wspolny dzielnik

[2entartain]

Musze znalezc najwiekszy wspolny dzielnik ale cos mi nie gra w algorytmie Euklidesa...
NDW(37,32)
\(37=32\cdot 1+5\)
\(32=5\cdot 6+2\)
\(5=2\cdot2+1\) 
NDW(37,32)=1
ale nie umiem dojsc do liniowej kombinacji dla NWD \(1=37x+32y, x,y\in\mathbb{Z}\)
czy ktos pomoze?

[konrad131011]

37 to liczba pierwsza, więc dzieli się przez siebie samą i 1

[2entartain]

to wiem, ale to nie bylo moje pytanie

[octahedron]

\(\begin{array}{c|c|c}1&0&37\\\hline 0&1&32\end{array}\quad w_1-w_2
\begin{array}{c|c|c}1&-1&5\\\hline 0&1&32\end{array}\quad w_2-6w_1
\begin{array}{c|c|c}1&-1&5\\\hline -6&7&2\end{array}\quad w_1-2w_2
\begin{array}{c|c|c}13&-15&1\\\hline -6&7&2\end{array}
13\cdot 37-15\cdot 32=1\)

[rayman]

skoro masz znalezc liniowa kombinacje uzywajac algorytmu Euklidesa to zaczynamy od ostatniego rownania
\(1=5-2\cdot 2\)(*) i idziemy ''w gore''
\(5=37-32\) to wstawiamy do (*) i mamy
\(1=5-2(32-5\cdot 6)=-2\cdot 32+13\cdot 5\)
\(1=-2\cdot 32+13(37-32)=13\cdot 37+(-15)\cdot 32\)