__Number Theory : Modular Arithmetic – Part 1__

__Number Theory : Modular Arithmetic – Part 1__

After reading our previous article on GCD Algorithms, we welcome you to our
brand-new article and appreciate your efforts to learn new things till now.
So, in this article we will be looking into some basics of modular
arithmetic.

Let’s start with the formal definition of modular arithmetic.

**Definition from Wikipedia:**
** **
In
mathematics
, **modular arithmetic** is a system of
arithmetic
for
integers
, where numbers "wrap around" when reaching a certain value, called the
**
modulus.
**
In simple words modular arithmetic is dealing with modulus operator
(denoted as ‘%’) and making calculations with big numbers easy.

Suppose you want to multiply two numbers (lets say ‘a’ and ‘b’) and then
divide it by some number (lets say ‘p’) to give out final remainder, easy
task right? But what if ‘a’ and ‘b’ are much bigger number (i.e. as large
as 10^{12} )

then if you first multiply ‘a’ and ‘b’ you will be getting some number
around 10^{24 }which cannot be stored in standard integer datatype
and hence we will be getting wrong answer on doing division with ‘p’.

But, same thing can be done in modular arithmetic very easily, isn’t that
sounds great?.... So, be relaxed and keep reading this article to get
answer to your questions 😊

let’s first understand
**
what does modulus operator gives?
**
E.g. you are asked to divide 27 by 5 (i.e. 27 / 5 = ?)

We will do integer division of 27 by 5, to see the magic !!

So, here we get 27 / 5 = 5(quotient) as shown above, and the remainder i.e. 2 is what modulus operator gives. Hence 27 % 5 = 2(remainder)

So, after gaining knowledge of modulus operator let’s dive deep into some cool properties of modular arithmetic.

##

__Property 1 - Quotient – Remainder Theorem:__

__Property 1 - Quotient – Remainder Theorem:__

__
__

**For, two positive integers A and B, there exist integer ‘q’ and ‘r’ such that**

**A = B * q + r where 0 <= r < B
** here B is Divisor, r is remainder, q is quotient

hope you remembered this interesting property sounded as

**Dividend = Divisor * quotient + remainder**

**
**hence, we can write 27 / 5 in above form as:

**27(dividend) = 5(divisor) * 5(quotient) + 2(remainder)**

**proof of this property:**

This property can be easily proved, by reverse processing.

1. In simple words if your Divisor (i.e. 5 in our case) is greater than Dividend (i.e. 27 in our case) we can divide our Dividend (i.e. 27) into equal parts till we reach a number smaller than Divisor (i.e. 5) and the left over number is our remainder as discussed above.

2. So, finally if we multiply our Quotient ( i.e. 5 in our case) with Divisor ( i.e. 5) we are actually multiplying our Divisor (i.e. 5) with number of equal parts we obtained (i.e. 5) and then finally adding the remainder to answer as we were not able to divide our remainder.

__Property 2 – Addition Property:__

__Property 2 – Addition Property:__

**
**According to this property, If **a + b = c****, then a (modN) + b (modN) ≡ c (modN).
**

**
**In simple words

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

Lets, take an example to understand this property clearly

E.g. (10 + 12) % 7

= ((10 % 7) + (12 % 7)) % 7

= (3 + 5) % 7

= 8 % 7

= 1

as (10 + 12) % 7 = (22) % 7 = 1 hence we can see that this property is
verified.

** **

__Proof of this property:__** **
**(a + b) % m = ((a % m) + (b % m)) % m**
**
**
Consider a = m * q1 + r1

**b = m * q2 + r2 … writing ‘a’ and ‘b’ in property 1 form ( i.e.**

**Dividend = Divisor * quotient + remainder )**

Note: here r1 = ( a % m) and r2 = ( b % m) and q1, q2 are quotient.

Note: here r1 = ( a % m) and r2 = ( b % m) and q1, q2 are quotient.

**Now,**

**( a + b ) % m = ( m * q1 + r1 + m * q2 + r2 ) % m**….(substituting values of ‘a’ and ‘b’ )

= ( ( (m * q1) % m ) + (r1 % m) +( (m * q2) % m ) + (r2 % m) ) % m

since, (m * q1) % m = (m * q2) % m = 0,

**E.g. ( 7 * 5 ) % 7 = 0**

Hence, we have our expression as,

= ( (r1 % m) + (r2 % m) ) % m = ( r1 + r2 ) % m

therefore from our Note, above we can rewrite above expression as below:

= ( ( a % m ) + ( b % m ) ) % m

Hence, we proved that

**( a + b ) % m = ( ( a % m ) + ( b % m ) ) % m**

**
**

__Property 3 – Subtraction Property:__

__Property 3 – Subtraction Property:__

**
****(a - b) mod m = ((a mod m) - (b mod m)) mod m
**Lets, take an example to understand this property clearly

E.g. (20 - 12) % 7

= ((20 % 7) - (12 % 7)) % 7

= (6 - 5) % 7

= 1 % 7

= 1

as (20 - 12) % 7 = (8) % 7 = 1 hence we can see that this property is
verified.

** **

__Proof of this property:__** **
**(a - b) % m = ((a % m) - (b % m)) % m**
**
**
Consider a = m * q1 + r1

**b = m * q2 + r2 … writing ‘a’ and ‘b’ in property 1 form ( i.e.**

**Dividend = Divisor * quotient + remainder )**

Note: here r1 = ( a % m) and r2 = ( b % m)

Note: here r1 = ( a % m) and r2 = ( b % m)

**Now,**

**( a - b ) % m = ( m * q1 + r1 - m * q2 - r2 ) % m**….(substituting values of ‘a’ and ‘b’ )

