Rozwiąż kongruencję

Minnie_ · Post autor: **Minnie_** » 17 sty 2010, o 12:16

Mam do rozwiązania kongruencję
A) \(\displaystyle{ 8x\equiv 5(mod11)}\)
B) \(\displaystyle{ 3x\equiv 2(mod4)}\)
C) \(\displaystyle{ 25x\equiv 8(mod29)}\)
Proszę o pomoc w rozwiązaniu i małe proste wytłumaczenie

infty · Post autor: **infty** » 17 sty 2010, o 13:37

Robiłam na podstawie .

Rozwiążmy najpierw \(\displaystyle{ 8x \equiv 5 \pmod{11}.}\) Wiemy, że \(\displaystyle{ gcd(8,11)=1}\), więc mamy jedno rozwiązanie:
\(\displaystyle{ x=2+11k}\). Teraz podstawmy wynik w drugim równaniu:
\(\displaystyle{ 3(2+11k) \equiv 2 \pmod{4}}\)
\(\displaystyle{ 6+33k \equiv 2 \pmod{4}}\)
\(\displaystyle{ 33k \equiv 0 \pmod{4}}\)
Obliczamy ponownie \(\displaystyle{ gcd(33,4)=1}\), zatem mamy jedno rozwiązanie \(\displaystyle{ k=0+4t}\).
Wynik wstawiamy za \(\displaystyle{ x}\) w ostatniej równości:
\(\displaystyle{ 25(4t) \equiv 8 \pmod{29}}\)
\(\displaystyle{ 100t \equiv 8 \pmod{29}}\)
\(\displaystyle{ gcd(100,29)=1}\), mamy więc jedno rozwiązanie \(\displaystyle{ t=14+29s}\).
Ostatecznie \(\displaystyle{ x=2+11k=2+44t=2+44(14+s)=44s + 14*44+2}\), inaczej \(\displaystyle{ x \equiv 2 \pmod{44}}\).

Minnie_ · Post autor: **Minnie_** » 17 sty 2010, o 13:55

To nie jest układ kongruencji tylko 3 pojedyncze równania. Czy ktoś pomoże w rozwiązaniu?

infty · Post autor: **infty** » 17 sty 2010, o 14:35

W takim razie pierwszą masz rozwiązaną: \(\displaystyle{ x=2+11k}\).
Druga analogicznie. Najpierw szukamy\(\displaystyle{ gcd(3,4)=1.}\) Oznacza
to, że mamy jedno rozwiązanie. Ponieważ liczby są mae od razu widzimy,
że \(\displaystyle{ x\equiv2\pmod4}\) (\(\displaystyle{ 3*2\equiv2\pmod4}\) i możemy dodawać sobie
dowolnie wielokrotności 4). Napisz dokładnie, czego nie rozumiesz, teraz powinieneś rozwiązać
samodzielnie podpunkt C.

Minnie_ · Post autor: **Minnie_** » 17 sty 2010, o 14:46

skąd wiemy że rozwiązaniem pierwszego równania jest \(\displaystyle{ x=2+11k}\)?

infty · Post autor: **infty** » 17 sty 2010, o 15:02

Jak \(\displaystyle{ 2}\) podstawimy pod \(\displaystyle{ x}\) w \(\displaystyle{ 8x \equiv 5 \pmod{11}}\) to otrzymamy:
\(\displaystyle{ 16 \equiv 5 \pmod{11}}\). Skoro działamy w arytmetyce mod 11, to możemy jedenaście
dowolnie odejmować i dodawać do każdej ze stron osobno. Zatem
\(\displaystyle{ 16-11 \equiv 5 \pmod{11}}\). Skoro wyszła nam równość, to \(\displaystyle{ 2}\) rzeczywiście
było rozwiązaniem. Ale ponieważ działamy modulo 11, to możemy sobie dodawać do wyniku
dowolną liczbę liczby 11, czyli tu \(\displaystyle{ 11k.}\) Czyli tak na prawdę jedno rozwiązanie oznacza,
że jest jedno w zbiorze liczb \(\displaystyle{ \{0,...,10\}}\) (do 10, bo arytmetyka modulo 11).

