Number Theory is a topic which you will come across frequently in programming contests. I feel this is a topic which has a lot of resources but these resources are scattered. Therefore, I write this tutorial trying to bring in all the best resources together. There are many people who feel I am not good at Math, can I be a good competitive programmer?. This tutorial is for you guys. Don't hesitate to read it as the material here is presented in extremely lucid form and anyone can understand it. Feel free to ask in case you have any doubts.

In many problems especially in problems where the answer can become very very large, you must have found that they ask you to report the answer modulo 10^9+7. Let us learn more about this modulo operator and it's properties.

Introduction

I will strongly encourage you to read all the topics in this section : What is modular arithmetic? (article), starting with "What is modular arithmetic?" and ending with "The Euclidean algorithm". The Euclidean algorithm is a very well know algorithm to find the Greatest Common Divisor (GCD, also known as HCF) of two numbers. Although there are functions to calculate the GCD of two numbers, I strongly recommend you to go through the proof and completely understand it as such concepts may appear in the form of a problem.

Modular Inverse

The article finishes without discussing how to compute mod inverse. Before learning how to write a program to compute mod inverse it is important to know the Extended Euclidean Algorithm. Here is a link to understand what is this algorithm: Extended Euclidean Algorithm

Implementing Greatest Common Divisor (GCD)

If you could not understand the last part, good! We will discuss in fact how to write code to find GCD as well as write code to find the two parameters as mentioned by Extended Euclidean Algorithm.

We will be using recursion so at this point I would ask you to have a look at this if you are not very comfortable with recursion: Introduction To Recursion.

We proved that GCD(A,B) = GCD(B,A%B). We pass parameters to our GCD function in such a way that the first parameter is always larger than the second parameter. This is the reason why we say GCD(A,B)=GCD(B,A%B) and not GCD(A,B)=GCD(A%B,B). We always ensure that our GCD function has the first parameter larger than the second.

Great! What is the base case? What is the recursive case?

int GCD(int A, int B) 
{
    if(B==0) return A;
    return GCD(B,A%B); 
    // Note: A%B is always less than B (property of modulus)
}

Deriving Extended Euclidean Algorithm

Now let us write code to compute the parameters x and y as described in the Extended Euclidean Algorithm. We want use substitution as we saw this is becoming too cumbersome. We will use recursion. Lets go ahead.

We know that,

A*x+B*y=gcd(A,B) .............................................(1)

Extended Euclidean Algorithm finds x and y for us.

=> B*x1 + (A%B)*y1 = gcd(A,B)

[This follows from the Euclidean Algorithm. Remember the recurrence GCD(A,B)=GCD(B,A%B)]

=> B*x1 + (A-[A/B]*B)*y1 = gcd(A,B)

{[A/B] represents floor(A/B)}

Expanding,

B*x1 + A*y1 - [A/B]*B*y1 = gcd(A,B)

Taking B common,

B(x1-[A/B]*B) + A*y1 = gcd(A,B)

=> A*y1 + B*(x1-[A/B]*B) = gcd(A,B)......................(2)

Comparing 1 and 2,

x=y1 and y=x1-[A/B]*B

This shows that if y1 and x1 can be calculated we can calculate x and y. Recursion is our friend!

Implementing Extended Euclidean Algorithm

But what is the base case? If B==0 what are the values of x and y?

A*x+0=A => x=1 and y=0

Here is the code:

long long x,y;
long long extended_gcd(long long a, long long b)
{
	if(b==0){
		x=1;
		y=0;
		return a;
	}
	long long g=extended_gcd(b,a%b);
	long long x1=x;
	long long y1=y;
	x=y1;
	y=x1-((a/b)*y1);
	return g;
}

I hope you can figure out how x1 and y1 are calculated recursively.

In the end x and y will have the required values to satisfy A*x+B*y=gcd(A,B)

Refer: Basic and Extended Euclidean algorithms

Now how do we calculate mod inverse?

We will use the exact same code as above. We have to send the parameters of a and b in a particular way. Lets see how this works.

Look at method 2 in the following link: Modular multiplicative inverse

The parameter x will be the mod inverse of the required number.

Note: In case you are unable to understand the code given in the geeksforgeeks site, do not worry. Use the code I provided above.

Conclusion

That's it! You now know one of the most important topics in number theory modular arithmetic. You have also picked up a very important algorithm called the Euclidean Algorithm. We saw how Euclid extended hos algorithm to find the two parameters x and y and how we computed mod Inverse of a particular number modulo m using the Extended Euclidean Algorithm.

Please feel free to ask in case you have any doubts.