Najlepsza odpowiedź
2 ^ 30 * 3 ^ 20
= (2 ^ 3) ^ 10 * (3 ^ 2) ^ 10
= 8 ^ 10 * 9 ^ 10
= (8 * 9) ^ 10
= 72 ^ 10
od 72 mod 7 = 2,
72 ^ 10 mod 7
= (2 ^ 10) mod 7
= 1024 mod 7
= 2
Odpowiedź
Możesz po prostu odpalić komputer i zapytać, a ja dostałem 1091132094649, ale musisz mieć na myśli, jak można to zrobić przy użyciu minimum ołówka i papieru, lub jak można rozwiązać znacznie większy problem na komputerze bez nadmiernego wykorzystania cykli procesora.
Prawdopodobnie chcą chińskiego twierdzenia o resztach do tego. 20 = 2 ^ 2 * 5, więc 20 ^ 10 = 2 ^ 20 * 5 ^ 10.
Więc co to jest 3 ^ 30 mod 5 ^ 10? Pracuj w arytmetyce o podstawie 5. 3 ^ 3 = 102, 3 ^ 6 = 102 * 102 = 10404, 3 ^ 12 = 114001231, teraz pomnóż przez 3 ^ 3 = 102, ale ODRZUCAJĄC wszystkie cyfry poza dziesiątą potęgą 5: 12133131112 przycina do 2133131112. Na koniec wyrównaj to do kwadratu na zewnątrz, odrzucając wszystko powyżej dziesiątej potęgi 5: 4304012044. Podstawa 10, aby wrócić do znanego terenu, to jest 9047774.
Teraz potrzebujesz 3 ^ 30 mod 2 ^ 20. To samo ćwiczenie, ale tym razem pracujesz w systemie binarnym. W końcu dowiadujesz się, że jest to 686265 mod 2 ^ 20.
Nadszedł czas na chińskie twierdzenie o resztach. To mówi, że biorąc pod uwagę dwa względnie pierwsze moduły, tutaj 2 ^ 20 i 5 ^ 10, i każdy z warunków zgodności, tutaj odpowiedź to 9047774 mod pierwszy i 686265 mod drugi, istnieje unikalne n między 0 a iloczynem Twoje moduły, mniej 1. I znajdujesz to dzięki idei, że jeśli n = a mod p i b mod q, to n = a + pk, więc (a + pk) = b mod q. więc pk = (b-a) mod q, więc k = (odwrotność p) * (b-a) mod q. I odwrotność p mod q znajduje się za pomocą rozszerzonego algorytmu euklidesowego. (Wydobywasz gcd z p i q, wiedząc doskonale, że na końcu będzie 1, ale śledząc, czego się dowiadujesz o s * p + t * q = coraz mniejszy i mniejszy, w miarę upływu czasu, aż uzyskasz s * p + t * q = 1, a następnie s jest odwrotnością p mod q.)