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
and . 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:
- Input the data for computing the power of
xʸin modular arithmetic:
- Your data will be summarized at the bottom of the calc. Verify if everything is all right.
- 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
5⁴ mod 3.
We know that
5⁴ = 625, so our problem is in fact
625 mod 3.
625 is not divisible by
624 is (this is because the sum of its digits is
6+2+4 = 12, which is divisible by
625 - 1 is divisible by
3, which means that
5⁴ mod 3 = 625 mod 3 = 1.
Example 2. Smart method
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
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
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
162⁶⁰ mod 61.
Fermat's little theorem states that if
n is a prime number, then for any integer
a we have:
a is not divisible by
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.
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.