Najlepsza odpowiedź
Najpierw musimy spojrzeć na moduł (lub liczba, przez którą „próbujemy podzielić). W tym przypadku jest to 1818. Następnie wstawiasz 1818 do funkcji totient Eulera , aby uzyskać ϕ (18) ϕ (18) W szczególności dla wszystkich liczb całkowitych nn mamy
ϕ (n) = n∏p | n (1−1p), ϕ (n) = n∏p | n (1−1p),
gdzie produkt przechodzi przez wszystkie unikalne czynniki pierwsze liczby nn. W tym przypadku
ϕ (18) = (18) (1/2) (2/3) = 6. (18) = (18) (1/2) (2/3) = 6.
Ok, więc następnym krokiem jest twierdzenie Eulera , które mówi, że dla każdej innej liczby całkowitej aa, czyli względnie pierwsza do nn, mamy to, że aa do potęgi ϕ (n) ϕ (n) pozostawia resztę z 11 po podzieleniu przez nn. To znaczy
aϕ (n) ≡1 (modn) .aϕ (n) ≡1 (modn).
Od 1717 roku jest rzeczywiście względnie pierwsze w stosunku do 1818 roku, znamy 176176 liści przypomnienie o 1. Oznacza to, że możemy po prostu dalej dzielić 176176 z 1720017200 bez zmieniania pozostałych. Innym sposobem na powiedzenie tego jest to, że 17 do dowolnej potęgi będącej wielokrotnością 6 pozostawi resztę z 1. W końcu, ponieważ 200 to 2 więcej niż wielokrotność 6, wiemy, że
17200≡172 (mod18) .17200≡172 (mod18).
To znacznie upraszcza problem – prawie jesteśmy na miejscu! Skrótem do zakończenia problemu jest uświadomienie sobie, że 1717 pozostawia resztę −1−1 po podzieleniu przez 1818 (tj. 17≡ − 1 (mod18) 17≡ − 1 (mod18)), więc 172172 pozostawia resztę z (- 1) 2 = 1. (- 1) 2 = 1.
Tak więc nasza odpowiedź brzmi 1 . Następnym razem będziesz mieć problem z pozostałymi sporej mocy można zastosować to ładne uogólnione rozwiązanie i jednocześnie brzmieć sprytnie :). Jeśli nie widziałeś wcześniej notacji modmod, zobacz Arytmetyka modularna .
PS Być może słyszałeś o specjalnym przypadku tego twierdzenia zwane małe twierdzenie Fermata , które działa, gdy masz moduł będący liczbą pierwszą (nie w tym przypadku). Twierdzenie mówi, że dla dowolnej liczby pierwszej pp i liczba całkowita aa, która nie jest wielokrotnością pp,
ap − 1≡1 (modp) .ap − 1≡1 (modp).
To ciekawa sztuczka, ale jej w zasadzie to samo, co „s powyżej, ponieważ ϕ (p) = p − 1ϕ (p) = p − 1 dla dowolnej liczby pierwszej pp. Pytania tego typu stają się naprawdę proste, jeśli zrozumiesz pojęcie reszty ujemne . Zawsze próbuj i zmniejsz dywidendę do 1 lub -1.
Rem [17 ^ 200/18] = Rem [(-1) ^ 200/18] = Rem [1/18] = 1
Odpowiedź
Ważna podstawa potrzebna do rozwiązania problemu :
Wiemy, że reszta uzyskana z dzielenia r pq jest iloczynem reszt uzyskanych z dzielenia p i q oddzielnie. Nazywa się to lematem na resztach. Możesz to udowodnić twierdzeniem Euklidesa o dzieleniu.
Rozwiązanie
17 po podzieleniu przez resztę 18 liści -1 (wygodniej jest pracować z -1 niż 17)
Zastosowanie pozostałego lematu do 17 × 17 × 17 … × 17 (2000 razy) po podzieleniu przez 18 zostanie uzyskana, gdy poszczególne reszty są mnożone tj. -1 × -1 .. × -1 (2000 razy) czyli reszta to 1 \ blacksquare
Gdyby było 17 podniesione do jakiejś nieparzystej, reszta wyniosłaby -1 lub 17 .