aa Hugo: Liczenie wysokich potęg z modulo − Euler nawiązuje tutaj do wątku ktory probóje zrozumieć https://matematykaszkolna.pl/forum/223751.html 77¹³³mod80 Trivial robił tutaj na: 133 = 128 + 4 + 1 = 2⁷ + 2² + 1\ następnie pisze: Podnosimy 77 do kwadratu 7 razy (modulo 80): 77*77 = 5929 5929−74*80 = 9 tylko że 5929*5929*5929*5929*5929*5929*5929 // to strasznie duza liczba, czy da się to jakoś ladniej?

ABC: 77≡−3 mod 80 77⁴≡(−3)⁴=81≡1 mod 80

Adamm: z tw. Eulera 80 = 16*5 77¹³³ ≡ 2 (mod 5) 77¹³³ ≡ (−3)⁵ = −3*81 ≡ 13 (mod 16) ⇒ 77¹³³ ≡ r (mod 80) 0≤r<80 to r∊{13, 29, 45, 61, 77} ale r ≡ 2 (mod 5), więc 77¹³³ ≡ 77 (mod 80)

Hugo: to tak można ? modulować gdy wisi w powietrzu znak potęgi? rozumiem że wykonywałeś cząstkę 2², a nie 2*7 idąc Twoim tokiem myślenia, 77 do potęgi 2⁷ mod 80 = (−3) do potęgi 2⁷ mod 80 = 9⁷mod80 = 4782969mod80 4782969−59787*80 = 9 Trivial wyszlo 1 dla 2⁷, gdzie się rąbnąłem ?

ABC: 77¹³³=77¹³²*77=(77⁴)³³*77≡1³³*77=77 tak możesz na piechotę sprawdzić

Hugo: kurde genialne ! dziekuje może zdam

Hugo: A inny przykład bo zacząłem liczyć i średnio 42²³mod187 rozbijamy 23 = 2*11+1 (42²)¹¹*42 mod187 (1764 )¹¹*42 mod187 (1764−187*9)¹¹*42 mod187 81¹¹*42 mod187 rozbijamy 11 = 5*2+1 81^5*2*81*42 mod187 67*81*42mod187 = 168 swietne ! caly semestr probowalem to wykminić