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
Wartość NWD i równanie
-
- 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
By wyznaczyć liczby a i b wystarczy się 'cofać' w algorytmie Euklidesa do samego początku odpowiednio przekształcając.
-
- 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
Czy mógłbyś podać na jakimś przykładzie o jakie konkretnie przekształcenia chodzi?
-
- 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
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ą
\(\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ą