Układ kongruencji
-
- Użytkownik
- Posty: 15
- Rejestracja: 8 paź 2007, o 14:38
- Płeć: Kobieta
- Lokalizacja: Tarnów
- Podziękował: 4 razy
Układ kongruencji
Witam. Bardzo chciałabym prosić o pomoc w rozwiązaniu jednego układu. Nie chodzi mi tutaj o rozwiązanie krok po kroku, lecz raczej o pewne wskazówki, zasady, schematy rozwiązywania takiego zadania.
Może przedstawię tutaj etap do którego doszłam podczas rozwiązywania takiego układu:
\(\displaystyle{ \left\{\begin{array}{l} x\equiv 7(mod 12)\\x\equiv 10(mod 15)\\x\equiv 8(mod 14) \end{array}}\)
Najpierw sprowadziłam układ do równoważnego mu układu takiego, by moduły kongruencji były parami względnie pierwsze:
\(\displaystyle{ x\equiv 7(mod 12) \Longleftrightarrow\left\{\begin{array}{l} x\equiv 7(mod 3)\\x\equiv 7(mod 4) \end{array}}\)
Co jest równoważne:
\(\displaystyle{ \left\{\begin{array}{l} x\equiv 1(mod 3)\\x\equiv 3(mod4) \end{array}}\)
\(\displaystyle{ x=1+3\cdot k}\)
\(\displaystyle{ 1+3\cdot k\equiv 3(mod4)}\)
\(\displaystyle{ 3\cdot k\equiv 2(mod4)}\)
Mnożę obydwie strony przez 3:
\(\displaystyle{ 9\cdot k\equiv 6(mod4)}\)
\(\displaystyle{ k=2+4\cdot s}\)
A więc:
\(\displaystyle{ x=1+3\cdot k=1+3\cdot (2+4\cdot s)=7+12\cdot s}\)
\(\displaystyle{ 7+12\cdot s\equiv 0(mod 5)}\)
\(\displaystyle{ 2+2\cdot s\equiv 0(mod5)}\)
\(\displaystyle{ 2\cdot s\equiv 3(mod 5)}\)
I pomnożyłam znowu przez 3 obydwie strony:
\(\displaystyle{ 6\cdot s\equiv 9(mod 5)}\)
\(\displaystyle{ s\equiv 4(mod 5)}\)
\(\displaystyle{ s=4+5\cdot t}\)
A więc:
\(\displaystyle{ x=7+12\cdot s=7+12\cdot (4+5\cdot t)=55+60\cdot t}\)
\(\displaystyle{ 55+60\cdot t\equiv 1(mod 3)}\)
\(\displaystyle{ 1+60\cdot t\equiv 1(mod 3)}\)
\(\displaystyle{ 60\cdot t\equiv 0(mod 3)}\)
A więc otrzymuję (jak się nie mylę) nierówność tożsamościową.
\(\displaystyle{ 55+60\cdot t\equiv 0(mod 2)}\)
\(\displaystyle{ 1+60\cdot t\equiv 0(mod 2)}\)
\(\displaystyle{ 60\cdot t\equiv 1(mod 2)}\)
I w tym miejscu pojawia się problem, który polega na mojej bezradności. Po prostu nie wiem co dalej.
W temacie zadania pisze, że rozwiązać o ile to możliwe. Jednak ani w tym układzie ani w drugim nie jestem w stanie rozwiązać go do końca.
Czy w takim razie jest możliwe rozwiązanie tego układu? Bardzo proszę o pomoc, o pewne wskazówki i informacje które pomogą mi rozwiązać to zadanie.
Będę bardzo wdzięczna.
Może przedstawię tutaj etap do którego doszłam podczas rozwiązywania takiego układu:
\(\displaystyle{ \left\{\begin{array}{l} x\equiv 7(mod 12)\\x\equiv 10(mod 15)\\x\equiv 8(mod 14) \end{array}}\)
Najpierw sprowadziłam układ do równoważnego mu układu takiego, by moduły kongruencji były parami względnie pierwsze:
\(\displaystyle{ x\equiv 7(mod 12) \Longleftrightarrow\left\{\begin{array}{l} x\equiv 7(mod 3)\\x\equiv 7(mod 4) \end{array}}\)
Co jest równoważne:
\(\displaystyle{ \left\{\begin{array}{l} x\equiv 1(mod 3)\\x\equiv 3(mod4) \end{array}}\)
\(\displaystyle{ x=1+3\cdot k}\)
\(\displaystyle{ 1+3\cdot k\equiv 3(mod4)}\)
\(\displaystyle{ 3\cdot k\equiv 2(mod4)}\)
Mnożę obydwie strony przez 3:
\(\displaystyle{ 9\cdot k\equiv 6(mod4)}\)
\(\displaystyle{ k=2+4\cdot s}\)
A więc:
\(\displaystyle{ x=1+3\cdot k=1+3\cdot (2+4\cdot s)=7+12\cdot s}\)
\(\displaystyle{ 7+12\cdot s\equiv 0(mod 5)}\)
\(\displaystyle{ 2+2\cdot s\equiv 0(mod5)}\)
\(\displaystyle{ 2\cdot s\equiv 3(mod 5)}\)
I pomnożyłam znowu przez 3 obydwie strony:
\(\displaystyle{ 6\cdot s\equiv 9(mod 5)}\)
\(\displaystyle{ s\equiv 4(mod 5)}\)
\(\displaystyle{ s=4+5\cdot t}\)
A więc:
\(\displaystyle{ x=7+12\cdot s=7+12\cdot (4+5\cdot t)=55+60\cdot t}\)
\(\displaystyle{ 55+60\cdot t\equiv 1(mod 3)}\)
\(\displaystyle{ 1+60\cdot t\equiv 1(mod 3)}\)
\(\displaystyle{ 60\cdot t\equiv 0(mod 3)}\)
A więc otrzymuję (jak się nie mylę) nierówność tożsamościową.
\(\displaystyle{ 55+60\cdot t\equiv 0(mod 2)}\)
\(\displaystyle{ 1+60\cdot t\equiv 0(mod 2)}\)
\(\displaystyle{ 60\cdot t\equiv 1(mod 2)}\)
I w tym miejscu pojawia się problem, który polega na mojej bezradności. Po prostu nie wiem co dalej.
W temacie zadania pisze, że rozwiązać o ile to możliwe. Jednak ani w tym układzie ani w drugim nie jestem w stanie rozwiązać go do końca.
Czy w takim razie jest możliwe rozwiązanie tego układu? Bardzo proszę o pomoc, o pewne wskazówki i informacje które pomogą mi rozwiązać to zadanie.
Będę bardzo wdzięczna.
-
- Użytkownik
- Posty: 2234
- Rejestracja: 26 paź 2006, o 18:08
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 22 razy
- Pomógł: 390 razy
Układ kongruencji
Znaczy nie sprawdzałem pełni Twoejgo zapisu, ale to co napisałaś na końcu jest oczywistą sprzecznością
-
- Użytkownik
- Posty: 15
- Rejestracja: 8 paź 2007, o 14:38
- Płeć: Kobieta
- Lokalizacja: Tarnów
- Podziękował: 4 razy
Układ kongruencji
A więc sprzeczność wychodzi wtedy kiedy mam coś takiego:
\(\displaystyle{ 60\cdot t\equiv 1(mod 2)}\)
A tożsamość, gdy:
\(\displaystyle{ 60\cdot t\equiv 0(mod 2)}\)
Bardzo proszę o wyjaśnienie moich wątpliwości
\(\displaystyle{ 60\cdot t\equiv 1(mod 2)}\)
A tożsamość, gdy:
\(\displaystyle{ 60\cdot t\equiv 0(mod 2)}\)
Bardzo proszę o wyjaśnienie moich wątpliwości
-
- Użytkownik
- Posty: 2234
- Rejestracja: 26 paź 2006, o 18:08
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 22 razy
- Pomógł: 390 razy
Układ kongruencji
No tak, masz rację. Dzieje się tak dlatego, że z zapisu \(\displaystyle{ 60t\equiv 1 \ (mod2)}\) wynika, że \(\displaystyle{ 60t=2k+1}\) Natomiast z zapisu \(\displaystyle{ 60t\equiv 0 \ (mod2)}\) jest spełnione dla każdego t
- Sir George
- Użytkownik
- Posty: 1145
- Rejestracja: 27 kwie 2006, o 10:19
- Płeć: Mężczyzna
- Lokalizacja: z Konopii
- Podziękował: 4 razy
- Pomógł: 203 razy
Układ kongruencji
BTW, już z księżyca widać, że układ jest sprzeczny...
A dokładniej sprzeczny jest układ kongruencji: \(\displaystyle{ \left\{\begin{array}{ll}x \equiv 7 & (\mod 12) \cr & \cr x\equiv 8 & (\mod 14)\end{array}\right.}\)
Po prostu z pierwszej kongruencji wynika, że x jest nieparzyste, a z drugiej natomiast, że jest parzyste...
Pozdrawiam ...
A dokładniej sprzeczny jest układ kongruencji: \(\displaystyle{ \left\{\begin{array}{ll}x \equiv 7 & (\mod 12) \cr & \cr x\equiv 8 & (\mod 14)\end{array}\right.}\)
Po prostu z pierwszej kongruencji wynika, że x jest nieparzyste, a z drugiej natomiast, że jest parzyste...
Pozdrawiam ...
-
- Użytkownik
- Posty: 2234
- Rejestracja: 26 paź 2006, o 18:08
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 22 razy
- Pomógł: 390 razy
-
- Użytkownik
- Posty: 15
- Rejestracja: 8 paź 2007, o 14:38
- Płeć: Kobieta
- Lokalizacja: Tarnów
- Podziękował: 4 razy
Układ kongruencji
Mam jeszcze jedną prośbę, także związaną z modułami.
Mam rozwiązać takie równianie
\(\displaystyle{ 10\cdot x\equiv 14(mod 12)}\)
I to potrafię rozwiązać. Chodzi mi tutaj o drugą część tego zadania, która brzmi:
W przypadku gdy istnieje podać rozwiązanie i poszukać najmniejszego rozwiązania nieujemnego
jak sie takie rozwiązanie szuka?? Jak się szuka także największej liczy ujemnej będącej rozwiązaniem szczególnym układu kongruencji?
I jeszcze jedno zadanko:
Wyliczyć:
\(\displaystyle{ d=NWD(a,b)}\)
i mam tutaj wskazać przedstawienie Bezouta dla d, jeśli:
\(\displaystyle{ a=26}\) i \(\displaystyle{ b=19}\)
Oczywiście wyliczyłam NWD, który wynosi:\(\displaystyle{ 1=-8\cdot 26+11\cdot 19}\)
I jak przedstawić to w postaci Bezouta??
Mam rozwiązać takie równianie
\(\displaystyle{ 10\cdot x\equiv 14(mod 12)}\)
I to potrafię rozwiązać. Chodzi mi tutaj o drugą część tego zadania, która brzmi:
W przypadku gdy istnieje podać rozwiązanie i poszukać najmniejszego rozwiązania nieujemnego
jak sie takie rozwiązanie szuka?? Jak się szuka także największej liczy ujemnej będącej rozwiązaniem szczególnym układu kongruencji?
I jeszcze jedno zadanko:
Wyliczyć:
\(\displaystyle{ d=NWD(a,b)}\)
i mam tutaj wskazać przedstawienie Bezouta dla d, jeśli:
\(\displaystyle{ a=26}\) i \(\displaystyle{ b=19}\)
Oczywiście wyliczyłam NWD, który wynosi:\(\displaystyle{ 1=-8\cdot 26+11\cdot 19}\)
I jak przedstawić to w postaci Bezouta??
-
- Użytkownik
- Posty: 2234
- Rejestracja: 26 paź 2006, o 18:08
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 22 razy
- Pomógł: 390 razy
Układ kongruencji
\(\displaystyle{ 10x \equiv 14 (mod12)}\) z tego wynika, że:
\(\displaystyle{ 10x=12l+14 \\ l\in Z}\)
\(\displaystyle{ 5x=6l+7}\)
\(\displaystyle{ x=\frac{6l+7}{5}}\) dalej rozważając prawą stronę:
\(\displaystyle{ 6l+7\equiv l+7 \(mod5)}\) czyli mamy:
\(\displaystyle{ l=5r-7 \\ r\in Z}\), bo musi przystawać do zera mofulo 5
czyli podstawiając:
\(\displaystyle{ x=\frac{6*(5r-7)+7}{5}=\frac{30r-42+7}{5}=\frac{30r-35}{5}=6r-7}\)
\(\displaystyle{ 10x=12l+14 \\ l\in Z}\)
\(\displaystyle{ 5x=6l+7}\)
\(\displaystyle{ x=\frac{6l+7}{5}}\) dalej rozważając prawą stronę:
\(\displaystyle{ 6l+7\equiv l+7 \(mod5)}\) czyli mamy:
\(\displaystyle{ l=5r-7 \\ r\in Z}\), bo musi przystawać do zera mofulo 5
czyli podstawiając:
\(\displaystyle{ x=\frac{6*(5r-7)+7}{5}=\frac{30r-42+7}{5}=\frac{30r-35}{5}=6r-7}\)