Rozszerzony algorytm Euklidesa

[grzezuk]

Cześć, potrzebuję pomocy z następujacym zadaniem:
Korzystając z rozszerzonego algorytmu Euklidesa znajdź takie liczby całkowite p i q dla których

\(\displaystyle{ NWD\left( a,b\right) = pa + qb}\)

dla a=377, b=123.

Znalazłem w innym temacie z podobnym zadaniem metodę która mówiła, że NWD najłatwiej znaleźć odejmując mniejszą liczbę od większej do momentu aż odjemna bądź odjemnik będą równe różnicy - wtedy różnica jest NWD, co dało mi wynik 1, więc otrzymuję równanie:

\(\displaystyle{ 377p + 123q = 1}\)

Nie wiem co dalej.

[bakala12]

Masz zły wynik. Obie liczby dzielą się na przykład przez \(\displaystyle{ 7}\), więc NWD na pewno nie będzie równe \(\displaystyle{ 1}\). Pokaż jak liczysz.

[grzezuk]

Liczę tak, że wypisuję sobie obie liczby i odejmuję mniejszą od większej:

377____123 (123 mniejsze więc od 377 odejmuję 123 i wynik wpisuję w miejsce 377)
254____123
131____123
8______123 (teraz 8 jest mniejsze więc odejmuję 8 od 123)
.
.
.
8____11
8____3
5____3
2____3
2____1
1____1 (dwie równe liczby - wynik)

Z tego co wiem, ani 377 ani 123 nie dzielą się bez reszty przez 7 ?

[bakala12]

Ok, myślałem że liczysz \(\displaystyle{ NWD\left( 1001,357\right)}\)
W takim razie jest dobrze. Ale taki algorytm nie jest zbyt efektywny, lepiej wykonywać dzielenie z resztą. Znacznie lepiej.

[grzezuk]

Przepraszam, podałem złe dane w I poście. Już poprawiłem. Możesz wytłumaczyć na czym polega Twoja metoda ?

[bakala12]

Opiera się ona na równości:
\(\displaystyle{ NWD\left( a,b\right)=NWD\left( a,a\pmod{b}\right)}\)
Metoda wygląda tak (\(\displaystyle{ a \ge b}\)):
1. Dzielimy \(\displaystyle{ a}\) przez \(\displaystyle{ b}\) otrzymując resztę \(\displaystyle{ r}\).
2. Jeśli \(\displaystyle{ r=0}\), to koniec i \(\displaystyle{ NWD\left( a,b\right)=b}\)
3. Jeśli \(\displaystyle{ r \neq 0}\) to \(\displaystyle{ a:=b}\), \(\displaystyle{ b:=r}\) i wracamy do kroku 1.

EDIT: Poprawiłem błąd.

[grzezuk]

Rozumiem, rzeczywiście jest ona prostsza. Co dalej z zadaniem ? Jak znaleźć wszystkie takie liczby \(\displaystyle{ p}\) i \(\displaystyle{ q}\) które spełnią warunek ?

[bakala12]

Tutaj jest wszystko napisane ... _Euklidesa
Wystarczy tylko przeczytać.

[grzezuk]

No tak, trafiłem na ten artykuł. Pytanie moje dotyczy jednak podania odpowiedzi. Mam sobie wystrzelać takie wartości żeby równanie było spełnione ?

Mam jeszcze pytanie do liczenia \(\displaystyle{ NWD}\) Twoją metodą, napisałeś, że jeśli \(\displaystyle{ r=1}\) to \(\displaystyle{ NWD = b}\), jednak licząc \(\displaystyle{ NWD(3,2)}\) otrzymujemy resztę \(\displaystyle{ r=1}\) i wg. Twojego algorytmu \(\displaystyle{ NWD(3,2)=b=2}\) co jest nieprawdą. Czy zatem w przypadku gdy \(\displaystyle{ r=1}\) nie powinno być \(\displaystyle{ NWD(a,b)=r}\) ??

[bakala12]

No bo skopałem, miało być \(\displaystyle{ r=0}\), przepraszam i już poprawiam

-- 30 cze 2014, o 17:21 --

