oblicz resztę z dzielenia vito: Korzystając z Małego Twierdzenia Fermata oblicz resztę z dzielenia liczby 6¹⁰⁰⁰ przez 13. Wcześniej robiłem to tak, że wyznaczałem 6¹⁰⁰⁰ mod 13 6=13*0+6 Czyli 13 nie dzieli 6. No i teraz powinno mi wyjść 6¹⁰⁰⁰ ≡ i tutaj powinna wyjść ta reszta do potęgi 1000 tylko, że u nas reszta wynosi 6.

jc: 6¹² = 1 (mod 13), 6²=−3 (mod 13), 6⁴=9 (mod 13) Dlatego 6¹⁰⁰⁰ = (6¹²)⁸³*6⁴=9 (mod 13)

vito: Mógłbyś to krok po kroku wyjaśnić jak rozwiązać ?

jc: Czy znasz oznaczenie a=b (mod n)?

vito: Nie, chyba, że oznacza to tyle co a jest resztą z dzielenia b/n

vito: Doczytałem, że to oznacza tyle iż a i b podzielone przez n da nam taką samą resztę. Dalej nie wiem skąd wzięliśmy 6¹² , 6², 6⁴

jc: a = b (mod n) oznacza, że n| a−b Relacja przystawania ma podobne własności do relacji równości. 6² = 36 = −3 (mod 13) bo 13 | 36 − (−3)= 39 Jeśli a = b (mod n) c = d (mod n) to ac = bd (mod n) 6⁴ = (6²)² = (−3)² = 9 (mod 13) 6⁶ = (6²)³ = (−3)³ = −27 = −1 (mod 13) 6¹² = 1 (mod 13) to jest właśnie MTF 1000 = 12*83+4 6¹⁰⁰⁰=(6¹2)⁸³*6⁴ = 6⁴ = 9 (mod 13)

Mila: 6¹⁰⁰⁰=x (mod13) Z tw. Fermata 13− liczba pierwsza 6⊥13 − liczby względnie pierwsze⇔6¹³⁻¹=1 (mod13) 6¹²=1 (mod13) ( czyli 6¹²=13k+1, k∊N ) ================================ 1000=12*83+4 (6¹²)⁸³ 6¹⁰⁰⁰=(6¹²)⁸³*6⁴ 6⁴=1296=99*13+9⇔ 6⁴=9(mod13) (6¹²)⁸³=1(mod13) 6⁴=9(mod13) stąd (6¹²)⁸³*6⁴=1*9(mod13)=9(mod13)⇔ 6¹⁰⁰⁰=13*m +9, m∊N ===================