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.

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¹² )

then if you first multiply ‘a’ and ‘b’ you will be getting some number around 10²⁴ 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:

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

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:

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

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.

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:

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)

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:

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)

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

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:

‘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.

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

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