Algorytm Euklidesa

[Kabacz]

Skorzystaj z algorytmu euklidesa, aby znaleźć NWD(m,n) oraz liczby \(\displaystyle{ s,t \in Z}\) takie, że \(\displaystyle{ NWD(m,n)=sm+tn.}\). NA podstawie NWD wyznacz NWW.
m=72 n=17
Może mi ktoś wyjaśnić jak zrobić te oto zadanie? Za bardzo nie wiem co to ma być te "s" oraz "t".
Znalazłem NWD za pomocą algorytmu, ale co zrobić dalej to nie mam pojęcia.
\(\displaystyle{ 72:17=4 \ reszty \ 4}\)
\(\displaystyle{ 17:4=4 \ reszty \ 1}\)
\(\displaystyle{ 4:1=4 \ reszty \ 0}\)
Czyli NWD(72,17)=1 tak ?

[Psiaczek]

Czyli NWD(72,17)=1 tak ?

Tak , ale mając na uwadze dalszy ciąg twojego polecenia lepiej pisać tak:

\(\displaystyle{ 72=4 \cdot 17+4}\)

\(\displaystyle{ 17=4 \cdot 4+1}\)

teraz linjkę z ostatnią niezerową resztą zapisz tak żeby NWD został po jednej stronie:

\(\displaystyle{ 17-4 \cdot 4=1}\)

i podstaw przekształconą pierwszą linijkę \(\displaystyle{ 4=72-4 \cdot 17}\) w miejsce drugiej czwórki ( ten przykład cholera jest niedydaktyczny bo wystepują czwórki spełniające różne funkcje )

otrzymasz:

\(\displaystyle{ 17-4(72-4 \cdot 17)=1}\)

po przejściach \(\displaystyle{ 17 \cdot 17-4 \cdot 72=1}\) znów dwie siedemnastki niestety , pierwsza to współczynnik

czyli \(\displaystyle{ NWD(72,17)=17 \cdot 17-4 \cdot 72}\) twoje tajemnicze \(\displaystyle{ s,t}\) się znalazły.


Zrób sobie przykład na innych liczbach, bo ten z uwagi na te współczynniki co wychodzą jest nieco mylący.

[Kabacz]

Jednej rzeczy nie rozumiem.
Jak z tej formy \(\displaystyle{ 17-4(72-4 \cdot 17)=1}\) przejść na \(\displaystyle{ 17 \cdot 17-4 \cdot 72=1}\) ?

[Psiaczek]

Jednej rzeczy nie rozumiem.
Jak z tej formy \(\displaystyle{ 17-4(72-4 \cdot 17)=1}\) przejść na \(\displaystyle{ 17 \cdot 17-4 \cdot 72=1}\) ?

\(\displaystyle{ (-4) \cdot(- 4) =16, 16+1=17}\) zbierasz do kupy siedemnastki, mówiłem że jest mylący

[Kabacz]

hmmm to może zobaczmy inny przykład. np m=320 n=30
Czyli
\(\displaystyle{ 320:30=10 / reszty / 20}\)
\(\displaystyle{ 30:20=1 / reszty / 10}\)
\(\displaystyle{ 20:10=2 / reszty / 0}\)

\(\displaystyle{ 320=30 \cdot 10 + 20}\)
\(\displaystyle{ 30=20 \cdot 1 + 10}\)

\(\displaystyle{ 320 - 30 \cdot 10= 20}\)
\(\displaystyle{ 30 - 20 \cdot 1 =10}\)

\(\displaystyle{ 30 - ( 320 - 30 \cdot 10) 1 =10}\)

No i tutaj znowu nie wiem jak dalej iść. Coś mi ten etap opornie idzie.

[Psiaczek]

hmmm to może zobaczmy inny przykład. np \(\displaystyle{ m=320 n=30}\)

\(\displaystyle{ 320=10 \cdot 30+20}\)

\(\displaystyle{ 30=1 \cdot 20+10}\)

\(\displaystyle{ 30-1 \cdot 20=10}\)

z pierwszej linijki \(\displaystyle{ 20=320-10 \cdot 30}\)


\(\displaystyle{ 30-1 \cdot (320-10 \cdot 30)=10}\)

\(\displaystyle{ 11 \cdot 30-1 \cdot 320=10}\)

zaczaiłeś?

[Kabacz]

Już łapie o co chodzi. Dziękuje bardzo za pomoc