Minnie_ · Post autor: **Minnie_** » 17 sty 2010, o 15:25

Ok ale czy nie ma jakiegoś wzoru czy sposobu na obliczenie \(\displaystyle{ x}\)? Dla małych liczb mogę podstawiać ale dla większych jak w przykładzie c to już jest problem.

infty · Post autor: **infty** » 17 sty 2010, o 16:01

Jest sposób. Jeśli mamy równanie \(\displaystyle{ ax \equiv b \pmod {n}}\)
i \(\displaystyle{ d=gcd(a,n)}\) oraz \(\displaystyle{ d | b}\) to wtedy:
1. obliczamy takie \(\displaystyle{ r}\) i \(\displaystyle{ s}\) z rozszerzonego algorytmu Euklidesa,
że \(\displaystyle{ ra+sn=d}\) ( ... _algorithm)
2. obliczamy \(\displaystyle{ x=\frac{rb}{d}}\)
3. inne rozwiązania, jeśli istnieją, są kongruentne z \(\displaystyle{ x}\) modulo \(\displaystyle{ \frac{n}{d}}\) i należą
do zbioru \(\displaystyle{ \{0,...,(n-1)\}}\)

WhiteRabbit7 · Post autor: **WhiteRabbit7** » 13 kwie 2016, o 14:02

Przepraszam za odkopanie, ale próbuję rozwiązać podpunkt a)\(\displaystyle{ 8x\equiv 5(mod11)}\) na podstawie wskazówek infty i jakoś mi nie wychodzi:
\(\displaystyle{ 11 = 1 \cdot 8+3}\)
\(\displaystyle{ 8=2 \cdot 3+2}\)
\(\displaystyle{ 3=1 \cdot 2+1}\)
\(\displaystyle{ 2=2 \cdot 1+0}\)
Zatem \(\displaystyle{ NWD(11,8)=1}\)
\(\displaystyle{ 1=3-2=3-8+2 \cdot 3=3 \cdot 3-8=3 \cdot (11-8)-8=3 \cdot 11 - 4 \cdot 8}\)
Czyli:
\(\displaystyle{ a=8, b=5, n=11, s=3, r=-4}\)
Podstawiamy do wzoru \(\displaystyle{ x=\frac{rb}{d}}\) i otrzymujemy \(\displaystyle{ x=\frac{(-4) \cdot 5}{1}=-20}\)
Czy może to jest poprawnie zrobione?

Premislav · Post autor: **Premislav** » 13 kwie 2016, o 18:22

Tym sposobem otrzymałeś rozwiązanie szczególne pierwszej kongruencji. Jej rozwiązanie ogólne jest postaci \(\displaystyle{ -20+11k}\) dla \(\displaystyle{ k \in \ZZ}\).

WhiteRabbit7 · Post autor: **WhiteRabbit7** » 13 kwie 2016, o 18:32

Czyli rozumiem, że jeśli polecenie brzmi "rozwiąż kongruencję" to ostateczną odpowiedzią powinna być postać ogólna?
A czy przy poleceniu "rozwiąż układ kongruencji" mam dążyć do uzyskania postaci ogólnej, czy tak jak ma to miejsce chociażby w tym przykładzie (mam na myśli odpowiedź w ostatnim poście w temacie) - 256565.htm do znalezienia najmniejszego, nieujemnego \(\displaystyle{ x}\) ?

Premislav · Post autor: **Premislav** » 13 kwie 2016, o 18:58

Mnie uczono tak (na algebrze abstrakcyjnej), że zawsze podajemy postać ogólną, chyba że polecenie w zadaniu jest inne. Zauważ, że w temacie, do którego link podałeś, w treści zadania żąda się znalezienia najmniejszego rozwiązania nieujemnego, a nie po prostu "rozwiązania kongruencji".

