C++’ers IRL
We know what a remainder is: it is the value produced after two integers are divided. For instance, we get $2$ as the remainder when $17$ is divided by $5$, or $0$ when $369$ is divided by $123$.
There was the modulo operator %, particularly for finding the remainder, ignoring the division result. For the examples above, $17 \ \% \ 5 = 2$ and $369 \ \% \ 123 = 0$.
To deal with large integers, we use this operator to compute the answer modulo some integer $m$, where $m$ is called the modulus. We don’t refer to $m$ alone, instead, we often use the expression “modulo $m$”. This is why the term modulus isn’t used so much.
What does “$x$ modulo $m$” even mean?
It is how we refer to the remainder itself since the remainder is the result of this modulo operation. It means the same as “remainder of $x$ divided by $m$”, “remainder when $x$ is divided by $m$”…
But wait, what if $m$ is so small that even if our calculations are wrong, we get the same remainder as the true answer’s remainder? For instance, $13$ and $18$ produce the same remainder modulo $5$, but we should’ve computed $13$ instead of $18$.
Yes, that’s so right. This is why $m$ is never that small. 😏
To decrease the probability of that happening, a large prime is chosen for $m$ such as $10^9 + 7$, $998244353$, etc.
Of course, there are so many other primes, but these two numbers have some special properties on their own, which even I don’t completely know about.
FYI, we almost always use $10^9 + 7$.
Well, so far so good. But our calculations will consist of many steps that lead to the final result, therefore many intermediate values. We can’t just find the final answer in one step, and then find the remainder. But, we should somehow always deal with small integers, as this is our actual purpose.
Then, how do we safely focus on finding the remainder?
For instance, calculating $5!$ requires several steps: