Understanding the Power of Modular Arithmetic in Programming: A Deep Dive into the Multiplication Property

Introduction

Modular arithmetic is a fundamental concept in mathematics and computer science, with applications spanning cryptography, number theory, and algorithm design. One of its most useful properties is the multiplication rule, which states that

(𝑎×𝑏)%𝑚= ( (𝑎%𝑚)×(𝑏%𝑚) )%𝑚

This article explores this property in detail, explaining its significance, mathematical foundation, and practical applications in programming.

What is Modular Arithmetic?

Modular arithmetic deals with integers and a special operation called the modulo operation. This operation finds the remainder when one number is divided by another. For example, 7%3=17%3=1 because 7 divided by 3 leaves a remainder of 1.

The Multiplication Property in Modular Arithmetic

One of the key properties of modular arithmetic is the multiplication rule. This rule can be stated as follows: When you multiply two numbers and then take the result modulo m, it is equivalent to first taking each number modulo m, then multiplying these results, and finally taking the result modulo 𝑚m. Mathematically:

(𝑎×𝑏)%𝑚= ( (𝑎%𝑚)×(𝑏%𝑚) )%𝑚

Why This Property Holds

To understand why this property holds, consider the mathematical definition:

• Let’s say a = q1⋅m+r1 ​ and b= q2⋅m+r2 where 𝑟1​ and 𝑟2​ are the remainders when 𝑎 and 𝑏 are divided by 𝑚, respectively. Hence, 𝑟1=a%m and 𝑟2​=b%m.
• When we multiply a and 𝑏

a×b=(q1​⋅m+r1​)×(q2​⋅m+r2​)

Expanding this:

• Notice that every term except 𝑟1⋅𝑟2 contains 𝑚 as a factor, meaning they will contribute 0 to the remainder when divided by 𝑚.
• Thus:

• Therefore:

Application

1. What exactly is “print it modulo 10⁹ + 7” in competitive programming web sites?

This is one of the most common question scenario that uses the multiplication property of modulus.

Few thing need to be consider that are:

1. 10⁹ + 7 is a prime number.
2. Sometimes when answer in the form of (ans)%(10⁹+7), this means that the actual answer to a problem lies above the range of 64-bit integer which is not possible to calculate so they want only the remainder left behind our actual answer.

Example

Suppose you are given a problem where you need to compute the sum of the first 𝑛 positive integers and print the result modulo 10⁹+7.

The sum of the first 𝑛n positive integers is given by:

𝑆=𝑛⋅(𝑛+1)/2

To print the result modulo ​ 10⁹+7, you would do the following:

1. Compute the sum 𝑆.
2. Compute S mod (10⁹+7).

When you see the formula:

(𝑎⋅𝑏)%𝑚=((𝑎%𝑚)⋅(𝑏%𝑚))%𝑚

This property helps prevent overflow during multiplication by ensuring that the intermediate results are kept within bounds. Here is an example:

Suppose 𝑎=1000000008 and 𝑏=1000000009, and 𝑚=1000000007.

Conclusion

In summary, “print it modulo 10⁹+7” is a common requirement in competitive programming to handle large numbers, prevent overflow, and take advantage of the properties of prime numbers in modular arithmetic. Always remember to apply the modulo operation at each step of your calculation to keep intermediate results manageable.

Note

Above content is compilation from various sources like chatgpt, qoura. I have comiple it for my personal reference.