Number Theory : Modular Arithmetic – Part 2

After clearing your basics of Modular Arithmetic in our previous article, it is the best time to learn some new and important concepts in modular arithmetic.

So, be relaxed and keep reading we will be making it super easy for you to understand and absorb new concepts 😊

Note: If you have not read our previous article on Modular Arithmetic – Part1, we highly recommend you to read it by clicking here, as we will be using some concepts of that article here.

let’s start with our first topic:

1. Modular Exponentiation

Now, you may think how or where is this property useful? So, let’s have a look at below scenario.
Suppose you are given a task to find out 29¹⁰ (mod 3), you can imagine how big this number is and completing this task is practically impossible without modular exponentiation.

So, how modular exponentiation solves this problem?
It’s very simple first of all you need to find such a number which gives same remainder as 29 when divided by 3, that number is 2 in our case as,
29 % 3 = 2 % 3 = 2

Hence, we can write 29 ≡ 2 (mod 3) great, now we will be applying property of modular exponentiation here, we get

If 29 ≡ 2 (mod 3) then 29¹⁰ ≡ 2¹⁰ (mod 3) ….by modular exponentiation.

so, now if we calculate 2¹⁰ (mod 3) = 1024 (mod 3) = 1 is same as what we get by doing 29¹⁰ (mod 3) isn’t that interesting and it made our calculation so easy, that’s why number theory is so much cool and awesome to learn.

Why don’t you try to get what 2^123456789 (mod 7) ≡ ? will be congruent to..it would be fun and learning do give it a try, if you got stuck google is always here to help you :)

---

2. Modulo Multiplicative Inverse

Did you remembered from our previous article that modular arithmetic won’t work same for division operation so for make it work for division operators we make use of modulo multiplicative inverse.

Now, let’s understand this concept formally.

Definition: Modulo Multiplicative inverse of a number ‘N’ under modulo ‘P’ is defined to be a number X such that N * X ≡ 1 (mod P).

E.g. Modulo Multiplicative inverse of 5, under modulo 7 is 3, since 5 * 3 ≡ 1 (mod 7)

Note: Modulo inverse of N, under modulo P exist if and only if N & P are Co-Prime with each other i.e. GCD( N , P) = 1 i.e. They should not have common prime divisors.

So,

Now, coming to implementation part or coding part so there are basically 2 ways to calculate modulo inverse efficiently.

1. Using Fermat’s Little Theorem.
2. Using Extended Euclidean Algorithm.

Note: Time Complexity of both the algorithm is almost same.

Let’s look at fermat’s little theorem.

A. Fermat’s little theorem

Fermat’s little theorem says that a^m-1 ≡ 1 mod m ….1

m is Prime Number, a is any integer and GCD(a,m) = 1 i.e. a and m are co-prime i.e. they do not have same or common prime divisors.

therefore, dividing by ‘a’ in equation 1,

Below is the implementation of above logic:

Time Complexity: O(Log m)

We will be discussing Extended Euclidean Algorithm in separate article as it have some great concept associated with it, and we don’t want to mix it with the concepts in this article.

It is always better to solve a question after you learn a new concept as it helps in making concrete concepts.

So, below are problems which are handpicked by Programmers Army to make your concept more solid which you learned.

We highly recommend to solve above problems if you got stuck read editorials for guidance.

Conclusion: We learned Modular Exponentiation and Modulo Multiplicative Inverse in this article and implemented modulo multiplicative inverse with use of fermat’s little theorem.

So that’s it for this article we will be coming up with our next article on further topics of number theory very soon till then keep learning, keep coding, keep reading and keep improving !!

Happy Coding

By Programmers Army 😊