Wartość NWD i równanie

[perm]

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]

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

[perm]

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

[abc666]

... _Euklidesa

[perm]

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]

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