# Modular Arithmetic in Rust

And basic properties with Examples

## What is Modular Arithmetic

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

## Need of Modular Arithmetic

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.

Now, both `i128` and `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.

## Basic Properties

Mathematically,

(a + b) mod m = ((a mod m) + (b mod m)) mod m

It can be extended to multiple numbers.

Example : Calculate remainder of 123 + 234 + 345 when divided by 45.

Solution :
123 mod 45 = 33
234 mod 45 = 9
345 mod 45 = 30

So, ( 123 + 234 + 345 ) mod 45
= ( 33 + 9 + 30 ) mod 45
= 27

Verifying : 123 + 234 + 345 = 702
and 702 mod 45 = 27

Hence Verified

### 2. Multiplication Property

Mathematically,

(a x b) mod m = ((a mod m) x (b mod m)) mod m

It can also be extended to multiple numbers.

Example : Calculate remainder of 123 x 234 x 345 when divided by 47.

Solution :
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
= 6

Verifying : 123 x 234 x 345 = 9929790
and 9929790 mod 47 = 6

Hence Verified

Note : There is no division property. As an alternative, See Modular Multiplicative Inverse in Rust.