No dobra, przeliczmy:
\(\displaystyle{ 377:123=3 \ r \ 8 \\
123:8=15 \ r \ 3 \\
8:3=2 \ r \ 2 \\
3:2=1 \ r \ 1 \\
2:1=1 \ r \ 0}\)
Ostatnia niezerowa reszta to \(\displaystyle{ NWD}\), więc \(\displaystyle{ NWD\left( 377,123\right)=1}\).
Teraz będziemy zapisywać:
\(\displaystyle{ 1=1 \cdot 3 -1 \cdot 2 = 123-15 \cdot 8-\left( 8-2 \cdot 3\right)=\\=
123-15 \cdot \left( 377-3 \cdot 123\right)-\left(377-3 \cdot 123\right) + 2 \cdot \left( 123-15 \cdot 8\right)=\\=
123-15 \cdot \left( 377-3 \cdot 123\right)-\left(377-3 \cdot 123\right) + 2 \cdot \left( 123-15 \cdot \left( 377-3 \cdot 123\right)\right)=\\=
\left( -46\right) \cdot 377+141 \cdot 123}\)

[grzezuk]

Czyli nie ma metody na określenie zbioru \(\displaystyle{ p}\) i \(\displaystyle{ q}\) tylko trzeba to tak rozpisać ?

[bakala12]

To jest tylko jedna z możliwości. Wszystkie rozwiązania są dane wzorem
\(\displaystyle{ p=-46-123n \\ q=141+377n}\) gdzie \(\displaystyle{ n}\) jest liczbą całkowitą. Dowód tego co tutaj napisałem jest prostym wnioskiem z chińskiego twierdzenia o resztach.

[kacperus]

To jest tylko jedna z możliwości. Wszystkie rozwiązania są dane wzorem
\(\displaystyle{ p=-46-123n \\ q=141+377n}\) gdzie \(\displaystyle{ n}\) jest liczbą całkowitą. Dowód tego co tutaj napisałem jest prostym wnioskiem z chińskiego twierdzenia o resztach.

nie rozumiem tej odpowiedzi, moze mi ktoś wytłumaczyć??
w jakims innym temacie jak wyliczyłem a i b z NWD to odejmowałem większą liczbę od mniejszej i wychodził największy wspólny dzielnik, tego nie rozumiem.

[_Michal]

w jakims innym temacie jak wyliczyłem a i b z NWD to odejmowałem większą liczbę od mniejszej i wychodził największy wspólny dzielnik, tego nie rozumiem.

No dobrze, dostałeś największy wspólny dzielnik. Ale w tym zadaniu chodziło o to żeby ten największy wspólny dzielnik (liczb \(\displaystyle{ a}\) i \(\displaystyle{ b}\)) zapisać jako \(\displaystyle{ pa+qb}\) (dla naturalnych \(\displaystyle{ p}\) i \(\displaystyle{ q}\)). Najłatwiej znaleźć takie \(\displaystyle{ p}\) i \(\displaystyle{ q}\) korzystając z algorytmu Euklidesa, ale dla danych \(\displaystyle{ a}\) i \(\displaystyle{ b}\) może istnieć więcej takich par \(\displaystyle{ (q, p)}\), tzn każda po podstawieniu do \(\displaystyle{ pa+qb}\) da \(\displaystyle{ NWD(a, b)}\). Użytkownik bakala12 po prostu wyznaczył wszystkie takie pary \(\displaystyle{ (q, b)}\) dla liczb \(\displaystyle{ (377, 123)}\). Żeby zrozumieć jak to zrobił poczytaj o rozwiązywaniu równań diofantycznych \(\displaystyle{ ax+by=c}\).

edit:
Mógłbyś się wyrazić precyzyjniej, bo aktualnie z twojej wypowiedzi wynika, że wyliczyłeś \(\displaystyle{ a}\) i \(\displaystyle{ b}\), a przecież \(\displaystyle{ a}\) i \(\displaystyle{ b}\) to liczby dane na początku zadania. Aktualnie wydaję mi się że chodziło Ci o kilkukrotne użycie tożsamości \(\displaystyle{ NWD(a, b)=NWD(a,a-b)}\) do wyliczenia \(\displaystyle{ NWD}\), ale wypowiedź jest absolutnie niejednoznaczna.

[kacperus]

nie zrozumiałem treści zadania, dzięki za wytłumaczenie.