Układy kongruencji - dlaczego takie rozwiązania?

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
Scrub
Użytkownik
Użytkownik
Posty: 79
Rejestracja: 4 paź 2016, o 18:55
Płeć: Mężczyzna
Podziękował: 36 razy

Układy kongruencji - dlaczego takie rozwiązania?

Post autor: Scrub »

1.
\(\displaystyle{ \begin{cases} x \equiv 1 \pmod{3} \\ x \equiv 1 \pmod{11} \end{cases}}\)
Rozwiązanie: \(\displaystyle{ x = 1+33 \cdot k}\)
Czy nie powinno być \(\displaystyle{ 4+33 \cdot k}\)?

2.
\(\displaystyle{ \begin{cases} x \equiv 1 \pmod{5} \\ x \equiv 22 \pmod{36} \end{cases}}\)
Rozwiązanie: \(\displaystyle{ 166+180 \cdot k}\)
Dlaczego nie \(\displaystyle{ 111+180 \cdot k}\)?

Moje wyniki uzyskałem sposobem przez podstawianie.
Proszę o wytłumaczenie jak dla debila.
Ostatnio zmieniony 11 paź 2017, o 23:20 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości: \pmod.
Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 8570
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 306 razy
Pomógł: 3347 razy

Układy kongruencji - dlaczego takie rozwiązania?

Post autor: kerajs »

Scrub pisze:1.
\(\displaystyle{ \begin{cases} x \equiv 1 \pmod{3} \\ x \equiv 1 \pmod{11} \end{cases}}\)
Rozwiązanie: \(\displaystyle{ x = 1+33 \cdot k}\)
Czy nie powinno być \(\displaystyle{ 4+33 \cdot k}\)?
\(\displaystyle{ (4+33 \cdot k) \pmod{11}=4 \neq 1}\)
Scrub pisze:2.
\(\displaystyle{ \begin{cases} x \equiv 1 \pmod{5} \\ x \equiv 22 \pmod{36} \end{cases}}\)
Rozwiązanie: \(\displaystyle{ 166+180 \cdot k}\)
Dlaczego nie \(\displaystyle{ 111+180 \cdot k}\)?
\(\displaystyle{ (111+180 \cdot k) \pmod{36}=3 \neq 22}\)
Ostatnio zmieniony 11 paź 2017, o 23:21 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości: \pmod.
Scrub
Użytkownik
Użytkownik
Posty: 79
Rejestracja: 4 paź 2016, o 18:55
Płeć: Mężczyzna
Podziękował: 36 razy

Układy kongruencji - dlaczego takie rozwiązania?

Post autor: Scrub »

Ok, więc jak to prawidłowo obliczyć?
I dlaczego nie można przez podstawianie?

Tu na przykład podstawianie daje poprawny wynik:
\(\displaystyle{ \begin{cases} x \equiv 1 \pmod{2} \\ x \equiv 2 \pmod{3} \end{cases} \\
5+6 \cdot k}\)
Ostatnio zmieniony 11 paź 2017, o 23:22 przez Jan Kraszewski, łącznie zmieniany 2 razy.
Powód: Poprawa wiadomości: \pmod.
pasman
Użytkownik
Użytkownik
Posty: 171
Rejestracja: 26 lut 2016, o 17:32
Płeć: Mężczyzna
Lokalizacja: Łódź
Podziękował: 1 raz
Pomógł: 14 razy

Układy kongruencji - dlaczego takie rozwiązania?

Post autor: pasman »

Scrub pisze:Ok, więc jak to prawidłowo obliczyć?
I dlaczego nie można przez podstawianie?
można przez podstawienie.
pokaż co i gdzie podstawiasz.
Scrub
Użytkownik
Użytkownik
Posty: 79
Rejestracja: 4 paź 2016, o 18:55
Płeć: Mężczyzna
Podziękował: 36 razy

Układy kongruencji - dlaczego takie rozwiązania?

Post autor: Scrub »

