Matematyka.pl

Oblicz \(\displaystyle{ 3 ^{81}mod10}\) wykorzystując własności operacji modulo.

Widzimy, że \(\displaystyle{ 3^{2}\equiv -1\pmod{10}}\), a zatem \(\displaystyle{ 3^{80}=(3^{2})^{40}\equiv (-1)^{40}\pmod{10}}\), dalej sobie powinieneś poradzić.

A jaki jest ogólny algorytm na rozwiązywanie równań tego typu?

Twierdzenie Eulera bywa przydatne:
... oria_liczb)

Ponadto często korzysta się z takich faktów, że jeśli \(\displaystyle{ a\equiv b \pmod{m}}\), to dla \(\displaystyle{ n}\) naturalnych mamy \(\displaystyle{ a^{n}\equiv b^{n}\pmod{m}}\)
oraz z tego, że jeśli \(\displaystyle{ x \equiv a\pmod{b}}\) i \(\displaystyle{ y \equiv c \pmod{b}}\), to \(\displaystyle{ xy \equiv ac \pmod{b}}\). Również wzór dwumianowy Newtona się przydaje.-- 3 cze 2016, o 13:28 --A ogólnego algorytmu raczej nie ma - ale powyższe fakty zwykle pozwalają rozwiązać takie zadanie.

Ogólnym algorytmem jest chyba stopniowa redukcja potęg i iloczynów do prostszej postaci?