Rozszerzony algorytm Euklidesa

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
acarmis
Użytkownik
Użytkownik
Posty: 11
Rejestracja: 20 mar 2012, o 08:39
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 2 razy

Rozszerzony algorytm Euklidesa

Post autor: acarmis »

Witam, poszukuje jakiegoś przykładu, wskazówek które pozwoli rozwiązać mi zadanie:
Stosując rozszerzony algorytm Euklidesa, proszę znaleźć rozwiązanie następującego równania diofantycznego (w liczbach całkowitych)
\(\displaystyle{ 128 x + 89 y = 15}\)

Zastanawia mnie czy nie ma jakiegoś błędu w tym równaniu ponieważ wszelkie przykłady wykorzystujące rozszerzony algorytm Euklidesa są w postaci:
\(\displaystyle{ NWD(a,b)=ax+by}\)


Jeżeli dobrze myślę to można to rozwiązać na początku równanie w postaci:
\(\displaystyle{ NWD(128,89)=128x+89y}\) a następnie wyliczony \(\displaystyle{ x}\) i \(\displaystyle{ y}\) pomnożyć przez \(\displaystyle{ 15}\)? Czy dobrze myślę?
Ostatnio zmieniony 28 kwie 2012, o 20:18 przez , łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości. Wszystkie wyrażenia matematyczne umieszczaj w tagach [latex] [/latex].
Użytkownik
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

Post autor: »

Jeśli chodzi o znalezienie pewnego rozwiązania, to Twój pomysł jest dobry.

Q.
acarmis
Użytkownik
Użytkownik
Posty: 11
Rejestracja: 20 mar 2012, o 08:39
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 2 razy

Rozszerzony algorytm Euklidesa

Post autor: acarmis »

A jak miało by to wyglądać dla wszystkich rozwiązań?
ODPOWIEDZ