Rozwiązywanie układu równań - kongruencje

[uczennn]

Cześć,
rozwiązuje układ równań:

\(\displaystyle{ \begin{cases} x \equiv 1\pmod{3} \\ x \equiv 3\pmod{5} \\ x \equiv 2\pmod{7} \end{cases}}\)

i w pewnym momencie natrafiłem na kongruencję, której nie potrafię przekształcić:
\(\displaystyle{ 15z \equiv -11\pmod{7}}\)

Wie ktoś może jak to przekształcić?

[Jan Kraszewski]

Wskazówka: \(\displaystyle{ 15=14+1}\).

JK

[uczennn]

czyli mam odjąć \(\displaystyle{ 14z}\)? czy \(\displaystyle{ 14}\)?

[Jan Kraszewski]

A jak myślisz?

JK

[uczennn]

\(\displaystyle{ 14z}\)

[Jan Kraszewski]

Zgadza się.

JK

[uczennn]

A dlaczego tak można?

[Jan Kraszewski]

Bo \(\displaystyle{ 14z\equiv 0\pmod{7}}\).

JK

[uczennn]

Czyli mozna tak robić tylko wtedy kiedy dzieli się ta liczba (którą odejmuje) z modulo bez reszty, tak?

A z tym jak obie poradzić? Mam odjąć \(\displaystyle{ 29m}\), ale wtedy zgodnie z tym co napisałem wyżej to jest niepoprawnie.
\(\displaystyle{ 30m \equiv -7\pmod{11}}\)

A jak mogę sprawdzić czy przekształcenia które robię są poprawne?

[Jan Kraszewski]

Czyli mozna tak robić tylko wtedy kiedy dzieli się ta liczba (którą odejmuje) z modulo bez reszty, tak?

Chyba nie wiesz, jakie działania można wykonywać na kongruencjach.

Przecież mając \(\displaystyle{ 15z \equiv -11\pmod{7}}\) nie odjąłeś od lewej strony \(\displaystyle{ 14z}\), tylko - formalnie rzecz biorąc - odjąłeś stronami kongruencję \(\displaystyle{ 14z\equiv 0\pmod{7}}\), bo kongruencje można odejmować stronami.

Albo inaczej, zauważyłeś, że \(\displaystyle{ 15z \equiv z\pmod{7}}\) i skorzystałeś z przechodniości przystawania modulo.

A z tym jak obie poradzić? Mam odjąć \(\displaystyle{ 29m}\), ale wtedy zgodnie z tym co napisałem wyżej to jest niepoprawnie.
\(\displaystyle{ 30m \equiv -7\pmod{11}}\)

Jak nietrudno zauważyć, \(\displaystyle{ 30m \equiv -3m\pmod{11}}\), dostajesz więc \(\displaystyle{ 3m \equiv 7\pmod{11}}\), stąd \(\displaystyle{ 12m \equiv 28\pmod{11}}\), czyli \(\displaystyle{ m \equiv 6\pmod{11}}\).

A jak mogę sprawdzić czy przekształcenia które robię są poprawne?

Poczytać jakiś podręcznik i nauczyć się, co wolno robić z kongruencjami?
Zrozumieć, na czym polegają działania na kongruencjach?

JK

[uczennn]

Jak nietrudno zauważyć, \(\displaystyle{ 30m \equiv -3m\pmod{11}}\), dostajesz więc \(\displaystyle{ 3m \equiv 7\pmod{11}}\), stąd \(\displaystyle{ 12m \equiv 28\pmod{11}}\), czyli \(\displaystyle{ m \equiv 6\pmod{11}}\).

Możesz mi wytłumaczyć krok po kroku jak to zrobiłeś?

[Jan Kraszewski]

Przekształcasz \(\displaystyle{ 30m \equiv -7\pmod{11}}\). Skoro \(\displaystyle{ 30m \equiv -3m\pmod{11}}\) (bo \(\displaystyle{ 11\mid(30m-(-3m))}\), to z przechodniości przystawania modulo masz \(\displaystyle{ -3m \equiv -7\pmod{11}}\), czyli \(\displaystyle{ 3m \equiv 7\pmod{11}}\) (pomnożyłem obustronnie przez \(\displaystyle{ -1}\)).

Dalej mnożę obustronnie otrzymaną kongruencję przez \(\displaystyle{ 4}\) i dostaję \(\displaystyle{ 12m \equiv 28\pmod{11}}\). Ponieważ \(\displaystyle{ 12m \equiv m\pmod{11}}\) oraz \(\displaystyle{ 28 \equiv 6\pmod{11}}\), więc z przechodniości przystawania modulo masz \(\displaystyle{ m \equiv 6\pmod{11}}\).

JK

[uczennn]

A skąd wzięło się \(\displaystyle{ -3m}\) w kongruencji w 2 wierszu?
I dlaczego dodajesz do \(\displaystyle{ b}\) literę \(\displaystyle{ m}\) ?
No i skąd się wzięła kongruencja \(\displaystyle{ 28\equiv 6\pmod{11}}\) i kongruencja \(\displaystyle{ 12m\equiv m\pmod{11}}\)? Sorry za brak znaku kongruencji ale pisze z telefonu

[Jan Kraszewski]

A skąd wzięło się \(\displaystyle{ -3m}\) w kongruencji w 2 wierszu?

Tak jak Ci napisałem: z przechodniości przystawania modulo. Jeśli \(\displaystyle{ s\equiv t\pmod{p}}\) i \(\displaystyle{ t\equiv w\pmod{p}}\), to \(\displaystyle{ s\equiv w\pmod{p}}\).

I dlaczego dodajesz do \(\displaystyle{ b}\) literę \(\displaystyle{ m}\) ?

Nie rozumiem pytania.

No i skąd się wzięła kongruencja \(\displaystyle{ 28\equiv 6\pmod{11}}\) i kongruencja \(\displaystyle{ 12m\equiv m\pmod{11}}\)?

Jeżeli zajmujesz się kongruencjami, to wypadałoby znać definicję kongruencji - te kongruencje wzięły się wprost z definicji.

JK

[uczennn]

A jak to :\(\displaystyle{ 30m \equiv -7\pmod{11}}\) przekształciłeś do postaci \(\displaystyle{ 30m \equiv -3m\pmod{11}}\)
Czyli to: \(\displaystyle{ 30m \equiv -3m\pmod{11}}\) wymyśliłeś z tego powodu aby mieć resztę równą zero?