Wyznacz resztę z dzielenia \(\displaystyle{ 787^{435}}\) przez \(\displaystyle{ 15}\)
Znalazłem multum tematów z podobnymi zadaniami, ale w żadnym nie dowiadziałem się skąd co się bierze. Znam małe twierdzenie fermata oraz eulera, lecz nie wiem jak je zastosować. Byłbym ogromnie wdzięczny gdyby ktoś mi wytłumaczył jak zrobić to zadanie.
Reszta z dzielenia \(\displaystyle{ 787}\) to \(\displaystyle{ 7}\), więc reszta z dzielenia potęgi jest taka jak z dzielenia \(\displaystyle{ 7^{435}}\). Masz, że \(\displaystyle{ 7^4}\) daje resztę \(\displaystyle{ 1}\), bo \(\displaystyle{ 7^2}\) ma resztę \(\displaystyle{ 4}\), a \(\displaystyle{ 4\cdot 4}\) ma resztę \(\displaystyle{ 1}\). Jesteśmy w domu: \(\displaystyle{ 7^{435}=7^{4\cdot 108+3}=(7^4)^{108}\cdot 343}\), więc reszta jest taka jak z \(\displaystyle{ 343}\). Wynosi więc \(\displaystyle{ 13}\). Uzupełnij szczegóły. Tzn. czemu można działać na resztach tak jak opisuję.
