Układ kongruencji

[piotrb]

Witam, proszę o pomoc w rozwiązaniu układu kongruencji:
\begin{cases}2x ≡ 1 \pmod{ 7}\\
3x ≡ 99 \pmod{ 192}\\
x ≡ 25 \pmod{ 98}\end{cases}

[Premislav]

Pierwszą kongruencję, czyli \(\displaystyle{ 2x\equiv 1\pmod{7}}\), mnożymy stronami przez odwrotność \(\displaystyle{ 2}\) modulo \(\displaystyle{ 7}\), czyli \(\displaystyle{ 4}\) (wszak \(\displaystyle{ 4\cdot 2\equiv 1\pmod{7}}\)), otrzymując \(\displaystyle{ x\equiv 4\pmod{7}}\).
Druga kongruencja w tym układzie, czyli \(\displaystyle{ 3x\equiv 99\pmod{192}}\) oznacza, że istnieje takie \(\displaystyle{ k\in \ZZ}\), iż
\(\displaystyle{ 3x=192k+99}\), a to po podzieleniu stronami przez \(\displaystyle{ 3}\) daje nam \(\displaystyle{ x=64k+33}\), tj. \(\displaystyle{ x\equiv 33\pmod{64}}\).
Zatem układ kongruencji z zadania można przepisać w formie:
\(\displaystyle{ \begin{cases}x\equiv 4\pmod{7}\\ x\equiv 33\pmod{64}\\x\equiv 25\pmod{98}\end{cases}}\)
Ostatnia z tych kongruencji oznacza istnienie takiego \(\displaystyle{ l\in \ZZ}\), że
\(\displaystyle{ x=98l+25=7(14l+3)+4}\), a więc \(\displaystyle{ x\equiv 4\pmod{7}}\), czyli pierwszą kongruencję można wyrzucić, ponieważ nie daje nam dodatkowej informacji. Pozostaje:
\(\displaystyle{ \begin{cases}x\equiv 33\pmod{64}\\x\equiv 25\pmod{98}\end{cases}}\), czyli
\(\displaystyle{ x}\) jest liczbą nieparzystą (co zapewnia nam już pierwsza kongruencja) i \(\displaystyle{ x=49\cdot (2l)+25}\), a stąd otrzymujemy
\(\displaystyle{ \begin{cases}x\equiv 33\pmod{64}\\x\equiv 25\pmod{49}\end{cases}}\)
Sprowadziliśmy to do takiej postaci, gdyż \(\displaystyle{ \NWD(64, 49)=1}\). Teraz możemy skorzystać z wzoru generującego rozwiązanie takiego (a nawet ogólniejszego) układu, patrz

Kod: Zaznacz cały

https://en.wikipedia.org/wiki/Chinese_remainder_theorem

.
Znajdujemy takie \(\displaystyle{ s,t\in \ZZ}\), że \(\displaystyle{ 49s+64t=1}\), korzystając z rozszerzonego algorytmu Euklidesa:
\(\displaystyle{ 64=1\cdot 49+15\\49=3\cdot 15+4\\15=3\cdot 4+3\\4=1\cdot 3+1\\1=4-1\cdot 3=(49-3\cdot 15)-1\cdot (15-3\cdot 4)\\=49-4\cdot 15+3\cdot (49-3\cdot 15)=4\cdot 49-13\cdot 15=4\cdot 49-13\cdot (64-49)=17\cdot 49-13\cdot 64}\)
czyli \(\displaystyle{ s=17, \ t=-13}\).
Wtedy zgodnie z linkiem rozwiązanie (jedyne z dokładnością do wielokrotności \(\displaystyle{ 49\cdot 64}\)) jest postaci
\(\displaystyle{ 33\cdot 17\cdot 49+25\cdot (-13)\cdot 64=6689 }\), a \(\displaystyle{ 6689\equiv 417\pmod{49\cdot 64}}\), tj. ostatecznie
\(\displaystyle{ x\equiv 417\pmod{49\cdot 64}}\).

[piotrb]

Dziękuję bardzo za pomoc.
Mam jeszcze jeden problem, nie jestem do końca pewien czy mogę przykładowo taki układ kongruencji:
\begin{cases}
x ≡ 1\pmod{ 12} \\
x ≡ 7\pmod{ 18} \\
x ≡ 13\pmod{ 42} \\
\end{cases}
rozpisać do takiej postaci:
\begin{cases}
x ≡ 1\pmod{ 3} \\
x ≡ 1\pmod{ 4} \\
----- \\
x ≡ 1\pmod{ 2} \\
x ≡ 7\pmod{ 9} \\
----- \\
x ≡ 1\pmod{ 6} \\
x ≡ 6\pmod{ 7} \\
\end{cases}
i następnie zredukować do takiej postaci:
\begin{cases}
x ≡ 1\pmod{ 4} \\
x ≡ 7\pmod{ 9} \\
x ≡ 6\pmod{ 7}
\end{cases}

[Premislav]

Tak, jak najbardziej.