WhiteRabbit7 · Post autor: **WhiteRabbit7** » 13 kwie 2016, o 19:01

Mając przykładowe zadanie, brzmiące właśnie - rozwiąż układ kongruencji:
\(\displaystyle{ \begin{cases}
3x \equiv 42(mod11)
\\ 5x \equiv 42(mod12)
\\ 8x \equiv 18(mod30)\end{cases}}\)

\(\displaystyle{ \begin{cases} 3x \equiv 9(mod11)
\\ 5x \equiv 6(mod12)
\\ 8x \equiv 18(mod30)\end{cases}}\)

\(\displaystyle{ \begin{cases}
55x \equiv 66(mod132)
\\ 36x \equiv 108(mod132)
\end{cases}}\)

\(\displaystyle{ \begin{cases}
55x \equiv 198(mod132)
\\ 36x \equiv 108(mod132)
\end{cases}}\)

\(\displaystyle{ \begin{cases}
19x \equiv 90(mod132)
\\ 8x \equiv 18(mod132)
\end{cases}}\)

\(\displaystyle{ \begin{cases}
570x \equiv 2700(mod3960)
\\ 1056x \equiv 2376(mod3960)
\end{cases}}\)

\(\displaystyle{ 486x\equiv3636(mod3960)}\)

Mogę zakończyć na tym etapie, czy jeszcze należy rozwiązać kongruencję, albo zapisać odpowiedź w postaci \(\displaystyle{ x=3960i +3636}\) ? Bazowałem na rozwiązaniu zamieszczonym w podanym przeze mnie temacie. Przy okazji będę bardzo wdzięczny za sprawdzenie zadania.

Premislav · Post autor: **Premislav** » 13 kwie 2016, o 19:38

Sorry, ale liczby są za duże, żebym to ręcznie sprawdzał, a na komputerze sam możesz.
\(\displaystyle{ 486x\equiv3636(mod3960)}\) to jak dla mnie nie jest jeszcze odpowiedź, należy przedstawić ją w postaci jak niżej. Ja zamieniłbym
\(\displaystyle{ 8x \equiv 18\pmod{30}}\) na \(\displaystyle{ 4x\equiv 9\pmod{15}}\), co dałoby:
\(\displaystyle{ \begin{cases} 3x \equiv 9(mod11) \\ 5x \equiv 6(mod12) \\ 4x \equiv 9(mod 15)\end{cases}}\)
i teraz bym znalazł z Euklidesa elementy odwrotne względem odpowiednio:
-trójki w \(\displaystyle{ \ZZ_{11}}\)
- piątki w \(\displaystyle{ \ZZ_{12}}\)
czwórki w \(\displaystyle{ \ZZ_{15}}\),
czyli kolejno \(\displaystyle{ 4,5, 4}\).
Po malutkiej redukcji Twoje kongruencje zamieniają się na:
\(\displaystyle{ \begin{cases} x \equiv 3(mod11) \\ x \equiv 6(mod12) \\ x \equiv 6(mod 15)\end{cases}}\)
o ile nie robię podstawowego błędu w mnożeniu, co niewykluczone

WhiteRabbit7 · Post autor: **WhiteRabbit7** » 13 kwie 2016, o 20:10

A w jaki sposób mogę sprawdzić, czy wynik \(\displaystyle{ 486x\equiv3636(mod3960)}\) jest poprawnym rozwiązaniem? Podstawić \(\displaystyle{ x = 3636(mod3960)/486}\) do \(\displaystyle{ \begin{cases} 3x \equiv 42(mod11) \\ 5x \equiv 42(mod12) \\ 8x \equiv 18(mod30)\end{cases}}\)
i sprawdzić, czy się zgadza we wszystkich równaniach?
Twój sposób jest oczywiście efektywniejszy, tylko ten, którym robię jest chyba bardziej uniwersalny i go w miarę ogarnąłem. Teraz tylko pytanie, czy działa.