Witam.
Szukam za pomoca algorytmu NWD(34,121). Znajduje Wynik, Jest nim "1".
Zrobiłem to w kilku krokach typu: NWD (34, 121 mod 34) i tak dalej aż do uzyskania wyniku.
Na koniec w treści zadania mam: Znalesc to NWD a NASTEPNIE: przedstawic NWD(34,121) jako kombinacje liniowa 34 i 121.
Aby ja uzyskać muszę od końca algorytmu wypisywać po koleji kombinacje az dojde do ostatniego kroku, czyli pierewszego kroku algorytmu. Jest to meczące i czasochlonne i do tego mozna sie pomylic:)
Jest jakis skrot jak wypisać NWD(34,121)=1 jako kombinacje liniowa?
Kombinacja Liniowa Algorytmu Euklidesa
-
natkoza
- Użytkownik
- Posty: 2278
- Rejestracja: 11 kwie 2007, o 18:49
- Płeć: Kobieta
- Lokalizacja: Dąbrowa Górnicza
- Podziękował: 41 razy
- Pomógł: 602 razy
Kombinacja Liniowa Algorytmu Euklidesa
no to tak:
NWD za pomoca algorytmu euklidesa
\(\displaystyle{ 121=3\cdot 34+19\\
34=1\cdot 19+15\\
19=1\cdot 15+4\\
15=3\cdot 4+3\\
4=1\cdot 3+1}\)
i teraz jako kombinacje liniową za pomocą rozszerzonego algorytmu eyklidesa
\(\displaystyle{ 1=4-1\cdot 3=4-(15-3\cdot 4)=4-1\cdot 15+3\cdot 4=4\cdot 4-1\cdot 15=4(19-1\cdot 15)-1\cdot 15=4\cdot 19-4\cdot 15-1\cdot 15=4\cdot 19-5\cdot 15=4\cdot 19-5(34-1\cdot 19)=4\cdot 19-5\cdot 34+5\cdot 19=9\cdot 19-5\cdot 34=9(121-3\cdot 34)-5\cdot 34=9\cdot 121-27\cdot 34-5\cdot 34=9\cdot 121-32\cdot 34}\)
innej metody nie kojarze
NWD za pomoca algorytmu euklidesa
\(\displaystyle{ 121=3\cdot 34+19\\
34=1\cdot 19+15\\
19=1\cdot 15+4\\
15=3\cdot 4+3\\
4=1\cdot 3+1}\)
i teraz jako kombinacje liniową za pomocą rozszerzonego algorytmu eyklidesa
\(\displaystyle{ 1=4-1\cdot 3=4-(15-3\cdot 4)=4-1\cdot 15+3\cdot 4=4\cdot 4-1\cdot 15=4(19-1\cdot 15)-1\cdot 15=4\cdot 19-4\cdot 15-1\cdot 15=4\cdot 19-5\cdot 15=4\cdot 19-5(34-1\cdot 19)=4\cdot 19-5\cdot 34+5\cdot 19=9\cdot 19-5\cdot 34=9(121-3\cdot 34)-5\cdot 34=9\cdot 121-27\cdot 34-5\cdot 34=9\cdot 121-32\cdot 34}\)
innej metody nie kojarze