Układ kongruencji

[dosmiko]

Dzień dobry,
potrzebuję pomocy przy rozwiązaniu takiego układu kongruencji:
x = 2(mod 4)
x = 3(mod 9)
x = 5(mod 7)

1.Zacząłem tak (z pierwszej kongruencji):
x = 4k + 2
2.Podstawiłem to do drugiej kongruencji
4k + 2 = 3(mod 9) /-2
4k = 1(mod 9)
3. Z rozszerzonego algorytmu Euklidesa wyszło mi, że odwrotnością 4 modulo 9 jest 7. Zapisałem, więc:
k = 7(mod 9)
4. Przekształciłem to do postaci:
k = 9m+7
5. Następnie wynik(k) podstawiłem do równania z x'em:
x = 4(9m+7)+2 = 36m+30
6. Podstawiłem x=36m+30 do trzeciej kongruencji i dostałem:
36m+30 = 5(mod 7)/-30
36m = -25(mod 7)
7. Szukam odwrotności 36 modulo 7. Wyszło mi 1, więc:
m = 1(mod 7)
8. Przekształciłem do postaci:
m = 7l + 1
9. Wynik (m) podstawiam pod k, a następnie, to k znów pod x, otrzymuję:
x = 252l + 66
No i wynik jest nieprawidłowy. Na zajęciach w krokach 6 i 7 wyszło inaczej, bo wyszło, że m = 3(mod 7). Wtedy wynik wychodzi prawidłowy. Nie mam jednak pojęcia skąd to 3 się wzięło.
Proszę o wytłumaczenia. Dziękuję

[grdv10]

W tej chwili nie jestem w stanie tego zanalizować, ale zobacz na chińskie twierdzenie o resztach.

[kerajs]

6. Podstawiłem x=36m+30 do trzeciej kongruencji i dostałem:
36m+30 = 5(mod 7)/-30
36m = -25(mod 7)
7. Szukam odwrotności 36 modulo 7. Wyszło mi 1, więc:
m = 1(mod 7)
8. Przekształciłem do postaci:
m = 7l + 1

Między 6. a 7. zgubiłeś -25.
dostałbyś:
\( m=1 \cdot (-25) ( \ mod \ 7)\\
m=3( \ mod \ 7)
\)

Ponadto można sobie uprościć obliczenia:
\(36m = -25( \ mod \ 7)\\
(7 \cdot 5+1)m=(-28+3)( \ mod \ 7)\\
m=3( \ mod \ 7)\)

[dosmiko]

W tej chwili nie jestem w stanie tego zanalizować, ale zobacz na chińskie twierdzenie o resztach.

Zastosowałem chińskie twierdzenie o resztach i wyszło. Dziękuję

6. Podstawiłem x=36m+30 do trzeciej kongruencji i dostałem:
36m+30 = 5(mod 7)/-30
36m = -25(mod 7)
7. Szukam odwrotności 36 modulo 7. Wyszło mi 1, więc:
m = 1(mod 7)
8. Przekształciłem do postaci:
m = 7l + 1

Między 6. a 7. zgubiłeś -25.
dostałbyś:
\( m=1 \cdot (-25) ( \ mod \ 7)\\
m=3( \ mod \ 7)
\)

Ponadto można sobie uprościć obliczenia:
\(36m = -25( \ mod \ 7)\\
(7 \cdot 5+1)m=(-28+3)( \ mod \ 7)\\
m=3( \ mod \ 7)\)

Nie wiem czy dobrze zrozumiałem tok rozumowania. Dlatego pozwolę sobie napisać przykłady, które przerobiłem samemu:
Pierwszy:
15m = -6(mod 7)
(7 * 2 +1 )m = (7 - 1)(mod 7)
m = 1(mod 7)

Drugi:
105m = -22(mod 8 )
(13 * 8 + 1)m = ( (-3) * 8 + 2)(mod 8 )
m = 2(mod 8 )

Jest w porządku?
Nie rozumiem trochę tego:
"Między 6. a 7. zgubiłeś -25.
dostałbyś:
m=1⋅(−25)( mod 7)
m=3( mod 7)"

[dosmiko]

Znalazłem analogię, ale nie wiem czy jest poprawna:
m=1⋅(−25)( mod 7)
m=3( mod 7), bo 1*(-25)=-25 => -25+7+7+7+7=3 (dodajemy dopóki nie dostaniemy liczby dodatniej jak najbliższej 0).

Teraz mam taki przykład:
x = 2 (mod 5)
x = 6 (mod 11)
1. Przekształcam x = 2 (mod 5) na x = 2 + 5i
2. Wstawiam do drugiej kongruencji:
2 + 5i = 6 (mod 11)
5i = 4 (mod 11)
3. Znajduje odwrotnosc 5 modulo 11. Jest ona równa 9. Mam, więc:
i = 9*4 (mod 11)
i = 36 (mod 11), 36 - 11 - 11- 11 = 3 (odejmujemy dopóki nie dostaniemy liczby dodatniej jak najbliższej 0). Mamy:
i = 3 (mod 11)
Dalej analogicznie jak w pierwszym przykładzie. Dobrze rozumiem?

[kerajs]

Pierwszy:
15m = -6(mod 7)
(7 * 2 +1 )m = (7 - 1)(mod 7)
m = 1(mod 7)

Przepisując zgubiłeś minus w drugiej linijce. Pewnie miało być (7 * 2 +1 )m = -(7 - 1)(mod 7) albo (7 * 2 +1 )m = (-7 + 1)(mod 7)
Wynik: x=7k+1

Drugi:
105m = -22(mod 8 )
(13 * 8 + 1)m = ( (-3) * 8 + 2)(mod 8 )
m = 2(mod 8 )

OK

Teraz mam taki przykład:
x = 2 (mod 5)
x = 6 (mod 11)
1. Przekształcam x = 2 (mod 5) na x = 2 + 5i
2. Wstawiam do drugiej kongruencji:
2 + 5i = 6 (mod 11)
5i = 4 (mod 11)
3. Znajduje odwrotnosc 5 modulo 11. Jest ona równa 9. Mam, więc:
i = 9*4 (mod 11)
i = 36 (mod 11), 36 - 11 - 11- 11 = 3 (odejmujemy dopóki nie dostaniemy liczby dodatniej jak najbliższej 0). Mamy:
i = 3 (mod 11)
Dalej analogicznie jak w pierwszym przykładzie. Dobrze rozumiem?

Dobrze. Wynik to x=55k+17. Warto zawsze sprawdzić czy uzyskana liczba spełnia równania z układu.

Znalazłem analogię, ale nie wiem czy jest poprawna:
m=1⋅(−25)( mod 7)
m=3( mod 7), bo 1*(-25)=-25 => -25+7+7+7+7=3 (dodajemy dopóki nie dostaniemy liczby dodatniej jak najbliższej 0).

Jest dobrze. Wygodniejsza jest nieujemna liczba mniejsza od dzielnika modulo.

[dosmiko]

Dziękuję za pomoc. Myślę, że już rozumiem.