1. Overview
When working with large numbers, intermediate results can exceed data type limits. For such scenarios, modular arithmetic helps keep numbers manageable and prevent overflow errors.
In this tutorial, we’ll learn how to perform modulo-arithmetic operations with 10^9 + 7 as an example format for the modulus.
2. Basics
In this section, let’s brush up on a few important concepts to help us perform modular arithmetic operations efficiently.
2.1. Symmetric Modulo and Non-negative Remainder
Let’s imagine that we want to compute a mod b. By applying the division algorithm, we can get the positive remainder (r):
a = q.b + r
where, b>0 and r≧0
We must note that we’ll assume that modulus (b) is a positive number for the scope of this article.
Subsequently, we can rewrite the equation to get a negative remainder:
a = (q+1)b - (b - r)
where, -(b-r)≦0
From a purely mathematical point of view, this is called symmetric modulo, where the remainder lies in the range [-b, b). However, most programming implementations prefer the non-negative remainder in the range [0, b) when returning the result of the modulo operation for a positive modulus.
2.2. Congruence Property
Now, let’s see another interesting property in modular arithmetic that deals with congruence relation (≡):
(a mod n) = (b mod n) <=> a≡b (mod n)
Essentially, two numbers, a and b, are congruent modulo n, if they give the same remainder when divided by n. As a result, we can say that 10 ≡ 4 (mod 3).
2.3. Strategy for Modular Arithmetic
Using the symmetric modulo and congruence properties, we can formulate a strategy for modular arithmetic operations by choosing a smaller intermediate result amongst two numbers whenever feasible.
For this purpose, let’s define the minSymmetricMod() method that returns the remainder that has a lower absolute value:
static int minSymmetricMod(int x) {
if (Math.abs(x % MOD) <= Math.abs((MOD - x) % MOD)) {
return x % MOD;
} else {
return -1 * ((MOD - x) % MOD);
}
}
As part of our strategy, we’ll use minSymmetricMod() to compute all the intermediate results.
Further, let’s define the mod() method that’s guaranteed to give a positive remainder value:
static int mod(int x) {
if (x >= 0) {
return x % MOD;
} else {
return mod(MOD + x);
}
}
We can use method overloading to support long values.
For our use cases, we’re using MOD = 10^9 + 7. However, unless stated otherwise, the general principle holds true for any other modulus value.
We’ll apply these concepts to addition, subtraction, multiplication, and other modular arithmetic operations.
3. Modular Sum
In this section, we’ll learn to do the modulo sum operation efficiently.
3.1. Distributive Property
The modulo operation follows distributive property over addition:
(a + b) mod n = ((a mod n) + (b mod n)) mod n
Further, we can use the symmetric_mod for all the intermediate modulo operators:
(a + b) mod n = ((a symmetric_mod n) + (b symmetric_mod n)) mod n
The outermost mod operation guarantees a positive remainder. In contrast, the inner symmetric_mod operations reduce the magnitude of the numbers by appropriately choosing the lower of the positive or negative remainders.
3.2. Computation
We can write the modAdd() method to compute the modulo sum of two numbers:
static int modSum(int a, int b) {
return mod(minSymmetricMod(a) + minSymmetricMod(b));
}
Now, let’s validate our approach by computing modulo sum for a few pairs of numbers:
assertEquals(1000000006, modSum(500000003, 500000003));
assertEquals(1, modSum(1000000006, 2));
assertEquals(999999999, modSum(999999999, 0));
assertEquals(1000000005, modSum(1000000006, 1000000006));
Perfect! We’ve got the right results.
4. Modular Subtraction
Now that we’ve discussed modulo addition operation, we can extend our approach to modulo subtraction in this section.
4.1. Distributive Property
Let’s start by looking at the distributive property of modulo operation over subtraction:
(a - b) mod n = ((a mod n) - (b mod n)) mod n
Further, let’s apply our strategy of using the symmetric_mod operation for the intermediate results:
(a - b) mod n = ((a symmetric_mod n) - (b symmetric_mod n)) mod n
That’s it. We’re now ready to implement this approach for computing modulo subtraction.
4.2. Computation
Let’s write the modSubtract() method to compute the modulo subtraction of two numbers:
static int modSubtract(int a, int b) {
return mod(minSymmetricMod(a) - minSymmetricMod(b));
}
Under the hood, minSymmetricMod() ensures that the magnitude of intermediate terms is kept as small as possible.
Next, we must test our implementation against different sets of numbers:
assertEquals(0, modSubtract(500000003, 500000003));
assertEquals(1000000005, modSubtract(1, 3));
assertEquals(999999999, modSubtract(999999999, 0));
Great! The result looks correct.
5. Modular Multiplication
In this section, let’s learn how to compute the modular multiplication of two numbers.
5.1. Distributive Property
Like addition, the modulo operation is also distributive over multiplication:
(a * b) mod n = ((a mod n) * (b mod n)) mod n
As a result, we can use the symmetric_mod operation for intermediate terms:
(a * b) mod n = ((a symmetric_mod n) * (b symmetric_mod n)) mod n
For all intermediate results, we’ll choose the remainder with a lower absolute value. Eventually, we’ll apply the mod operation to get a positive remainder.
5.2. Computation
Let’s write the modMultiply() method to compute the modulo multiplication of two numbers:
static long modMultiply(int a, int b) {
int result = minSymmetricMod((long) minSymmetricMod(a) * (long) minSymmetricMod(b));
return mod(result);
}
Although the upper bound on the return value of minSymmetricMod() is MOD – 1, the resulting value after multiplication could overflow the limit of the Integer data type. So, we must use a (long) type casting for multiplication.
Further, let’s test our implementation against a few pairs of numbers:
assertEquals(1, modMultiply(1000000006, 1000000006));
assertEquals(0, modMultiply(999999999, 0));
assertEquals(1000000006, modMultiply(500000003, 2));
assertEquals(250000002, modMultiply(500000003, 500000003));
Excellent! It looks like we nailed this one.
6. Modular Exponential
In this section, we’ll extend our approach of modulo multiplication computation to calculate modulo power.
6.1. Modular Exponential Property
Since modulo is distributive over multiplication, we can simplify the modular exponentiation:
(a ^ b) mod n = ((a mod n) ^ b) mod n
We must note that modulo isn’t distributive over the power operation as we didn’t take modulo for the exponent, b.
Like earlier, we can replace the mod for intermediate terms with the symmetric_mod operation:
(a ^ b) mod n = ((a symmetric_mod n) ^ b) mod n
We’ll use this property for computation purposes.
6.2. Computation
Let’s go ahead and write the modPower() method that takes two parameters, namely, base and exp:
static int modPower(int base, int exp) {
int result = 1;
int b = base;
while (exp > 0) {
if ((exp & 1) == 1) {
result = minSymmetricMod((long) minSymmetricMod(result) * (long) minSymmetricMod(b));
}
b = minSymmetricMod((long) minSymmetricMod(b) * (long) minSymmetricMod(b));
exp >>= 1;
}
return mod(result);
}
We used the fast power approach to calculate the exponential value while using minSymmetricMod() for intermediate modulo values. Additionally, we did a (long) typecast to hold the multiplication result, which could be larger than the Integer.MAX_VALUE value.
Now, let’s see our implementation in action by verifying it for different pairs of numbers:
assertEquals(16, modPower(2, 4));
assertEquals(1, modPower(2, 0));
assertEquals(1000000006, modPower(1000000006, 1));
assertEquals(1000000006, modPower(500000003, 500000003));
assertEquals(500000004, modPower(500000004, 500000004));
assertEquals(250000004, modPower(500000005, 500000005));
Fantastic! Our approach is highly performant and gives correct results.
7. Modular Multiplicative Inverse
The modulo multiplicative inverse of a mod m exists if and only if a and m are co-prime. For our scenario, m=10^9 + 7 is a prime number, which is co-prime with all other numbers, so let’s learn how to find the modular multiplication inverse.
7.1. Bézout’s Identity
According to Bézout’s Identity, we can express gcd(a, b) using two coefficients, x and y:
gcd(a, b) = x*a + y*b
Interestingly, when a and b are co-primes, we can replace gcd(a, b) with 1:
x*a + y*b = 1
Now, let’s apply the mod b operation on both sides of the equation:
(x*a + y*b) % b = 1 % b
=> (x*a) % b = 1
We’ve arrived at the definition of modular multiplicative inverse that states (a-1 * a) % b = 1.
The problem of finding the modular multiplicative inverse boils down to finding Bézout’s coefficient (x). Therefore, we can use the extended Euclidean algorithm to solve our use case.
7.2. Computation With Extended Euclidean Algorithm
Let’s write the extendedGcd() method that returns the greatest common divisor and Bézout’s coefficients:
static int[] extendedGcd(int a, int b) {
if (b == 0) {
return new int[] { a, 1, 0 };
}
int[] result = extendedGcd(b, a % b);
int gcd = result[0];
int x = result[2];
int y = result[1] - (a / b) * result[2];
return new int[] { gcd, x, y };
}
As a result, we can now find the modular multiplicative inverse using the extendedGCD() and mod() methods:
static int modInverse(int a) {
int[] result = extendedGcd(a, MOD);
int x = result[1];
return mod(x);
}
Lastly, we must test our implementation for a few numbers:
assertEquals(500000004, modInverse(2));
assertEquals(1, modInverse(1));
assertEquals(1000000006, modInverse(1000000006));
assertEquals(1000000005, modInverse(500000003));
The result looks correct.
8. Modular Division
Modular multiplication and modular inverse are prerequisites to understanding the modular division operation. Further, we can perform modular division only when modular inverse exists.
For two co-prime numbers, a and b, let’s write the modDivide() method to compute modular division:
static int modDivide(int a, int b) {
return mod(modMultiply(a, modInverse(b)));
}
If we notice clearly, it’s equivalent to the modular multiplication of a and the modular inverse of b.
Now, let’s see modular division in action for some of the sample numbers:
assertEquals(500000004, modDivide(1, 2));
assertEquals(2, modDivide(4, 2));
assertEquals(1000000006, modDivide(1000000006, 1));
It looks like we’ve got this one right.
9. Conclusion
In this article, we learned about the modular arithmetic operations for sum, multiplication, subtraction, power, inverse, and division. Further, we learned that modular multiplicative inverse and division operations are only possible for co-prime numbers.
As always, the code from this article is available over on GitHub.