Już jutro czeka mnie kolejna poprawka, tym razem z matematyki dyskretnej. Czy orientuje się ktoś jak robić tego typu zadania jak to zadanie nr 3 z linka tutaj:
http://wloclawek.wsinf.edu.pl/~pgmys/kursy/matemat/lekcja4.html
W notatkach mam jakas tabelke, ale nie wiem z czego wyliczyć te dwie liczby s i t (NWD z algorytmui umiem wyliczyć).
Skorzystaj z algorytmu Euklidesa, aby znaleźć NWD(m,n) oraz liczby s i t takie, że NWD(m,n) = s*m+t*n dla podanych liczb m i n.
a) m=20, n=14
Jeśli umiesz wyliczyć NWD algorytmem Euklidesa, to z wyznaczeniem s i t też sobie poradzisz. Po prostu wykonujesz algorytm Euklidesa "wspak" - podstawiając wyliczone wartości.
Przykład:
Liczymy NWD(882, 70).
882 = 12 * 70 + 42
70 = 1 * 42 + 28
42 = 1 * 28 + 14
28 = 2 * 14 + 0
Czyli NWD(882, 70) = 14 (zakładam że wiesz skąd się biorą poszczególne liczby w powyższych równościach). Teraz w drugą stronę (zaczynamy od przedostatniej równości):
14 = 42 - 1 * 28
Zastępujemy 28 korzystając z wcześniejszej równości:
14 = 42 - 1 * (70 - 1 * 42)
To samo robimy z 42 (oba wystąpienia):
14 = (882 - 12 * 70) - 1 * (70 - 1 * (882 - 12 * 70))
Upraszczamy i dostajemy co chcieliśmy:
14 = 2 * 882 - 25 * 70
