Układ kongruencji

[JustynaB.]

Witam. Bardzo chciałabym prosić o pomoc w rozwiązaniu jednego układu. Nie chodzi mi tutaj o rozwiązanie krok po kroku, lecz raczej o pewne wskazówki, zasady, schematy rozwiązywania takiego zadania.
Może przedstawię tutaj etap do którego doszłam podczas rozwiązywania takiego układu:

\(\displaystyle{ \left\{\begin{array}{l} x\equiv 7(mod 12)\\x\equiv 10(mod 15)\\x\equiv 8(mod 14) \end{array}}\)

Najpierw sprowadziłam układ do równoważnego mu układu takiego, by moduły kongruencji były parami względnie pierwsze:

\(\displaystyle{ x\equiv 7(mod 12) \Longleftrightarrow\left\{\begin{array}{l} x\equiv 7(mod 3)\\x\equiv 7(mod 4) \end{array}}\)

Co jest równoważne:
\(\displaystyle{ \left\{\begin{array}{l} x\equiv 1(mod 3)\\x\equiv 3(mod4) \end{array}}\)

\(\displaystyle{ x=1+3\cdot k}\)
\(\displaystyle{ 1+3\cdot k\equiv 3(mod4)}\)
\(\displaystyle{ 3\cdot k\equiv 2(mod4)}\)

Mnożę obydwie strony przez 3:

\(\displaystyle{ 9\cdot k\equiv 6(mod4)}\)
\(\displaystyle{ k=2+4\cdot s}\)

A więc:

\(\displaystyle{ x=1+3\cdot k=1+3\cdot (2+4\cdot s)=7+12\cdot s}\)
\(\displaystyle{ 7+12\cdot s\equiv 0(mod 5)}\)
\(\displaystyle{ 2+2\cdot s\equiv 0(mod5)}\)
\(\displaystyle{ 2\cdot s\equiv 3(mod 5)}\)

I pomnożyłam znowu przez 3 obydwie strony:

\(\displaystyle{ 6\cdot s\equiv 9(mod 5)}\)
\(\displaystyle{ s\equiv 4(mod 5)}\)
\(\displaystyle{ s=4+5\cdot t}\)

A więc:

\(\displaystyle{ x=7+12\cdot s=7+12\cdot (4+5\cdot t)=55+60\cdot t}\)
\(\displaystyle{ 55+60\cdot t\equiv 1(mod 3)}\)
\(\displaystyle{ 1+60\cdot t\equiv 1(mod 3)}\)
\(\displaystyle{ 60\cdot t\equiv 0(mod 3)}\)

A więc otrzymuję (jak się nie mylę) nierówność tożsamościową.

\(\displaystyle{ 55+60\cdot t\equiv 0(mod 2)}\)
\(\displaystyle{ 1+60\cdot t\equiv 0(mod 2)}\)
\(\displaystyle{ 60\cdot t\equiv 1(mod 2)}\)

I w tym miejscu pojawia się problem, który polega na mojej bezradności. Po prostu nie wiem co dalej.

W temacie zadania pisze, że rozwiązać o ile to możliwe. Jednak ani w tym układzie ani w drugim nie jestem w stanie rozwiązać go do końca.
Czy w takim razie jest możliwe rozwiązanie tego układu? Bardzo proszę o pomoc, o pewne wskazówki i informacje które pomogą mi rozwiązać to zadanie.

Będę bardzo wdzięczna.

[Piotr Rutkowski]

Znaczy nie sprawdzałem pełni Twoejgo zapisu, ale to co napisałaś na końcu jest oczywistą sprzecznością

[JustynaB.]

A więc sprzeczność wychodzi wtedy kiedy mam coś takiego:

\(\displaystyle{ 60\cdot t\equiv 1(mod 2)}\)

A tożsamość, gdy:

\(\displaystyle{ 60\cdot t\equiv 0(mod 2)}\)

Bardzo proszę o wyjaśnienie moich wątpliwości

[Piotr Rutkowski]

No tak, masz rację. Dzieje się tak dlatego, że z zapisu \(\displaystyle{ 60t\equiv 1 \ (mod2)}\) wynika, że \(\displaystyle{ 60t=2k+1}\) Natomiast z zapisu \(\displaystyle{ 60t\equiv 0 \ (mod2)}\) jest spełnione dla każdego t

[JustynaB.]

Bardzo dziękuję za pomoc

[Sir George]

BTW, już z księżyca widać, że układ jest sprzeczny...

A dokładniej sprzeczny jest układ kongruencji: \(\displaystyle{ \left\{\begin{array}{ll}x \equiv 7 & (\mod 12) \cr & \cr x\equiv 8 & (\mod 14)\end{array}\right.}\)

Po prostu z pierwszej kongruencji wynika, że x jest nieparzyste, a z drugiej natomiast, że jest parzyste...

Pozdrawiam ...

[Piotr Rutkowski]

No to prawda, ale mówiłem, że nie sprawdzałem początku

[JustynaB.]

Mam jeszcze jedną prośbę, także związaną z modułami.
Mam rozwiązać takie równianie

\(\displaystyle{ 10\cdot x\equiv 14(mod 12)}\)

I to potrafię rozwiązać. Chodzi mi tutaj o drugą część tego zadania, która brzmi:
W przypadku gdy istnieje podać rozwiązanie i poszukać najmniejszego rozwiązania nieujemnego

jak sie takie rozwiązanie szuka?? Jak się szuka także największej liczy ujemnej będącej rozwiązaniem szczególnym układu kongruencji?

I jeszcze jedno zadanko:
Wyliczyć:
\(\displaystyle{ d=NWD(a,b)}\)

i mam tutaj wskazać przedstawienie Bezouta dla d, jeśli:

\(\displaystyle{ a=26}\) i \(\displaystyle{ b=19}\)

Oczywiście wyliczyłam NWD, który wynosi:\(\displaystyle{ 1=-8\cdot 26+11\cdot 19}\)
I jak przedstawić to w postaci Bezouta??

[Piotr Rutkowski]

\(\displaystyle{ 10x \equiv 14 (mod12)}\) z tego wynika, że:
\(\displaystyle{ 10x=12l+14 \\ l\in Z}\)
\(\displaystyle{ 5x=6l+7}\)
\(\displaystyle{ x=\frac{6l+7}{5}}\) dalej rozważając prawą stronę:
\(\displaystyle{ 6l+7\equiv l+7 \(mod5)}\) czyli mamy:
\(\displaystyle{ l=5r-7 \\ r\in Z}\), bo musi przystawać do zera mofulo 5
czyli podstawiając:
\(\displaystyle{ x=\frac{6*(5r-7)+7}{5}=\frac{30r-42+7}{5}=\frac{30r-35}{5}=6r-7}\)