modulo Property for competitive programming | Most Important properties of modulo,modulo property

 GCD Property for competitive programming -

properties of modulo or modulo property play important role in competitive programming. Some of the Problems of competitive programming is directly asked based on properties of modulo or modulo property. So here are some most important Modulo Properties That you should know.

 

What is modulo operation: 
The remainder obtained after the division operation on two operands is known as modulo operation. Operator for doing modulus operation is ‘%’. For ex: a % b = c which means, when a is divided by b it gives the remainder c, 7%2 = 1, 17%3 = 2.

        

 Important properties of modulo-

1. ( a + b) % c = ( ( a % c ) + ( b % c ) ) % c
2. ( a * b) % c = ( ( a % c ) * ( b % c ) ) % c
3. ( a – b) % c = ( ( a % c ) – ( b % c ) ) % c
4. ( a / b ) % c = ( ( a % c ) / ( b % c ) ) % c

Basic Euclidean Algorithm for GCD-

• If we subtract smaller number from larger (we reduce larger number), GCD doesn’t change. So if we keep subtracting repeatedly the larger of two, we end up with GCD.
• Now instead of subtraction, if we divide a smaller number, the algorithm stops when we find remainder 0.

GCD calculation is a recursive approach and modulo expression also used while calculating GCD of two numbers.

int gcd(int a, int b)

{

    if (a == 0)

        return b;

    return gcd(b % a, a);

}

What is the concept of taking modulo by 1000000007?

This is done to avoid calculations involving very large numbers.
If you take mod after the final (actual) answer it would defeat the very purpose of using the mod operator in the question.

Thanks for reading this post. 

Code discussion It's a community where you people helps each other.

Join me on telegram-https://t.me/competitiveProgrammingDiscussion