Freaks City

Number Theory 1.1 Chinese Remainder Theorem Problem Statement Given a system of congruences: \[ \begin{cases} x \equiv a_1 \pmod{b_1} \\ x \equiv a_2 \pmod{b_2} \\ \vdots \\ x \equiv a_n \pmod{b_n} \end{cases} \] Find the smallest positive integer solution for \(x\), where \(b_i\) (for \(i \in [1,n]\)) are pairwise coprime. Theoretical Analy ...

Lucas Theorem Mathematical Statement Given prime $p$, the following congruence holds: $$\binom{n}{m} \equiv \binom{\lfloor n/p \rfloor}{\lfloor m/p \rfloor} \cdot \binom{n \bmod p}{m \bmod p} \pmod{p}$$ Proof Foundation Lemma 1 For prime $p$: $$\binom{p}{k} \equiv 0 \pmod{p} \text{ when } 0 < k < p$$ The numerator contains factor $p$, mak ...