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
It simply says if you have a ≡ b (mod N) then ak ≡ bk (mod N).
Let’s understand this with an example: we have16 ≡ 1 (mod 3) then according to modular exponentiation 162 ≡ 12 (mod 3) = 1 (here k = 2) hence we verified this property.
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 2910 (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 2910 ≡ 210 (mod 3) ….by modular exponentiation.
so, now if we calculate 210 (mod 3) = 1024 (mod 3) = 1 is same as what we get by doing 2910 (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 2123456789 (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.
what exactly is modulo multiplicative inverse?
In modulo multiplicative inverse we actually find the equivalent multiplication factor for the denominator in division expression and then instead of doing division operation we actually do multiplication operation to get the same result as we will be getting with division,
So by doing this we have successfully transformed our division into multiplication and now we can apply the modulo multiplicative property on this expression.
let’s take an example to understand it more clearly:
E.g1. suppose we want to do 10 / 5 (taking small number for better understanding)
so, here instead of dividing 10 by 5 we will find an equivalent multiplication factor for 1 / 5 that would give us the same result as dividing 10 by 5.
So, equivalent multiplication factor for 1/5 would be 0.2,
Hence, we have
10 / 5 = 10 * 0.2 = 2;
E.g2. Calculate ( 6 / 2 ) % 5: ….Note here GCD(2,5) = 1
Let’s suppose multiplicative inverse of ½ is 3, hence our expression becomes.
( 6 / 2 ) % 5 = ( 6 * (½) ) % 5 = ( 6 * 3 ) % 5 = ( 18 ) % 5 = 3 which is same as ( 6 / 2 ) % 5 = 3 % 5 = 3
Therefore we can summarize our discussion as below formula.
( A / B ) % P = ( A * X ) % P = ( ( A % P ) * (X % P) ) % P
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 am-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,
a m-2 ≡ a-1 mod m, which can be written as below
a-1 ≡ am-2 mod m, this is what we wanted to get i.e. a-1
Below is the implementation of above logic:
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.
1. Problem from CodeChef:
2. Problem from HackerEarth: https://www.hackerearth.com/problem /algorithm/modulo-inverse-problem/
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.
Below is short glimpse for quick revision.
1. if you have a ≡ b (mod N) then ak ≡ bk (mod N) … Modular Exponentiation
2. ( A / B ) % P = ( A * X ) % P = ( ( A % P ) * (X % P) ) % P Modulo Multiplicative Inverse.
3. a-1 ≡ am-2 mod m where m is prime number, it is 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 !!
By Programmers Army 😊