And basic properties with Examples
From Wikipedia :
In Number Theory, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus.
In Modular Arithmetic in competitive programming, we simply have to find answers modulo a given number.
Example : Find remainder when 123 x 234 is divided by 10
Solution : 123 x 234 = 15252 and clearly, answer is 2, because we know that 15250 is divisible by 10
In many questions, the answer grow so large that it becomes impossible to store it in any numerical data structure, especially when answer is factorial, exponent, permutation or combination of a number.
The largest numerical data structure in rust is
i128 for integers,
u128 for unsigned integers and
f64 for decimals.
u128 can store numbers upto order of
1038, which is pretty large, and both take 128 bits to represent.
But now suppose you have to tell the answer of 1000C 500 , which is of order of 10299 . Clearly it is impossible to calculate using traditional computation methods. Even if it is possible in certain languages like python, it takes really long time to compute it and is certainly not suitable for competitive programming.
So, answers are judged on the basis of modulo of answer from a given a number, generally
109+7 or 1000000007. So, it is necessary to know the properties of Modular Arithmetic and their application in order to compute the results efficiently.
It can be extended to multiple numbers.
Example : Calculate remainder of 123 + 234 + 345 when divided by 45.
123 mod 45 = 33
234 mod 45 = 9
345 mod 45 = 30
So, ( 123 + 234 + 345 ) mod 45
= ( 33 + 9 + 30 ) mod 45
123 + 234 + 345 = 702
and 702 mod 45 = 27
It can also be extended to multiple numbers.
Example : Calculate remainder of 123 x 234 x 345 when divided by 47.
123 mod 47 = 29
234 mod 47 = 46
345 mod 47 = 16
So, ( 123 x 234 x 345 ) mod 47
= ( 29 x 46 x 16 ) mod 47
123 x 234 x 345 = 9929790
and 9929790 mod 47 = 6
Note : There is no division property. As an alternative, See Modular Multiplicative Inverse in Rust.
This article covered basics of Modular Arithmetic.
In the next few articles, we will see more advanced properties of Modular Arithmetic.