Power Mod Calculator

Created by Anna Szczepanek, PhD
Reviewed by Wojciech Sas, PhD candidate and Jack Bowater
Last updated: Mar 14, 2022

Omni's power mod calculator is here to help whenever you need to compute powers in modular arithmetic. It uses one of the fast modular exponentiation algorithms, so there's no risk of facing the problem of overflow. Should you ever need to perform exponentiation modulo n by hand, we discuss several helpful methods you can use at home, including Fermat's little theorem.

Modular exponentiation definition

Modular exponentiation means that we perform exponentiation over a modulo, i.e., for the given integers a,b,n we want to find c such that

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

and 0c<n0 \leq c < n. Computing power in modular arithmetic is linked to modular inverses.

You can perform this calculation manually, but it can be very time-consuming. Alternatively, some mathematical theorems allow you to simplify the problem at hand - see below. There are also fast algorithms, which will give you the result almost immediately. We use one of these algorithms in this power mod calculator.

How to use this power mod calculator?

This power mod calculator is very user-friendly, so you'll have no trouble using it. You just need to:

  1. Input the data for computing the power of in modular arithmetic:
    • Base x;
    • Exponent y; and
    • Modulus n.
  2. Your data will be summarized at the bottom of the calc. Verify if everything is all right.
  3. The result of modular exponentiation will appear there as well. That's it!

Our power mod calculator will be your best friend if you're frequently faced with the problem of computing powers in modular arithmetic. Read on if you need to know how to calculate exponentiation modulo n by hand.

Examples of exponentiation modulo

Here we will go through several examples of performing exponentiation modulo by hand using different methods.

Example 1. Direct method

Let's calculate 5⁴ mod 3.

We know that 5⁴ = 625, so our problem is in fact 625 mod 3.

Clearly, 625 is not divisible by 3, but 624 is (this is because the sum of its digits is 6+2+4 = 12, which is divisible by 3).

So 625 - 1 is divisible by 3, which means that 5⁴ mod 3 = 625 mod 3 = 1.

Example 2. Smart method

Let's calculate 5⁴⁴ mod 2.

It's gonna be very hard to compute 5⁴⁴, because this number is very, very big. So, we need to be smart. Recall that mod 2 means that we're asking if the number at hand is even or odd: if it is even, then it's equal to 0 mod 2. If it's odd, it's equal to 1 mod 2.

When we're computing consecutive powers of 5, we get 5, 25, 625,.... As you can see, we always have 5 as the last digit. Indeed, if you have a number with the last digit equal to 5, and you multiply this number by 5, then you're bound to get 5 at the last place again. To see this, imagine performing the long multiplication algorithm - you start by multiplying 5 × 5, and so you get 25. So 5 goes to the result row, and 2 gets transferred to the next column. No matter what happens next, you have 5 as the last digit.

A number that has 5 as its last digit, is odd. So 5⁴⁴ mod 2 = 1.

Example 3. Last digit

Let's calculate 5⁴⁴⁴ mod 10.

First, you need to realize that computing mod 10 is the same as computing the number's last digit. We've already established that raising 5 to any positive integer power gives a number that ends with 5 (see above). Hence, 5⁴⁴⁴ ends with 5 as well, so 5⁴⁴⁴ mod 10 = 5.

Example 4. Fermat's little theorem

Let's calculate 162⁶⁰ mod 61.

Fermat's little theorem states that if n is a prime number, then for any integer a we have:

anmodn=aa^n \operatorname{mod} n = a

If additionally a is not divisible by n, then

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

Hence, since in our case we have n = 61, which is a prime number, and a = 162, which is not divisible by 61, we obtain

162⁶⁰ mod 61 = 1.

FAQ

What is modular exponentiation?

Modular exponentiation means that we're calculating powers in modular arithmetic, that is, performing an operation of the form ab mod n, where a, b and n are integers. If b is negative, modular exponentiation is linked to modular multiplication inverses.

How do I calculate exponential modulo?

If the numbers at hand are not very big, you can simply solve the exponent first and then apply the modulo. Otherwise, you either need to apply some smart reasoning, a math theorem (like Fermat's little theorem or Euler's theorem), or a specialized computer algorithm that performs fast modular exponentiation.

How do I reduce exponential power in modulo?

To reduce power in exponentiation modulo, you need to apply the rules of modular arithmetic, or even some advanced math theorems, like Fermat's little theorem or one of its generalizations, e.g., Euler's theorem.

What is Fermat's little theorem?

Fermat's little theorem is one of the most popular math theorems dealing with modular exponentiation. It has many generalizations, which you can evoke in more complicated calculations. We call it 'little' so as to distinguish it from its much more popular sibling, Fermat's last theorem.

Anna Szczepanek, PhD
x (base)
y (exponent)
n (divisor)
xy mod n = ?
Check out 61 similar arithmetic calculators ➗
Absolute valueAdditionAssociative property… 58 more
People also viewed…

Addiction

Addiction calculator tells you how much shorter your life would be if you were addicted to alcohol, cigarettes, cocaine, methamphetamine, methadone, or heroin.

Free fall

Our free fall calculator can find the velocity of a falling object and the height it drops from.

Pascal's triangle

The Pascal's triangle calculator will compute and show you the exact levels of the triangle you need.

Reference angle

The reference angle calculator finds the corresponding angle in the first quadrant.
Copyright by Omni Calculator sp. z o.o.
Privacy policy & cookies
main background