Problem assets/proof/theorems/numbertheory/crt.tex

\begin{redbox}{Dowód tw. \ref{tw:crt}}
    \begin{proof}
        Rozważmy układ równań:
        \[
        \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}
        \]
        Ponieważ \( m_1, m_2, \ldots, m_k \) są parami względnie pierwsze, to z Chińskiego Twierdzenia o Resztach wynika, że istnieje jedno rozwiązanie \( x \), które jest rozwiązaniem układu modularnego.
        
        Aby znaleźć to rozwiązanie, zastosujmy konstrukcję opartą na odwrotnościach modularnych.
        
        Niech \( M = m_1 m_2 \cdots m_k \). Definiujemy \( M_i = \frac{M}{m_i} \) dla każdego \( i = 1, 2, \ldots, k \). Wtedy \( M_i \) jest liczbą, która jest podzielna przez wszystkie \( m_j \) oprócz \( m_i \), czyli \( \gcd(M_i, m_i) = 1 \).
        
        Dla każdego \( i \) możemy znaleźć liczbę \( y_i \) taką, że:
        \[
        M_i y_i \equiv 1 \pmod{m_i}
        \]
        jest to **odwrotność modularna** \( M_i \) modulo \( m_i \).
        
        Zatem rozwiązanie \( x \) układu równań możemy zapisać w postaci:
        \[
        x = \sum_{i=1}^k a_i M_i y_i
        \]
        gdzie każda składnik \( a_i M_i y_i \) jest rozwiązaniem \( x \equiv a_i \pmod{m_i} \).
        
        Ponieważ \( M_i \) jest podzielne przez wszystkie \( m_j \) oprócz \( m_i \), każdy z tych składników spełnia odpowiednią kongruencję. W ten sposób \( x \) jest rozwiązaniem układu.
        
        Na koniec, ponieważ wszystkie \( m_i \) są parami względnie pierwsze, każde dwa rozwiązania \( x_1 \) i \( x_2 \) układu równań będą kongruentne modulo \( M = m_1 m_2 \cdots m_k \).
        
        Zatem rozwiązanie jest jedyne modulo \( M \), co kończy dowód.
    \end{proof}
\end{redbox}