Trivial albo PW ogipierogi: Trivial albo PW lub inny orzeł czy ktoś miły mógłby przypomnieć jak się to rozwiązywało ? oblicz 2¹0000 w Z₂7 8⁹999 w Z₃3 znaleźć dwie ostatnie cyfry liczby 43⁴8 znalesc ostatnia cyfre liczby 27²7²27

Trivial: Mogę pomóc, ale zapisz lepiej.

ogipierogi: o kurna, ale sie zapisło sorki oblicz 2¹⁰⁰⁰ w Z₂₇ 8⁹⁹⁹⁹ w Z₃₃ znaleźć dwie ostatnie cyfry liczby 43⁴⁸ znalesc ostatnia cyfre liczby 27²⁷²²⁷ oblicz 37x=15 w Z₁₂₇₄

zombi: Oo te dwie ostatnie cyfry, to Euler + kongru może zrobię, ale chwila.

Trivial: Przypomnij mi, Z₂₇ to po prostu liczby całkowite, które się zapętlają przy 27? 0,1,2,...,26, 0,1,...

zombi: 43⁴ = 1 mod 100 / ¹2 43⁴⁸ = 1 mod 100 czyli ostatnie cyfry to 01

zombi: 27⁴ = 1 mod 10 /⁶⁸⁰⁶ 27²⁷²²⁴ = 1 mod 10 /* 27³ 27²⁷²²⁷ = 3 mod 10 ostatnia cyfra 3

ogipierogi: Trivial tak jak napisałeś

Trivial: Jest taki sposób: Trzeba rozłożyć potęgę na postać binarną, a potem już prosto. Ten sposób nie jest może najszybszy, ale ma jedną ważną zaletę: zawsze zadziała. Jeśli wynik się powtórzy to mamy cykl i dzięki niemu wszystkie kolejne wyniki sa już policzone. Jeżeli dla jakiegoś wyniku otrzymamy 1 to w ogóle nie musimy już nic dalej liczyć! Zaczynamy od: 2 == 2 mod 27 2² == 4 mod 27 2⁴ == 16 mod 27 2⁸ == 256 == 13 mod 27 2¹⁶ == 169 == 7 mod 27 2³² == 49 == 22 mod 27 2⁶⁴ == 484 == 25 mod 27 2¹²⁸ == 625 == 4 mod 27 <−− cykl 2²⁵⁶ == 16 mod 27 2⁵¹² == 13 mod 27 Rozkładamy potęgę na postać binarną 2^{1 000}: 1 000 = 512 + 256 + 128 + 64 + 32 + 8 2¹⁰⁰⁰ == 13*16*4*25*22*13 == ... = 25 mod 27