= ( ( (m * q1) % m ) + (r1 % m) - ( (m * q2) % m ) - (r2 % m) ) % m

since, (m * q1) % m = (m * q2) % m = 0, E.g. ( 7 * 5 ) % 7 = 0

Hence, we have our expression as,

= ( (r1 % m) - (r2 % m) ) % m = ( r1 - r2 ) % m

therefore from our Note, above we can rewrite above expression as below:

= ( ( a % m ) - ( b % m ) ) % m

Hence, proved that

**( a - b ) % m = ( ( a % m ) - ( b % m ) ) % m**
**
**

**
**

__Property 4 – Multiplication Property:__

__Property 4 – Multiplication Property:__

__
__**(a * b) mod m = ((a mod m) * (b mod m)) mod m
**Lets, take an example to understand this property clearly

E.g. (10 * 12) % 7

= ((10 % 7) * (12 % 7)) % 7

= (3 * 5) % 7

= 15 % 7

= 1

as (10 * 12) % 7 = (120) % 7 = 1 hence we can see that this property is
verified.

** **

__Proof of this property:__** **
**(a * b) % m = ((a % m) * (b % m)) % m**
**
**
Consider a = m * q1 + r1

**b = m * q2 + r2 … writing ‘a’ and ‘b’ in property 1 form ( i.e.**

**Dividend = Divisor * quotient + remainder )**

Note: here r1 = ( a % m) and r2 = ( b % m)

Note: here r1 = ( a % m) and r2 = ( b % m)

**Now,**

**( a * b ) % m = ( (m * q1 + r1 ) * (m * q2 + r2 ) % m**….(substituting values of ‘a’ and ‘b’ )

= ( (m * q1) * (m * q2) + (r1 * m * q2) + (r2 * m * q1) + (r1 * r2) ) % m

since, (m * q1) % m = (m * q2) % m = 0,

**E.g. ( 7 * 5 ) % 7 = 0**

Hence, we have our expression as,

= ( r1 * r2 ) % m

therefore from our Note, above we can rewrite above expression as below:

= ( ( a % m ) * ( b % m ) ) % m

Hence, proved that

**( a * b ) % m = ( ( a % m ) * ( b % m ) ) % m**

**
**After reading above properties you may make a conclusion that we can do same modular magic with division operator, say

**( a / b ) % m = ( ( a % m ) / ( b % m ) ) % m**

**Lets, take an example to understand this property clearly**

E.g. (30 / 10) % 7

= ((30 % 7) / (10 % 7)) % 7

= (2 / 3) % 7

= 0.67 % 7

= Not a number, and according to mathematics we cannot find remainder of
floating-point numbers

as (30 / 10) % 7 = (3) % 7 = 3 hence we can see that this property is not working fine for division.

Hence, note here that this property does not work for division operator,
for make it work we would have to use modular inverse which we will be
covering in our upcoming articles.
**
**

**
**__
Property 5 – Congruence Property:
__

__Property 5 – Congruence Property:__

‘**a**’ and ‘**b**’ are said to be congruent to
each other under modulo ‘**N**’, if they leave same remainder
when divided by ‘N’. i.e. **a ****≡ b ( mod N)**
**
**

Let’s take an example to understand it clearly.

E.g. **13 ****≡ 41 (mod 7) ** here a = 13, b = 41
and N = 7

Now, since we have 13 % 7 = 6 which is same as 41 % 7 = 6 hence we can
write above expression since they give same remainder when divided by 7.

One important point to note here is if we add same integers on both side of
our original equation we still have the same result i.e. they do not loose
their congruency.

E.g. ( 13 + 35 + 5 ) % 7 = 53 % 7 = 4

( 41 + 35 + 5 ) % 7 = 81 % 7 = 4

i.e. they still are congruent and obey this property.

**
Important observations:
**

**1. If a ≡ b (mod N)**

then

**a – b ≡ 0 (mod N)**i.e. absolute( a – b ) is divisible by N

E.g. 13 ≡ 41 ( mod 7) à absolute(13 – 41) = 28 (mod 7) = 0 (mod 7)

2. If a ≡ b (mod N)

then there exist an integer ‘k’ such that a – b = N * (±k) i.e. **a = N * (**±**k) + b**

E.g. 13 ≡ 41 (mod 7) then we have k = ±4;

**13 = 7 * (-4) + 41 and 41 = 7 * 4 + 13**

3. If a ≡ b (mod N) and c ≡ d (mod N)

then

** ( a * c ) % N ≡ ( b * d ) % N**

E.g. 13 ≡ 3 (mod 5) and 9 ≡ 4 (mod 5)

(13 * 9) % 5 ≡ ( 3 * 4) % 5

( 117 ) % 5 ≡ (12 ) % 5

** 2 % 5 ≡ 2 % 5 **
Hence, the property is totally verified.

Below, is summary of this article to revise what we have learned in this
article quickly.

**Summary: **
1. **Dividend = Divisor * quotient + remainder**
**
**

**2.**

**( a + b ) % m = ( ( a % m ) + ( b % m ) ) % m**

**3.**

**( a - b ) % m = ( ( a % m ) - ( b % m ) ) % m**

4.

**( a * b ) % m = ( ( a % m ) * ( b % m ) ) % m**

5. **a ****≡ b ( mod N)**
**
**

**
Conclusion:
**
This was some basic concepts of Modular Arithmetic which you should be
familiar with while doing competitive programming. And in our upcoming
articles we will be covering some intermediate concepts of Modular
Arithmetic along with cool explanation by Programmers Army.

So that’s it for this article we will be coming up with our next article on
further topics of number theory very soon till then keep learning, keep
coding, keep reading and keep improving !!

Happy Coding 😊

By **Programmers Army**