Z punktu 1.
\(\displaystyle{ 1+3 \cdot (1+11 \cdot k) = 4+33 \cdot k}\)-- 5 paź 2017, o 19:59 --Pomoże ktoś?
Podobny przypadek tutaj:
Metoda podstawiania daje inny wynik, tylko że tam gościu od razu napisał wynik bez żadnych obliczeń :/
Scrub
Użytkownik
Użytkownik
Posty: 79
Rejestracja: 4 paź 2016, o 18:55
Płeć: Mężczyzna
Podziękował: 36 razy

Układy kongruencji - dlaczego takie rozwiązania?

Post autor: Scrub »

Odświeżam. Naprawdę nikt nie wie?
Jan Kraszewski
Administrator
Administrator
Posty: 34125
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Układy kongruencji - dlaczego takie rozwiązania?

Post autor: Jan Kraszewski »

Scrub pisze:Z punktu 1.
\(\displaystyle{ 1+3 \cdot (1+11 \cdot k) = 4+33 \cdot k}\)
Ale skąd Ty to wziąłeś?
Scrub pisze:Tu na przykład podstawianie daje poprawny wynik:
\(\displaystyle{ \begin{cases} x \equiv 1 \pmod{2} \\ x \equiv 2 \pmod{3} \end{cases} \\
5+6 \cdot k}\)
Zbieg okoliczności.
Scrub pisze:Ok, więc jak to prawidłowo obliczyć?
Skoro \(\displaystyle{ x \equiv 1 \pmod{11}}\), to \(\displaystyle{ x=11k+1}\), zatem z \(\displaystyle{ x \equiv 1 \pmod{3}}\) mamy

\(\displaystyle{ 11k+1\equiv 1 \pmod{3} \\
11k\equiv 0 \pmod{3} \\
22k\equiv 0\pmod{3} \\
k\equiv 0 \pmod{3}}\)


zatem \(\displaystyle{ k=3m}\), skąd \(\displaystyle{ x=11\cdot 3m+1=33m+1}\).

JK
Scrub
Użytkownik
Użytkownik
Posty: 79
Rejestracja: 4 paź 2016, o 18:55
Płeć: Mężczyzna
Podziękował: 36 razy

Re: Układy kongruencji - dlaczego takie rozwiązania?

Post autor: Scrub »

Dzięki, wygląda na to że działa ta metoda
Jeszcze mam pytanie, czy jest jakiś sposób na doprowadzanie pojedynczej kongruencji do postaci, w której z lewej strony mamy samo \(\displaystyle{ x}\)? Można kombinować z mnożeniem, żeby po operacji modulo tyle wyszło, ale w niektórych przykładach nie mogę nic wymyślić.
Np. mamy
\(\displaystyle{ 4x \equiv 2 \pmod{15}}\)
więc mnożymy przez \(\displaystyle{ 4}\)
\(\displaystyle{ 16x \equiv 8 \pmod{15}}\)
\(\displaystyle{ \Rightarrow x \equiv 8 \pmod{15}}\)
Ten przykład był prosty i sposób rozwiązania rzucał się w oczy, a co zrobić gdy tak nie jest?
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Układy kongruencji - dlaczego takie rozwiązania?

Post autor: Premislav »

Tak. Gdy masz kongruencję
\(\displaystyle{ nx\equiv k \pmod{m}}\), przy czym \(\displaystyle{ (m,n)=1}\), to znajdujesz element odwrotny do
\(\displaystyle{ n}\) w \(\displaystyle{ \ZZ^*_m}\) z mnożeniem (co można zgadnąć lub znaleźć za pomocą rozszerzonego algorytmu Euklidesa), po czym mnożysz stronami przez ten element odwrotny.
Przykładowo:
\(\displaystyle{ 4x\equiv 2\pmod{15}\\ (15,4)=1\\15=3\cdot 4+3\\4=1\cdot 3+1\\1=4-3=4-(15-3\cdot 4)=4\cdot 4-15}\)
czyli
\(\displaystyle{ 4\cdot 4=15+1\equiv 1\pmod{15}}\), więc szukaną odwrotnością jest \(\displaystyle{ 4}\) (akurat w tak prostym przykładzie można ordynarnie zgadnąć).
ODPOWIEDZ