Wartość NWD i równanie

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
perm
Użytkownik
Użytkownik
Posty: 31
Rejestracja: 15 sty 2011, o 10:04
Płeć: Mężczyzna
Lokalizacja: Ryki
Podziękował: 10 razy

Wartość NWD i równanie

Post autor: perm » 1 wrz 2011, o 12:44

Witam, mam problem z pewnym zadankiem:

Oblicz wartość
\(\displaystyle{ n=NWD(3330, 1503)}\)

Następnie pokaż dowolne liczby całkowite a,b, aby
\(\displaystyle{ a \cdot 3330 + b \cdot 1503 = n}\)

Z pierwszą częścią zadania nie mam problemu, z algorytmu Euklidesa wychodzi \(\displaystyle{ n=9}\). Ale gdy podstawię \(\displaystyle{ n=9}\) w równaniu poniżej, to po przekształceniach wychodzi mi \(\displaystyle{ 0=0}\) i nic już z tym nie mogę zrobić. Jest jakiś sposób na rozwiązanie tego? Czy może ja robię coś źle?

Proszę o pomoc

Lider Artur
Użytkownik
Użytkownik
Posty: 692
Rejestracja: 19 cze 2011, o 23:29
Płeć: Mężczyzna
Lokalizacja: Warszawa
Pomógł: 107 razy

Wartość NWD i równanie

Post autor: Lider Artur » 1 wrz 2011, o 15:34

By wyznaczyć liczby a i b wystarczy się 'cofać' w algorytmie Euklidesa do samego początku odpowiednio przekształcając.

perm
Użytkownik
Użytkownik
Posty: 31
Rejestracja: 15 sty 2011, o 10:04
Płeć: Mężczyzna
Lokalizacja: Ryki
Podziękował: 10 razy

Wartość NWD i równanie

Post autor: perm » 1 wrz 2011, o 15:38

Czy mógłbyś podać na jakimś przykładzie o jakie konkretnie przekształcenia chodzi?

abc666

Wartość NWD i równanie

Post autor: abc666 » 1 wrz 2011, o 16:27


perm
Użytkownik
Użytkownik
Posty: 31
Rejestracja: 15 sty 2011, o 10:04
Płeć: Mężczyzna
Lokalizacja: Ryki
Podziękował: 10 razy

Wartość NWD i równanie

Post autor: perm » 1 wrz 2011, o 17:50

Staram się wykonać te przekształcenia, ale chyba coś mi nie wychodzi. Proszę o sprawdzenie poprawności zapisu:

\(\displaystyle{ 324 = 1 \cdot 3304 + \left( -2\right) \cdot 1503}\)
\(\displaystyle{ 207 = 1 \cdot 1503 + \left( -4\right) \cdot 324}\)
\(\displaystyle{ 117 = 1 \cdot 324 + \left( -1\right) \cdot 207}\)
\(\displaystyle{ 90 = 1 \cdot 207 + \left( -1\right) \cdot 117}\)
\(\displaystyle{ 27 = 1 \cdot 107 + \left( -1\right) \cdot 90}\)
\(\displaystyle{ 9 = 1 \cdot 90 + \left( -3\right) \cdot 27}\)
\(\displaystyle{ 0 = 1 \cdot 27 + \left( -3\right) \cdot 9}\)

Ale w dalszym ciągu nie wiem jak odczytać \(\displaystyle{ a}\) i \(\displaystyle{ b}\). Staram się sprowadzić cały ten algorytm do jednego równania, ale jego końcówka jest tak pokręcona, zawiła i niezrozumiała że nie daję rady z wyliczeniem tego. Proszę o pomoc, również bardzo byłbym wdzięczny gdyby ktoś pokazał mi, jak powinno się prawidłowo przekształcić ten algorytm.-- 2 wrz 2011, o 16:47 --Czy naprawdę nikt nie może mi pomóc? Nie jest to chyba trudne, a terminy gonią

Xitami

Wartość NWD i równanie

Post autor: Xitami » 3 wrz 2011, o 08:20

\(\displaystyle{ a=167n+116\\b=-370n-257}\)

ODPOWIEDZ