Równania mod, układ kongruencji

[Scoler]

Przygotowań do egzaminu poprawkowe ciąg dalszy.

Mam takie zadanie, ale nie wiem jak się takie coś robi. Wiem, że prawdopodobnie trzeba policzyć NWD dla każdego równania i później wyznaczyć element odwrotny. Bardzo proszę o pomoc.

Z równań
\(\displaystyle{ a)\ 7x=4\pmod{30};\\ b)\ 3x=6\pmod{10};\\ c)\ 5x=7\pmod{15};\\ d)\ x=22\pmod{150};\\ e)\ 14x=8 \pmod{60}}\)
wybierz równanie równoważne z układem kongruencji (w sensie rozwiązania):

\(\displaystyle{ \begin{cases} x=2\pmod{10}\\x=7\pmod{15}\end{cases}}\)

[Premislav]

Ja bym rozłożył układ kongruencji:
\(\displaystyle{ \begin{cases} x=2\pmod{10}\\x=7\pmod{15}\end{cases}}\)
na taki:
\(\displaystyle{ \begin{cases}x\equiv 0\pmod{2}\\ x\equiv 2\pmod{3} \\ x\equiv 2\pmod{5}\\ \end{cases}}\)
i dalej z chińskiego,
Można też bardziej „chałupniczo":
z warunku \(\displaystyle{ x\equiv 2\pmod{10}}\) wiemy, że \(\displaystyle{ x\pmod{30}\in \left\{ 2,12,22\right\}}\), zaś dzięki warunkowi \(\displaystyle{ x\equiv 7\pmod{15}}\) mamy, że \(\displaystyle{ x\pmod{30}\in \left\{7, 22 \right\}}\), a więc łącząc te dwa fakty dostajemy \(\displaystyle{ x\equiv 22\pmod{30}}\).
Z drugiej strony jeśli \(\displaystyle{ x\equiv 22\pmod{30}}\), to oczywiście zarówno \(\displaystyle{ x\equiv 2\pmod{10}}\), jak i \(\displaystyle{ \equiv 7\pmod{15}}\).

Teraz wystarczy uporządkować te kongruencje z podpunktów, np. pozbywając się współczynników tam, gdzie są one odwracalne przez pomnożenie stronami przez element odwrotny, a tam gdzie współczynnik nie jest odwracalny, dzieląc przez \(\displaystyle{ \NWD}\), np.
\(\displaystyle{ 14x\equiv 8\pmod{60} \Leftrightarrow 7x\equiv 4\pmod{30}}\)
bo ta informacja oznacza, że istnieje taka liczba całkowita \(\displaystyle{ k}\), iż \(\displaystyle{ 14x=60k+8}\).
W istocie więc po prostych obliczeniach uzyskujemy, że pasują podpunkty a) i e).
Można też łatwo odrzucić niektóre podpunkty z automatu, np. c) jest sprzeczny (patrz podzielność przez \(\displaystyle{ 5}\)), a podany układ kongruencji nie jest sprzeczny, d) niesie więcej informacji, niż jesteśmy w stanie uzyskać, bo z \(\displaystyle{ x\equiv 22\pmod{30}}\) nie wynika, że \(\displaystyle{ x\equiv 22\pmod{150}}\).

[Scoler]

Powoli xd. Jestem na poziomie mułu jeśli chodzi o rozumienie tego.
Najpierw może jak w ogóle rozwiązać takie równanie modularne np. równanie a)

\(\displaystyle{ 7x=4\pmod{30}}\)

Najpierw muszę pomnożyć równanie przez \(\displaystyle{ 7^{-1}\pmod{30}}\)?
Czyli muszę znaleźć taką liczbę, która pomnożona przez \(\displaystyle{ 7}\) daję \(\displaystyle{ 1}\) w \(\displaystyle{ \pmod{30}}\)?

[Premislav]

Najpierw może jak w ogóle rozwiązać takie równanie modularne np. równanie a)

\(\displaystyle{ 7x=4\pmod{30}}\)

Najpierw muszę pomnożyć równanie przez \(\displaystyle{ 7^{-1}\pmod{30}}\)?
Czyli muszę znaleźć taką liczbę, która pomnożona przez \(\displaystyle{ 7}\) daję \(\displaystyle{ 1}\) w \(\displaystyle{ \pmod{30}}\)?

Zgadza się. Taką liczbę znajduje się zazwyczaj albo zgadując, albo stosując rozszerzony algorytm Euklidesa: ... _Euklidesa. Znajdziemy więc tak \(\displaystyle{ 7^{-1}\pmod{30}}\):
\(\displaystyle{ 30=4\cdot 7+2\\7=3\cdot 2+1\\ 1=7-3\cdot 2=7-3\cdot (30-4\cdot 7)=\\=13\cdot 7-3\cdot 30}\), czyli
\(\displaystyle{ 13\cdot 7=3\cdot 30+1}\), a więc \(\displaystyle{ 13\cdot 7\equiv 1\pmod{30}}\), czyli \(\displaystyle{ 7^{-1}\pmod{30}=13}\).

[Scoler]

Kumam i co dalej? Bo to dla mnie dość czarna magia.
Mnożę obustronnie przez 13?

[Janusz Tracz]

Tak. Dowiedziałeś się że \(\displaystyle{ 13}\) jest odwrotne do \(\displaystyle{ 7}\) w modulo \(\displaystyle{ 30}\) więc pomnożenie kongruencji \(\displaystyle{ 7x\equiv 4\bmod 30}\) stronami przez \(\displaystyle{ 13}\) sprowadza problem do \(\displaystyle{ x\equiv 13\cdot4\bmod 30}\) a dalej \(\displaystyle{ x\equiv 22 \bmod 30}\) a to (właściwie z definicji) oznacza że \(\displaystyle{ x-22}\) dzieli się przez \(\displaystyle{ 30}\) czyli że \(\displaystyle{ x=30k+22}\) gdzie \(\displaystyle{ k\in\ZZ}\) co jest rozwiązaniem kongruencji.