Dzień dobry, rozwiązuje algorytm Euklidesa i utknąłem w jednym punkcie i nie wiem co dalej.
Oto przykład i moje rozwiązanie:
\(\displaystyle{ NWD(6408, 4280) = 6408x + 4280y}\)
\(\displaystyle{ 6408 = 4280\cdot 1 + 2128}\)
\(\displaystyle{ 4280 = 2128\cdot 2 + 24}\)
\(\displaystyle{ 2128 = 24\cdot 88 + 16}\)
\(\displaystyle{ 24 = 16\cdot 1 +8}\)
\(\displaystyle{ 16 = 8\cdot 2 + 0}\)
Po przekształceniach:
\(\displaystyle{ NWD(6408, 4280) = 8 = 24 - 1(2128 - 88(4280 - 2(6408 - 4280))) = 24 - 1(2128 - 88(4280(3) + 6408(-2))) = 24 - 1(2128 - (4280(264) + 6408(-176)) = ...}\)
Dalej nie wiem co wyłączać to 2128 stoi na przeszkodzie.
Rozszerzony algorytm Euklidesa
-
Qń
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
Rozszerzony algorytm Euklidesa
Wiesz przecież, że \(\displaystyle{ 2128=6408 - 4280}\).
Ale tak czy siak robisz to w dziwny sposób (no i zostaje Ci jeszcze \(\displaystyle{ 24}\) na początku). Rozsądniej robić to od końca:
\(\displaystyle{ 8=24-16= 24- (2128 - 88\cdot 24) = -2128 +89\cdot 24 = \\ =-2128 +89 (4280 - 2\cdot 2128) = \ldots}\)
W ten sposób na końcu zostanie Ci tylko kombinacja liniowa wyjściowych liczb.
Q.
Ale tak czy siak robisz to w dziwny sposób (no i zostaje Ci jeszcze \(\displaystyle{ 24}\) na początku). Rozsądniej robić to od końca:
\(\displaystyle{ 8=24-16= 24- (2128 - 88\cdot 24) = -2128 +89\cdot 24 = \\ =-2128 +89 (4280 - 2\cdot 2128) = \ldots}\)
W ten sposób na końcu zostanie Ci tylko kombinacja liniowa wyjściowych liczb.
Q.
Rozszerzony algorytm Euklidesa
Dzięki za pomoc, ładnie wyszło.
Mam jeszcze inny przykład
\(\displaystyle{ NWD(6408, 4282) = 6408x + 4282y}\)
\(\displaystyle{ 6408 = 4282\cdot 1 + 2126}\)
\(\displaystyle{ 4282 = 2126\cdot 2 +30}\)
\(\displaystyle{ 2126 = 30\cdot 70 + 26}\)
\(\displaystyle{ 30 = 26\cdot 1 + 4}\)
\(\displaystyle{ 26 = 4\cdot 6 + 2}\)
\(\displaystyle{ 4 = 2\cdot 2 + 0}\)
\(\displaystyle{ 2 = 26 - 6\cdot 4 = 26 - 6(30 - 26) = 26 - 6(30 - (2126 - 70\cdot 30)) = 26 - 6(-2126 + 71\cdot 30)= ...}\)
I dalej się ciagnie to 26 - 6 i wiem, że to nie wyjdzie. Jak je zniwelować?
Mam jeszcze inny przykład
\(\displaystyle{ NWD(6408, 4282) = 6408x + 4282y}\)
\(\displaystyle{ 6408 = 4282\cdot 1 + 2126}\)
\(\displaystyle{ 4282 = 2126\cdot 2 +30}\)
\(\displaystyle{ 2126 = 30\cdot 70 + 26}\)
\(\displaystyle{ 30 = 26\cdot 1 + 4}\)
\(\displaystyle{ 26 = 4\cdot 6 + 2}\)
\(\displaystyle{ 4 = 2\cdot 2 + 0}\)
\(\displaystyle{ 2 = 26 - 6\cdot 4 = 26 - 6(30 - 26) = 26 - 6(30 - (2126 - 70\cdot 30)) = 26 - 6(-2126 + 71\cdot 30)= ...}\)
I dalej się ciagnie to 26 - 6 i wiem, że to nie wyjdzie. Jak je zniwelować?
-
Qń
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
Rozszerzony algorytm Euklidesa
Znowu robisz to nie tak jak trzeba.
W momencie kiedy dochodzisz do:
\(\displaystyle{ 26 - 6(30 - 26)}\)
to najpierw porządkujesz:
\(\displaystyle{ 7\cdot 26 - 6\cdot 30}\)
a potem dopiero zastępujesz mniejszą z liczb przy pomocy poprzedniej równości:
\(\displaystyle{ 26=2126 - 30\cdot 70}\)
i znów porządkujesz, a potem dopiero zastępujesz.
Q.
W momencie kiedy dochodzisz do:
\(\displaystyle{ 26 - 6(30 - 26)}\)
to najpierw porządkujesz:
\(\displaystyle{ 7\cdot 26 - 6\cdot 30}\)
a potem dopiero zastępujesz mniejszą z liczb przy pomocy poprzedniej równości:
\(\displaystyle{ 26=2126 - 30\cdot 70}\)
i znów porządkujesz, a potem dopiero zastępujesz.
Q.
Rozszerzony algorytm Euklidesa
Wniosek jest taki, że należy porządkować wpierw a dopiero potem podstawiać, zrobiłem jak mówisz i wyszło. Dzięki Qń za pomoc