Modulo matinf: Jak wyznaczyć resztę z dzielenia 5²⁰⁰⁹ przez 17 ?

ICSP: 5^16k ≡ 1 mod 17 dla naturalnego k

zombi: Szukamy, żeby potęga dawała 5, dawała jakąś fajną resztę z dzielenia przez 17. 5≡5(mod 17) | ² 5²≡8(mod 17) | *5 5³≡6(mod 17) | ² 5⁶≡2(mod 17) | ⁴ 5²⁴≡(−1)(mod 17) mamy szukaną fajną resztę Teraz musimy się dowiedzieć ile 24 mieści się w 2009, Zauważ, że 2009 = 83*24 + 17 Czyli 5²⁴≡(−1)(mod 17) /⁸³ 5¹⁹⁹²≡(−1)(mod 17) brakuje nam jeszcze / *5¹⁷ 5{2009}≡(−1)*2*2*6*8(mod 17) 5²⁰⁰⁹≡12(mod 17)

zombi: Nie znalazłem tej 1 co ICSP o niej mówi Nie patrz na moje, bo za długo wszystko.

Mila: 5¹⁶=1 (mod17) 5²⁰⁰⁹=5²⁰⁰⁰*5⁹=(5¹⁶)¹²⁵*5⁹ 5²⁰⁰⁰=1 (mod 17) 5³=6(mod17) 5⁹=(5³)³=216(mod17)=12(mod17) 5²⁰⁰⁹=12 (mod17)

5-latek: A mozna to rozwiazac bez modulo? Bo bede mial podobne do rozwiazania

Mila: Można. Napisz swoje zadanie.

5-latek: oblicz reszte z dzielenia 57383⁴ przez 19