Problem assets/theorems/numbertheory/crt.tex

\begin{bluebox}{Chińskie Twierdzenie o Resztach}
    \begin{theorem}[Chińskie Twierdzenie o Resztach]
        \label{tw:crt}
        Niech \( m_1, m_2, \ldots, m_k \) będą liczbami całkowitymi większymi niż 1, takimi że są parami względnie pierwsze, tzn.:
        \[
        \gcd(m_i, m_j) = 1 \quad \text{dla } i \neq j.
        \]
        Dla dowolnych liczb całkowitych \( a_1, a_2, \ldots, a_k \) układ równań kongruencyjnych:
        \[
        \begin{cases}
        x \equiv a_1 \pmod{m_1} \\
        x \equiv a_2 \pmod{m_2} \\
        \quad\vdots \\
        x \equiv a_k \pmod{m_k}
        \end{cases}
        \]
        ma dokładnie jedno rozwiązanie modulo \( M = m_1 m_2 \cdots m_k \).
        
        Innymi słowy, istnieje liczba całkowita \( x \) taka, że spełnia wszystkie powyższe kongruencje, a każde dwa takie rozwiązania są kongruentne modulo \( M \).
    \end{theorem}
\end{bluebox}