# 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,

**for unsigned integers and**

`u128`

**for decimals.**

`f64`

Now, both ** i128** and

**can store numbers upto order of**

`u128`

**, which is pretty large, and both take 128 bits to represent.**

`10`^{38}

But now suppose you have to tell the answer of ** ^{1000}C _{500}** , which is of order of

**10**. 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.

^{299}So, answers are judged on the basis of modulo of answer from a given a number, generally ** 10**. So, it is necessary to know the properties of Modular Arithmetic and their application in order to compute the results efficiently.

^{9}+7 or 1000000007

## Basic Properties

### 1. Addition Property

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.

## Conclusion

This article covered basics of Modular Arithmetic.

In the next few articles, we will see more advanced properties of Modular Arithmetic.

**Thank You**