algorytmy Ambitny: Algorytmy i struktury danych zadanie:https://ibb.co/kmgLY6 Witam, rozwiązałem je następująco: korzystam ze wzoru a^{( p−1)(q−1)} ≡ 1(mod pq) więc p = 2 i q =5 (liczby pierwsze wybieram) a =17 17^{(2−1)(5−1)} = 1(mod 2*5) 17⁽¹⁾⁽⁴⁾ = 1 mod 10 17⁵ = 1 mod (10) 17¹⁷¹⁷ mod 10 zapiszemy jako 17¹⁷¹⁷ = 17^(42+1)17 mod 10 = 17^(42*17+117) mod 10 = 17^{434 + 1} mod 10 przyjmuje 34 jako stałą k = 17^(4k+1) mod 10 = 17^(4k) mod 10 * 17¹ mod 10 = (17⁴)^k mod 10 * 17 ¹ mod 10 17⁴ = 1 mod 10 =1^k * 17¹ mod 10 = 1*17 mod 10 = 17 mod 10 = 7 więc 17¹⁷¹⁷ mod 10 = 7 , cyfrą jedności liczby 17¹⁷¹⁷ jest 7, Dobrze rozwiązałem zadanie?

Mac Donald: ten wzór to wynika np. z tw. Fermata (małego) dalej po uzyskaniu 17⁴=1 (mod 10) wystarczy policzyć 17¹⁷ przez 4 (4²+1)¹⁷ = 1 (mod 4) zatem 17¹⁷¹⁷=17 (mod 10) bez tego kombinowania którego zreszrą nie rozumiem

kochanus_niepospolitus: A od kiedy 1*4 = 5 Sam wynik dobry (https://www.wolframalpha.com/input/?i=17%5E(17%5E17)), aczkolwiek dawno miałem teorię liczb więc nie rozumiem przejścia z 17^{(16 +1)17} (mod 10) = 17^{1617 +117} (mod 10)

Ambitny: nie mogę chyba tak na tym skończyć, bo nie pokazałem kilku operacji

Ambitny: a no to może się pomyliłem @kochanus

kochanus_niepospolitus: po prostu mały chochlik się pojawił u Ciebie w 3 linijce

Ambitny: tak naprawdę to nie wiem dlaczego mi wyszedł prawidłowy wynik, bo taka operacja raczej nie jest równoważna z linijką pod spodem ? = 17^{(42 + 1)17} mod 10 = 17^{(42*17 + 117)} mod 10

Ambitny: chciałem uzyskać 4^k, ale w ten sposób raczej mi się nie uda

Ambitny: ktoś mógłby rozwiać moje wątpliwości? własnie niedawno przyszedlem z zajec i prowadzący mi powiedział, że takiej operacji nie mogę zrobić, pomoże mi ktoś to poprawić?

Adamm: czy nie rozumiesz dlaczego (4*4+1)¹⁷ ≡₄ 1 wynika to z faktu że a ≡_n b oraz a' ≡_n b' to aa' ≡_n bb' skoro 4*4+1 ≡₄ 1 to tym bardziej (4*4+1)ⁿ ≡₄ 1 dla dowolnej potęgi naturalnej n

Ambitny: Tzn Nie rozumiem.dlaczego operacja z 14 : 10 jest niepoprawna, i jak to ew. można poprawić

kochanus_niepospolitus: Ambitny ... a skąd wiesz, że: 17^{(16 + 1)17} (mod 10) = 17^{1617 + 117} (mod 10) Bo to, że obie liczby nie są sobie równe to chyba nie mamy tutaj wątpliwości. Skąd masz pewność, że obie liczby będą miały taką samą ostatnią cyfrę ?

kochanus_niepospolitus: Tak jak wcześniej pisałem − teorię liczb miałem bardzo dawno temu, więc nie byłem pewien, ale podejrzane to przejście było dla mnie.

kochanus_niepospolitus: kuźwa ... tutaj akurat ta równość zachodzi, jednak to trzeba odpowiednio opisać: zauważ, że: (16 + 1)¹⁷ = 16¹⁷ + a₁16¹⁶ + a₂16¹⁵ + ... + a₁₆16 + 1 już abstrahując od wartości a₁, ... a₁₆ (bo są one mniej istotne) wiemy, że: 17⁴ (mod 10) = 1 ... a więc 17¹⁶ (mod 10) = 1 ... a więc 17^16*c (mod 10) = 1 gdzie c∊N₊ w takim razie zapisujemy: 17^{(16 + 1)17} (mod 10) = 17^{1617 +a₁1616 +a₂1615 +...+a₁₆16 + 1} (mod 10) = = [17¹⁶¹⁷ (mod 10)]*[17^1616*a₁ (mod 10)]*...*[17¹ (mod10)] = = 1*1*...*1*7 = 7 zastosowano dodatkowo: (a*b) (mod c) = [a (mod c)]*[b (mod c)]

Ambitny: Dziękuje kochanus

Ambitny: Właśnie nie byłem pewien tej operacji

kochanus_niepospolitus: pamiętaj, że równość tutaj wynika z tego, że 17⁴ (mod 10) = 1 i tylko z tego to wynika