Zapis dziesiętny. Mariusz: Podaj cztery ostatnie cyfry zapisu dziesiętnego jakiejś liczby. Jak zrobić zadania tego typu? Np, 1414²015 Myślę, że to będzie jakiś "ciąg" nastepujacych po sobie liczb ale nie mam nawet jak tego sprawdzić bo mi się miejsce w kalkulatorze kończy

Mariusz: 1414²⁰¹⁵ miało być

Adamm: 10000=2⁴*5⁴=16*625 1414 = 6 mod 16 φ(16)=8 2015 = 7 mod 8 6²⁰¹⁵ = 2²⁰¹⁵*3²⁰¹⁵ = 8*3⁷ = 24*3⁶ = 8*3⁶ = ... = 8 mod 16 1414 = 164 mod 625 φ(625)=500 164²⁰¹⁵ = 164¹⁵ = 164*26896⁷ = 164*21⁷ = 164*21*441³ = = −164*21*184³ = −3444*184³ = −319*184³ = −319*106*184 = −319*129 = = 99 mod 625 reszty mogą być 99, 99+625, 99+2*625, ... ale dodatkowo muszą dać resztę 8 z dzielenia przez 16, czyli być podzielne przez 8 99 daje resztę 3 625 daje 1 99+5*625 albo 99+13*625 to kandydaci, ale drugi jest podzielny przez 16 czyli reszta to 3224 i takie są ostatnie 4 cyfry

Adamm: coś pokręciłem, bo powinno być 8224

Mariusz: Dobra, wielkie dzięki za rozpisanie tego wszystkiego. ALE co to jest za znak φ i co oznacza mod?

Adamm: no tak 6²⁰¹⁵ = 0 mod 16 tak samo jak 2²⁰¹⁵ = 0 mod 16 w takim razie reszta postaci 99+k*625 i musi być podzielna przez 16, więc wynosi 99+13*625 = 8224

Adamm: mod to relacja 2 liczby całkowite a, b są a = b mod n jeśli n|(a−b) lub inaczej jeśli dają taką samą resztę z dzielenia φ(n) to tocjent https://pl.wikipedia.org/wiki/Funkcja_%CF%86 po drodze korzystałem z https://pl.wikipedia.org/wiki/Twierdzenie_Eulera_(teoria_liczb)

Mariusz: Kurde, będę musiał nad tym posiedzieć. Jeszcze raz dziękuję