Modular Basics + Number Theory + Permutations

$Binary Exponentiation - to find a^{b} \to converted b into binary$

Benefit - instead of multiplying b times => multiply log2(b) times
If a is large → take (a % M)
If M is itself very large (like 1e18) => instead of a*a → DO a+a+a....(a times)

even if a*a = 1e18 → will not get reduced
log²(n) bcz log(n) for binary_Multiply & log(n) for expo

Same code as expo => Only change * to + everywhere

If b is large in ab

→ abc ≠ a(bc % M) (modM) → cannot take mod in power

Use Euler Theorem → abc
≡a(bc % ɸ(m)) (modM) → ɸ is euler totient function

For safety, add extra ɸ in power bcz above fails if gcd(a, m) ≠ 1
abc
≡a(ɸ(m) + (bc % ɸ(m)))(modM) → updated

GCD + prime properties

a divides b + b divides a ---> a = ± b
gcd is always +ve --> bcz let's say -d is gcd
=> d is also gcd and since gcd is greatest divisor --> gcd = d
To make (a,b) co-prime --> divide both by their gcd
a divides c + b divides c + gcd(a,b)=1 --> a*b divides c
a divides b*c + gcd(a,b)=1 --> a divides c
gcd(a,bc)=1 ⇔ gcd(a,b)=1 and gcd(a,c)=1
For gcd problems, take gcd to be d --> and then think
gcd(0,x)= x lcm(a,b)= 0 (if any of a or b = 0}

Modular properties

a≡ b (mod n) + c≡ d (mod n) --> a+c≡ b+d or ac≡ bd (mod n)

Converse NOT true -> 4+2≡ 5+1 (mod 6) or 3*2≡ 6*1 (mod 6)

ca≡ cb (mod n) --> a≡ b (mod n/d) where d = gcd(n,c)

Similar to GCD point 3

If gcd(a,n)= d then ax≡ b (mod n) has d solutions if d divides b

ax - ny = b <=> ax ≡ b (mod n) bcz n divides (ax-b)
If gcd(a,n)=1 => x ≡ a⁻¹b(mod n) to get unique x [use GCD point 3]

Fermat's theorem - p is prime + gcd(p,a)= 1 --> a p−1≡ 1(mod p)
p is prime + a is any number --> a p ≡ a(mod p)
Wilson's theorem - If p is prime --> (p-1)! ≡ -1(mod p)
Modular inverse - ax ≡ 1(mod m) + gcd(a,m)=1
=> unique solution exists(from 3)and x is the modular inverse

a*(a p−2) ≡ 1(mod p) [from fermat's theorem] --> a p−2 is inverse

a≡ b (mod n) + m is divisor of n --> a≡ b (mod m)

Divisor Results

N = p_{1}^{a_{1}} \cdot p_{2}^{a_{2}} \cdot p_{3}^{a_{3}} \dots p_{k}^{a_{k}}

where

p_{1}, p_{2}, \dots, p_{k}

are distinct prime numbers
τ(N)=(a1+1)(a2+1)(a3+1)⋯(ak+1) ---> number of divisors

σ(N)=(p1−1p1a1+1−1)(p2−1p2a2+1−1)(p3−1p3a3+1−1)⋯(pk−1pkak+1−1) --> sum of all divisors

Idea - (a1+1) choices for divisor in τ(N) + all choices are independent of others

$σ (N) = (1 + p_{1} + p_{1}^{2} + \dots + p_{1}^{a_{1}}) (1 + p_{2} + p_{2}^{2} + \dots + p_{2}^{a_{2}}) \dots (1 + p_{k} + p_{k}^{2} + \dots + p_{k}^{a_{k}})$

Chinese Remainder theorem

for pairwise coprime integers m₁, m₂,...,mₖ and corresponding remainders a₁, a₂,...,aₖ, there exists a unique solution modulo M = m₁×m₂×...×mₖ to the system:

{\begin{cases} x \equiv a_{1} (m o d m_{1}) \\ x \equiv a_{2} (m o d m_{2}) \\ ⋮ \\ x \equiv a_{k} (m o d m_{k}) \end{cases}

above system of equations corresponds to "x≡a
(mod M
)"

Euler Totient function

ɸ(n) is number of integers not more than n and relatively prime to n

ɸ(p) = p-1 [when p is prime] bcz all 1 to p-1 are co-prime with p
ɸ(pk)=pk−pk−1 [when p is prime] bcz total value = pkvalues divisible by p are {p, 2p, ...., pk−1* p} --> total = pk−1 (subtract it)

ɸ(n) is always even for n > 2
ɸ(n) is multiplicative function => ɸ(m*n) = ɸ(m) * ɸ(n) {if gcd(m, n) = 1}
$N = p_{1}^{a_{1}} \cdot p_{2}^{a_{2}} \cdot p_{3}^{a_{3}} \dots p_{k}^{a_{k}}$ where $p_{1}, p_{2}, \dots, p_{k}$ are distinct prime numbers

ɸ(n) = ( $p_{1}^{a_{1}} - p_{1}^{a_{1-1}})*(p_{2}^{a_{2}} - p_{2}^{a_{2-1}})* \dots*(p_{k}^{a_{k}}$ - pkak-1 )

Euler's Theorem - aϕ(n)≡1 (modn) if gcd(a, n) = 1

Permutation and Combinations

Problem Type - Find number of integer solutions to equation $x_1 + x_2 + \ldots + x_k = n$ ( $x_i \ge 0$ $x_i \ge 0$ $x_i \ge 0$ ) → ways to arrange n identical items into k distinct bin → C(n+k-1, k-1)

need (k-1) bars → same as choosing (k-1) positions out of {n + (k-1)} positions
C(n + 1, k - 1)❌ bcz ignores case where two or more bars are next to each other
NOTE - If ( $x_i \ge 0$ $x_i \ge 0$ $x_i \ge 0$ ) → subtract 1 from each to convert into ( $x_i \ge 0$ $x_i \ge 0$ $x_i \ge 0$ ) → C(n - 1, k-1)

Problem Type - Find number of integer solutions to equation $x_1 + x_2 + \ldots + x_k = n$ ( $x_i \ge 0$ $x_i \ge 0$ $x_i \ge 0$ ) → ways to arrange n identical items into k+1 distinct bin → C(n+k, k)

bcz add one extra slack bin to create equality (like Optimisation Techniques)

Search This Blog

CPP notes