Rozszerzony algorytm Euklidesa
-
- Użytkownik
- Posty: 15
- Rejestracja: 30 cze 2014, o 13:16
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 3 razy
Rozszerzony algorytm Euklidesa
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.
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.
Ostatnio zmieniony 30 cze 2014, o 14:26 przez grzezuk, łącznie zmieniany 2 razy.
-
- Użytkownik
- Posty: 3044
- Rejestracja: 25 mar 2010, o 15:34
- Płeć: Mężczyzna
- Lokalizacja: Gołąb
- Podziękował: 24 razy
- Pomógł: 513 razy
Rozszerzony algorytm Euklidesa
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.
-
- Użytkownik
- Posty: 15
- Rejestracja: 30 cze 2014, o 13:16
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 3 razy
Rozszerzony algorytm Euklidesa
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 ?
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 ?
-
- Użytkownik
- Posty: 3044
- Rejestracja: 25 mar 2010, o 15:34
- Płeć: Mężczyzna
- Lokalizacja: Gołąb
- Podziękował: 24 razy
- Pomógł: 513 razy
Rozszerzony algorytm Euklidesa
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.
W takim razie jest dobrze. Ale taki algorytm nie jest zbyt efektywny, lepiej wykonywać dzielenie z resztą. Znacznie lepiej.
-
- Użytkownik
- Posty: 15
- Rejestracja: 30 cze 2014, o 13:16
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 3 razy
Rozszerzony algorytm Euklidesa
Przepraszam, podałem złe dane w I poście. Już poprawiłem. Możesz wytłumaczyć na czym polega Twoja metoda ?
-
- Użytkownik
- Posty: 3044
- Rejestracja: 25 mar 2010, o 15:34
- Płeć: Mężczyzna
- Lokalizacja: Gołąb
- Podziękował: 24 razy
- Pomógł: 513 razy
Rozszerzony algorytm Euklidesa
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.
\(\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.
-
- Użytkownik
- Posty: 15
- Rejestracja: 30 cze 2014, o 13:16
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 3 razy
Rozszerzony algorytm Euklidesa
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 ?
-
- Użytkownik
- Posty: 15
- Rejestracja: 30 cze 2014, o 13:16
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 3 razy
Rozszerzony algorytm Euklidesa
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}\) ??
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}\) ??
-
- Użytkownik
- Posty: 3044
- Rejestracja: 25 mar 2010, o 15:34
- Płeć: Mężczyzna
- Lokalizacja: Gołąb
- Podziękował: 24 razy
- Pomógł: 513 razy
Rozszerzony algorytm Euklidesa
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}\)
-- 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}\)
-
- Użytkownik
- Posty: 15
- Rejestracja: 30 cze 2014, o 13:16
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 3 razy
Rozszerzony algorytm Euklidesa
Czyli nie ma metody na określenie zbioru \(\displaystyle{ p}\) i \(\displaystyle{ q}\) tylko trzeba to tak rozpisać ?
-
- Użytkownik
- Posty: 3044
- Rejestracja: 25 mar 2010, o 15:34
- Płeć: Mężczyzna
- Lokalizacja: Gołąb
- Podziękował: 24 razy
- Pomógł: 513 razy
Rozszerzony algorytm Euklidesa
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.
\(\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.
-
- Użytkownik
- Posty: 32
- Rejestracja: 16 paź 2016, o 18:52
- Płeć: Mężczyzna
- Podziękował: 15 razy
Rozszerzony algorytm Euklidesa
nie rozumiem tej odpowiedzi, moze mi ktoś wytłumaczyć??bakala12 pisze: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.
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.
-
- Użytkownik
- Posty: 75
- Rejestracja: 30 lis 2014, o 19:46
- Płeć: Mężczyzna
- Lokalizacja: Edinburgh & Śląsk
- Pomógł: 13 razy
Rozszerzony algorytm Euklidesa
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}\).kacperus pisze: 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.
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.