Układy kongruencji - dlaczego takie rozwiązania?
Układy kongruencji - dlaczego takie rozwiązania?
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.
\(\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.
Powód: Poprawa wiadomości: \pmod.
- kerajs
- 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?
\(\displaystyle{ (4+33 \cdot k) \pmod{11}=4 \neq 1}\)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{ (111+180 \cdot k) \pmod{36}=3 \neq 22}\)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}\)?
Ostatnio zmieniony 11 paź 2017, o 23:21 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości: \pmod.
Powód: Poprawa wiadomości: \pmod.
Układy kongruencji - dlaczego takie rozwiązania?
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}\)
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.
Powód: Poprawa wiadomości: \pmod.
-
- 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?
można przez podstawienie.Scrub pisze:Ok, więc jak to prawidłowo obliczyć?
I dlaczego nie można przez podstawianie?
pokaż co i gdzie podstawiasz.
Układy kongruencji - dlaczego takie rozwiązania?
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ń :/
\(\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ń :/
-
- 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?
Ale skąd Ty to wziąłeś?Scrub pisze:Z punktu 1.
\(\displaystyle{ 1+3 \cdot (1+11 \cdot k) = 4+33 \cdot k}\)
Zbieg okoliczności.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}\)
Skoro \(\displaystyle{ x \equiv 1 \pmod{11}}\), to \(\displaystyle{ x=11k+1}\), zatem z \(\displaystyle{ x \equiv 1 \pmod{3}}\) mamyScrub pisze:Ok, więc jak to prawidłowo obliczyć?
\(\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
Re: Układy kongruencji - dlaczego takie rozwiązania?
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?
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?
- Premislav
- 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?
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ąć).
\(\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ąć).