rozwiązanie układu kongruencji

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Szymon66
Użytkownik
Użytkownik
Posty: 9
Rejestracja: 19 sie 2019, o 21:09
Płeć: Mężczyzna
Lokalizacja: Zalesie
Podziękował: 1 raz

rozwiązanie układu kongruencji

Post autor: Szymon66 »

Witam, szukam małej pomocy z układami kongruencji otóż, obyłem się z prostszymi przykładami już aczkolwiek trafiłem na takie coś.
a)
\(\displaystyle{ \begin{cases} x\equiv 1 \pmod{15} \\
x\equiv 22 \pmod{36} \end{cases}}\)

b)
\(\displaystyle{ \begin{cases} x\equiv 1 \pmod{12} \\
x\equiv 7 \pmod{18} \\
x\equiv 13 \pmod{42} \end{cases}}\)


Teraz by użyć CHTWoR, moduły muszą być względnie pierwsze, zgaduje, że trzeba je rozbić tak by powstało więcej równań z czego kilka z nich się skróci tylko, że doszedłem do czegoś takiego i niestety nie bardzo wiem jak je "skracać"?

Przyklad
a)
\(\displaystyle{ \begin{cases} x\equiv 1 \pmod{3} \\
x\equiv 1 \pmod{4} \\
x\equiv 2 \pmod{4} \\
x\equiv 4 \pmod{9} \end{cases}}\)



b)
\(\displaystyle{ \begin{cases} x\equiv 1 \pmod{3}\\
x\equiv 1 \pmod{4}\\
x\equiv 1 \pmod{2}\\
x\equiv 7 \pmod{9} \\
x\equiv 1 \pmod{6} \\
x\equiv 6 \pmod{7} \end{cases}}\)



Kombinowałem już na kilka sposobów niestety nie potrafię znaleźć zależności, w przykładzie b) wypisałem sobie kilkanaście liczb spełniających ten układ "nierozbity" i wnioskuję, że wynikiem będzie \(\displaystyle{ 97+k \cdot 252}\) ale jak do tego dojść poprzez CHTWoR, co tu się dokładnie skraca? Czy dobrze rozbiłem te układy?
Ostatnio zmieniony 19 sie 2019, o 21:59 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Używaj LaTeXa do wszystkich wyrażeń matematycznych.
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: rozwiązanie układu kongruencji

Post autor: Dasio11 »

Zachodzą równoważności

\(\displaystyle{ \begin{array}{llcl}
x \equiv \phantom{2}1 \pmod{15} & \iff x \equiv \phantom{2}1 \pmod{3} & \& & x \equiv \phantom{2}1 \pmod{5} \\[1ex]
x \equiv 22 \pmod{36} & \iff x \equiv 22 \pmod{4} & \& & x \equiv 22 \pmod{9} \\
& \iff x \equiv \phantom{2}2 \pmod{4} & \& & x \equiv \phantom{2}4 \pmod{9}
\end{array}}\)


Widać, że z warunku \(\displaystyle{ x \equiv 4 \pmod{9}}\) wynika warunek \(\displaystyle{ x \equiv 1 \pmod{3}}\), więc ten drugi można usunąć i dostać układ, dla którego spełnione są założenia Chińskiego Twierdzenia o Resztach. Co więcej, pierwszy krok dalszej części jest za darmo - wystarczy odwrócić drugi z powyższych ciągów równoważności.
Szymon66
Użytkownik
Użytkownik
Posty: 9
Rejestracja: 19 sie 2019, o 21:09
Płeć: Mężczyzna
Lokalizacja: Zalesie
Podziękował: 1 raz

Re: rozwiązanie układu kongruencji

Post autor: Szymon66 »

Okej dziękuję za pomoc, faktycznie widać tą zależność, czy w przykładzie b) moge usunąć te równania?
\(\displaystyle{ x\equiv 1 \pmod{3}\\ x\equiv 1 \pmod{4}\\ x\equiv 1 \pmod{2}}\)
ponieważ rozwiązania są w \(\displaystyle{ x\equiv 1 \pmod{6}}\)?-- 20 sie 2019, o 00:29 --Okej, można zamknąć, znalazłem inną zależność, wynik prawidłowy, dziekuje za pomoc
ODPOWIEDZ