Modular Arithmetic

$x$ mod $m$ is the remainder of $x$ when $x$ is divided by $m$. It is also represented by the sign $\%$. For example, 19 % 4 is 3, since 19 = 4 * 4 + 3.

In many problems, modulo is used since if the answer is very large, modulo m (for example, $m = 10^9 + 7$) will keep the answer $< m$ thus fitting it within the primitive data type.

Properties of Modular Arithmetic

Modular Multiplicative Inverse

The modular multiplicative inverse of an integer $x$ such that,

• The value of $x$ should be in the range $[1, m - 1]$
• The multiplicative inverse only exists if a and m are relatively prime

Example

• $a = 7$, $m = 9$. Since $(7 * \underline{4}) \% 9 = 1$, 4 is the modulo inverse of 7 under 9.
• $a = 5$, $m = 8$. Since $(5 * \underline{5}) \% 8 = 1$, 5 is the modulo inverse of 5 under 8.

Calculation of Modular Multiplicative Inverse

If $m$ is prime, we can use Fermat’s little theorem to calculate the modulo inverse.

Implementation: Factorial of a Large Number

int factorial(int n, int m) {
    long long ans = 1;

    for (int i = 2; i <= n; ++i) {
        ans = (ans * (long long) i) % m;
    }
    
    return ans % m;
}