Rozwiąż układ równań

[kacperus]

\(\displaystyle{ \begin{cases} x+y=26\\ 13x+y=4 \end{cases}}\)
w \(\displaystyle{ \ZZ_{14}}\)

zacząłem tak:
\(\displaystyle{ 12x=-22\pmod{14}}\)

szukam odwrotności do \(\displaystyle{ 12}\) no i nie ma... nie wiem jak zabrać się za takie zadanie.

[Premislav]

\(\displaystyle{ 12x\equiv -22\pmod{14}}\)
oznacza, że istnieje taka liczba całkowita \(\displaystyle{ k}\), iż
\(\displaystyle{ 12x=14k-22}\), tj.
\(\displaystyle{ 6x=7k-11}\),
innymi słowy
\(\displaystyle{ 6x\equiv -11\pmod{7}}\)
(czy jak kto woli \(\displaystyle{ 6x\equiv 3\pmod{7}}\)).
I dalej chyba sobie poradzisz…

Ja bym zaczął inaczej, a mianowicie dodałbym oba równania i zredukował modulo \(\displaystyle{ 14}\), ale co kto lubi.

[kacperus]

wyszło mi:
\(\displaystyle{ 6x=-11 \pmod{7}}\)
z rozszerzonego algorytmu euklidesa:
\(\displaystyle{ 1=1 \cdot 7-1 \cdot 6}\)
odwrotność \(\displaystyle{ 6}\) to \(\displaystyle{ -1}\) albo \(\displaystyle{ 6}\)

\(\displaystyle{ 6x=-11}\) mnożę obustronnie przez \(\displaystyle{ 6}\)
\(\displaystyle{ 36x=-66 \pmod{7}}\)
\(\displaystyle{ x = 4;}\)

teraz po prostu za \(\displaystyle{ x}\)wstawiam \(\displaystyle{ 4}\) jak w zwykłych równaniach?

\(\displaystyle{ 4+y=26 \pmod{14} \\
y=22 \pmod{14} \\
y = 8}\)

[Premislav]

teraz po prostu za \(\displaystyle{ x}\) wstawiam \(\displaystyle{ 4}\) jak w zwykłych równaniach?

No prawie, ale nie tak szybko, wszakże uzyskałeś z tego rozumowania, że \(\displaystyle{ x\equiv 4\pmod{7}}\), a w \(\displaystyle{ \ZZ_{14}}\) są dwa elementy spełniające ten warunek: \(\displaystyle{ 4}\) oraz \(\displaystyle{ 11}\). Należy więc rozważyć dwa przypadki.

[kacperus]

Rozumiem, że NWD = 2 stąd są dwa rozwiązania ale nie wiem co zrobić aby wyliczyć drugi element 11.

-- 3 paź 2018, o 20:07 --

jeśli \(\displaystyle{ \pmod = 7}\) to czy to \(\displaystyle{ 11}\) nie powinno być również zredukowane do\(\displaystyle{ 4}\) ?

gdy odwrotność 6 = -1:
\(\displaystyle{ 6x\cdot (-1) = 11 \pmod 7}\)
\(\displaystyle{ -6x=11 \pmod 7}\)
\(\displaystyle{ x = 11 \pmod 7}\)
\(\displaystyle{ x = 4}\)

gdy odwrotność 6 = 6:
\(\displaystyle{ 6x\cdot 6=-11\cdot 6 \pmod 7}\)
\(\displaystyle{ x=-66 \pmod 7}\)
\(\displaystyle{ x = 4}\)

w dwóch przypadkach wychodzi mi tylko 1 rozwiązanie. Zapewne czegoś nie rozumiem ale nie wiem czego.-- 3 paź 2018, o 23:09 --Proszę o jakąś podpowiedź

[Premislav]

Układ równań masz rozwiązać w \(\displaystyle{ \ZZ_{14}}\), tymczasem doszliśmy do tego, że
\(\displaystyle{ x\equiv 4\pmod{7}}\), tj. istnieje takie całkowite \(\displaystyle{ m}\), że \(\displaystyle{ x=7m+4}\). Są dwa takie iksy w \(\displaystyle{ \ZZ_{14}}\), oczywiście różniące się o pewną krotność \(\displaystyle{ 7}\). Dla każdego z tych dwóch podstawiasz i masz rozwiązanie.
Trochę bez sensu piszesz też „gdy odwrotność \(\displaystyle{ 6=-1}\), gdy odwrotność \(\displaystyle{ 6=6}\)". W \(\displaystyle{ \ZZ_7}\) mamy \(\displaystyle{ -1=6}\), bo utożsamiamy liczby różniące się o krotność \(\displaystyle{ 7.}\).

W tym podejściu dość szybko wychodzę trochę poza strukturę \(\displaystyle{ \ZZ_{14}}\), a potem do niej wracam, jeśli nie chcielibyśmy jej opuszczać, to wyglądałoby to tak: w \(\displaystyle{ \ZZ_{14}}\) mamy

\(\displaystyle{ \begin{cases} x+y=26\\ 13x+y=4 \end{cases} \Leftrightarrow \begin{cases} x+y=12\\ 13x+y=4 \end{cases} \Leftrightarrow \\ \Leftrightarrow \begin{cases} y=12-x \\ y=4-13x\end{cases} \Leftrightarrow \\ \Leftrightarrow \begin{cases}y=12-x\\ 12-x=4-13x\end{cases} \Leftrightarrow \\ \Leftrightarrow \begin{cases} y=12-x\\ 2x=8 \end{cases}}\)
i nie możemy sobie tak po prostu podzielić tego drugiego równania przez \(\displaystyle{ 2}\), gdyż \(\displaystyle{ 2}\) jest dzielnikiem zera w \(\displaystyle{ \ZZ_{14}}\). Przepisujemy to jako:
\(\displaystyle{ \begin{cases} y=12-x \\ 2(x-4)=0 \end{cases}}\) i albo jeden z czynników w tym ostatni równaniu jest zerem (w \(\displaystyle{ \ZZ_{14}}\)), tj. \(\displaystyle{ x-4=0}\),
albo \(\displaystyle{ 2(x-4)}\) jest rozkładem zera na iloczyn niezerowych elementów \(\displaystyle{ \ZZ_{14}}\), a istnieje tylko jeden taki, \(\displaystyle{ 2\cdot 7}\).