3.3 KiB
Calculating {n \choose r} \% m
like a pro
Let's begin with some prerequisites.
Modular arithmetic
(a \bmod m)
, also represented as a \% m =
remainder left when a
is divided by m
.
Example: 10 \% 7 = 3
Properties of \%
Distritbutive over addition & substraction (\pm)
(a\pm b) \% m = \Bigl[ (a \% m ) \pm (b \% m) \Bigr] \% m
(8+13)\%7 = \Bigl[(8 \% 7) + (13 \% 7)\Bigr]\%7
21\%7 = [1 + 6]\%7
0 = 7 \% 7
0 = 0
Distritbutive over multiplication (\times)
(a \times b) \% m = \Bigl[ (a \% m ) \times (b \% m) \Bigr] \% m
(8 \times 13)\%7 = \Bigl[(8 \% 7) \times (13 \% 7)\Bigr]\%7
104 \% 7 = [1 \times 6]\%7
6 = 6 \% 7
6 = 6
- NOT distributive over $\div$
Unlike
+, -, \times
, the modulo operator does not distribute over division. So,\left (\dfrac ab \right )\%m \;\;\red \neq\;\; \left[\dfrac{a\%m}{b\%m}\right] \% m
. However, the concept of Modular Inverse (discussed later) helps us simplify these calculations.
Calculating (n! \bmod m)
in \mathcal O(n)
time
Since \%
distributes over \times
, we can say that
$$(n!) % m = \Bigl[n (n-1)(n-2) \cdots 1\Bigr] % m \[.5em] =\overbrace{\underbrace{{\underbrace{\overbrace{n \cdot (n-1)}^{%m} \cdot (n-2)}{%m} \cdots} \cdot 2}{% m} \cdot 1}^{%m}$$
So, we can simply calculate factorial, by taking \%
after every multiplication.
def fact_mod(n, mod):
ans = 1
for i in [1 .. n]
ans = (ans * i) % mod
return ans
Binary Exponentiation: calculating (n^p \bmod m)
in \mathcal O(\log_2 p)
time
def binary_exponentiation(n, p, mod):
if n == 0: return 0
if p == 0: return 1
ans = binary_exponentiation(n, p//2, mod) # note: integer division
ans = ans * ans
if p is even:
return ans
else:
return ans * n
Fermat's Little Theorem
If p
is prime, then
a^p \equiv a \pmod p
Euler's generalization to Fermat's Little theorem
Iff a
and m
are co-prime, then
\boxed{a^{\phi(m)} \equiv 1 \pmod m}
Let's break it down:
a
is coprime withm
iffgcd(a, m) = 1
, that is,a
andm
do not have any common factor.- If
a \bmod m = b \bmod m
, we say thata \equiv b \pmod m
\phi(m)
is the Euler's Totient Function form
Euler's Totient Function \phi(m)
The Euler's Totient Function \phi(m)
counts the number whole numbers smaller than m
which are coprime with m
For example, if m = 30
, then what numbers are coprime with m
?
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
-----------------------------
1 7
11 13 17 19
23 29
-----------------------------
count = 8
- If
m
is prime,\boxed{\phi(m) = m - 1}
- If
m
is not prime, then let us factorizem
Letm = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot p_3^{\alpha_3} \ldots
Then,\boxed{\phi(m) = m \left (1 - \dfrac1 p_1 \right )\left (1 - \dfrac1 p_2 \right )\left (1 - \dfrac1 p_3 \right ) \cdots}
Example,
- if
m = 17
,\phi(17) = 16
- if
m = 30 = 2^1 \cdot 3^1 \cdot 5^1
, then\phi(30) = 30 \left( 1 - \dfrac 1 2 \right )\left( 1 - \dfrac 1 3 \right )\left( 1 - \dfrac 1 5 \right )
= 30 \cdot \dfrac12 \cdot \dfrac23 \cdot \dfrac45 = 8