# 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

$(a + b) \%m = (a \%m + b \%m) \% m \\ (a - b) \%m = (a \%m - b \%m + m) \% m \\ (a . b) \%m = (a \%m . b \%m) \% m \\$

## Modular Multiplicative Inverse

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

$ax \equiv 1 (\bmod \space m)$
• 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.

$x = a^{(m - 2)} \bmod m$

## 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;
}