układ kongruencji

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
Awatar użytkownika
leszczu450
Użytkownik
Użytkownik
Posty: 4414
Rejestracja: 10 paź 2012, o 23:20
Płeć: Mężczyzna
Lokalizacja: Toruń
Podziękował: 1589 razy
Pomógł: 364 razy

układ kongruencji

Post autor: leszczu450 »

Cześć !

Robię już n-ty raz to zadania i nie wychodzi mi to co chce otrzymać : ) Bo znam wynik!

Układ jest następujący:
\(\displaystyle{ \begin{cases} x \equiv 1 (\mod 2) \\ x \equiv 2 (\mod 3) \\ x \equiv 3 (\mod 4) \\ x \equiv 4 (\mod 5) \\ x \equiv 5 (\mod 6) \\ x \equiv 0 (\mod 7)\end{cases}}\)

Zdaję sobie sprawę, że pewne warunki się gdzieś pokrywają i że trzeba to jakoś uporządkować. Ale zupełnie nie wiem jak.

Ja mimo wszystko robie to na żywca. Nie wiem czy jest sens żebym całe moję błedne rozwiązanie tu zaprezentował. Może z góry mi powiecie co robić w takich przypadkach jak ten. Jaką kongruencje mogę rozdzielić na co i czy sposób rozwiązywania jest taki sam jak przy dwóch, trzech kongruencjach?

Pozdrawiam i z góry dziękuję za pomoc!

Zobaczyłem dopiero teraz, że piąta kongruencja jest tutaj zbędna bo jak się ją rozbije na kongruencje o modułach dwa i trzy to mamy dokładnie to co jest w pierwszej i drugiej linijce. Dochodzę zatem do takiego układu, ale zatrzymuje się w jednym miejscu:

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

I nie wiem jak to ruszyć.
Użytkownik
Użytkownik
Posty: 9833
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2632 razy

układ kongruencji

Post autor: »

Pozbądźmy się najpierw dublujących się (redundantnych) informacji. Zauważmy, że z warunków \(\displaystyle{ x \equiv 1 \pmod 2}\) i \(\displaystyle{ x \equiv 2 \pmod 3}\) wynika, że \(\displaystyle{ x\equiv 5\pmod 6}\), zatem tego ostatniego możemy się pozbyć. Tak samo z warunku \(\displaystyle{ x\equiv 3\pmod 4}\) wynika, że \(\displaystyle{ x \equiv 1 \pmod 2}\), zatem tego ostatniego również możemy się pozbyć. Tak więc nasz układ jest równoważny następującemu:
\(\displaystyle{ \begin{cases}
x \equiv 2 \pmod 3\\
x \equiv 3 \pmod 4\\
x \equiv 4 \pmod 5\\
x \equiv 0 \pmod 7
\end{cases}}\)


A ten układ już spełnia założenia Chińskiego Twierdzenia o Resztach, zatem można już go rozwiązywać stosownym algorytmem - albo tym z Wikipedii, albo przy użyciu systemu niezależnych reszt (który w zasadzie jest tym samym co ten z Wiki, ale ładniej zapisanym), albo też na piechotę.

W tym akurat wypadku łatwo zauważyć, że \(\displaystyle{ x+1}\) jest podzielne przez \(\displaystyle{ 3,4,5}\), zatem jest też podzielne przez \(\displaystyle{ 60}\). Stąd \(\displaystyle{ x=60k-1}\). Tak więc mamy kolejno:
\(\displaystyle{ 60k-1 \equiv 0 \pmod 7\\
4k \equiv 1 \pmod 7\\
k\equiv 2 \pmod 7\\
k=7l+2\\
x= 60(7l+2)-1 =420l+119}\)


Q.
Awatar użytkownika
leszczu450
Użytkownik
Użytkownik
Posty: 4414
Rejestracja: 10 paź 2012, o 23:20
Płeć: Mężczyzna
Lokalizacja: Toruń
Podziękował: 1589 razy
Pomógł: 364 razy

układ kongruencji

Post autor: leszczu450 »

, nie rozumiem pierwszej części. Skąd wiesz co jest zbędne a co nie?
Użytkownik
Użytkownik
Posty: 9833
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2632 razy

układ kongruencji

Post autor: »

Nie rozumiem pytania - pytasz dlaczego wolno mi się pozbyć tego czego się pozbyłem, czy też pytasz skąd wiedziałem co zostawić?

Q.
Awatar użytkownika
leszczu450
Użytkownik
Użytkownik
Posty: 4414
Rejestracja: 10 paź 2012, o 23:20
Płeć: Mężczyzna
Lokalizacja: Toruń
Podziękował: 1589 razy
Pomógł: 364 razy

układ kongruencji

Post autor: leszczu450 »

Qń pisze:Pozbądźmy się najpierw dublujących się (redundantnych) informacji. Zauważmy, że z warunków \(\displaystyle{ x \equiv 1 \pmod 2}\) i \(\displaystyle{ x \equiv 2 \pmod 3}\) wynika, że \(\displaystyle{ x\equiv 5\pmod 6}\), zatem tego ostatniego możemy się pozbyć. Tak samo z warunku \(\displaystyle{ x\equiv 3\pmod 4}\) wynika, że \(\displaystyle{ x \equiv 1 \pmod 2}\)
Nie rozumiem tego : ) Czemu z 2 pierwszych warunków wynika ten piaty?
Użytkownik
Użytkownik
Posty: 9833
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2632 razy

układ kongruencji

Post autor: »

Wynika to z Twierdzenia Chińskiego o Resztach, sam zresztą przecież to zauważyłeś w poprawionej wersji swojego pierwszego postu.

Q.
Awatar użytkownika
leszczu450
Użytkownik
Użytkownik
Posty: 4414
Rejestracja: 10 paź 2012, o 23:20
Płeć: Mężczyzna
Lokalizacja: Toruń
Podziękował: 1589 razy
Pomógł: 364 razy

układ kongruencji

Post autor: leszczu450 »

, dzięki wielkie!! Już wszystko rozumiem : )
ODPOWIEDZ