Kalkulator potęgowania modulo

Omni kalkulator potęgowania modulo pomoże ci zawsze wtedy, gdy potrzebujesz obliczyć potęgi w arytmetyce modularnej. Używa on jednego z szybkich algorytmów potęgowania modularnego, więc nie ma ryzyka napotkania problemu przepełnienia pamięci. A jeśli kiedykolwiek będziesz mieć potrzebę wykonać potęgowanie modulo n ręcznie*, to omówimy kilka pomocnych metod, których możesz użyć w domu, w tym małe twierdzenie Fermata.

Czy znasz nasze pozostałe kalkulatory potęgowania?

• kalkulator mnożenia potęg 🇺🇸
• kalkulator dzielenia potęg 🇺🇸
• kalkulator potęg ułamkowych 🇺🇸
• kalkulator regresji wykładniczej 🇺🇸
• kalkulator wzrostu wykładniczego

Potęgowanie modulo oznacza, że wykonujemy potęgowanie działania modulo, tj. dla danych liczb całkowitych a, b, n chcemy znaleźć c takie, że:

$c = a^b \operatorname{mod}n$

i $0 \leq c < n$. Obliczenie potęgi w arytmetyce modularnej jest związana z odwrotnościami modulo, które możesz odkryć za pomocą naszego kalkulatora odwrotności modulo 🇺🇸.

Możesz wykonać te obliczenia ręcznie, ale zazwyczaj jest to bardzo czasochłonne. Alternatywnie, niektóre twierdzenia matematyczne pozwalają uprościć dany problem — sprawdź poniższe rozdziały. Istnieją również szybkie algorytmy, które dadzą ci wynik niemal natychmiast. Używamy jednego z tych algorytmów w naszym kalkulatorze potęgowania modulo.

Omni kalkulator potęgowania modulo jest bardzo intuicyjny, więc nie będziesz mieć problemów z jego używaniem. Oto kroki, które należy wykonać:

1. Wprowadź dane do obliczenia potęgi x^y w arytmetyce modularnej:
   • podstawa x
   • wykładnik y
   • modulo n
2. Twoje dane zostaną podsumowane w dolnej części obliczenia. Sprawdź, czy wszystko jest w porządku.
3. Pojawi się tam również wynik potęgowania modulo. To wszystko!

Nasz kalkulator potęgowania modulo będzie twoim najlepszym przyjacielem, jeśli często spotykasz się z problemem obliczania potęg w arytmetyce modularnej. Czytaj dalej, jeśli chcesz wiedzieć, jak obliczyć potęgowanie modulo n ręcznie.

Poniżej omówimy kilka przykładów ręcznego potęgowania modulo przy użyciu różnych metod.

Przykład 1. Metoda bezpośrednia

Obliczmy 5⁴ mod 3.

Wiemy, że 5⁴ = 625, więc naszym problemem jest w praktyce 625 mod 3.

Oczywiście 625 nie jest podzielne przez 3, ale 624 jest (ponieważ suma cyfr wynosi 6+2+4 = 12, co jest podzielne przez 3).

Zatem 625 - 1 jest podzielne przez 3, co oznacza, że 5⁴ mod 3 = 625 mod 3 = 1.

Przykład 2. Metoda sprytna

Obliczmy 5⁴⁴ mod 2.

Obliczenie 5⁴⁴ będzie bardzo trudne, ponieważ liczba ta jest bardzo, bardzo duża. Musimy więc być sprytni. Przypomnijmy, że mod 2 oznacza, że pytamy, czy dana liczba jest parzysta, czy nieparzysta: jeśli jest parzysta, to jest równa 0 mod 2. Jeśli jest nieparzysta, to jest równa 1 mod 2.

Kiedy obliczamy kolejne potęgi 5, otrzymujemy 5, 25, 625,… Jak widzisz, zawsze mamy 5 jako ostatnią cyfrę. Rzeczywiście, jeśli masz liczbę z ostatnią cyfrą równą 5 i pomnożysz tę liczbę przez 5, to z pewnością ponownie otrzymasz 5 na ostatnim miejscu. Aby to zobaczyć, wyobraź sobie, że wykonujesz algorytm pisemnego mnożenia — zaczynasz od pomnożenia 5 ⋅ 5, a więc otrzymujesz 25. Tak więc 5 trafia do wiersza wynikowego, a 2 zostaje przeniesione do następnej kolumny. Bez względu na to, co stanie się później, ostatnią cyfrą będzie 5.

Liczba, której ostatnią cyfrą jest 5 jest nieparzysta. Zatem 5⁴⁴ mod 2 = 1.

Przykład 3. Ostatnia cyfra

Obliczmy 5⁴⁴⁴ mod 10.

Po pierwsze, musisz zdać sobie sprawę, że obliczenie mod 10 jest tym samym, co wyznaczenie ostatniej cyfry liczby. Ustaliliśmy już, że podniesienie 5 do dowolnej dodatniej potęgi liczby całkowitej daje liczbę zakończoną 5 (patrz wyżej). Stąd 5⁴⁴⁴ również kończy się 5, więc 5⁴⁴⁴ mod 10 = 5.

Przykład 4. Małe twierdzenie Fermata

Obliczmy 162⁶⁰ mod 61.

Małe twierdzenie Fermata mówi, że jeśli n jest liczbą pierwszą, to dla dowolnej liczby całkowitej a mamy:

$a^n \operatorname{mod} n = a$

Jeśli dodatkowo a nie jest podzielne przez n, to:

$a^{n-1} \operatorname{mod} n = 1$

Stąd, ponieważ w naszym przypadku mamy n = 61, które jest liczbą pierwszą, oraz a = 162, które nie jest podzielne przez 61, otrzymujemy:

162⁶⁰ mod 61 = 1